Vamana Index

Main Vamana Class

template<graphs::ImmutableMemoryGraph Graph, data::ImmutableMemoryDataset Data, typename Dist> class VamanaIndex

Implementation of the static Vamana index.

The mid-level implementation of the static Vamana graph-based index.

We can’t enforce any constraints on Dist because at construction time, we don’t necessarily know what the query type is going to be (since it need not be the same as the dataset elements).

Checking of the full concept is done when the VamanaIndex is embedded inside some kind of searcher (and in the test suite).

Template Parameters:

Graph – The full type of the graph being used to conduct searches.
Data – The full type of the dataset being indexed.
Dist – The distance functor used to compare queries with elements of the dataset.
PostOp – The cleanup operation that is performed after the initial graph search. This may be included to perform operations like reranking for quantized datasets.

Public Types

using Idx = typename Graph::index_type: The integer type used to encode entries in the graph.

using value_type = typename Data::value_type: The type of entries in the dataset.

using const_value_type = typename Data::const_value_type: The type of constant entries in the dataset.

using distance_type = Dist : Type of the distance functor.

using graph_type = Graph : Type of the graph.

using data_type = Data : Type of the dataset.

using search_parameters_type = VamanaSearchParameters : The type of the configurable search parameters.

using inner_scratch_type = svs::tag_t<extensions::single_search_setup>::result_t<Data, Dist>: The type of the search resource used for external threading.

Public Functions

inline distance_type get_distance() const: Return a copy of the primary distance functor used by the index.

inline VamanaIndex(Graph graph, Data data, Idx entry_point, Dist distance_function, threads::NativeThreadPool threadpool)

Construct a VamanaIndex from constituent parts.

This is a lower-level function that is meant to take a collection of instantiated components and assemble the final index. For a more “hands-free” approach, see the factory methods.

Preconditions:

graph.n_nodes() == data.size(): Graph and data should have the same number of entries.

See also

auto_assemble

Parameters:

graph – An existing graph over data that has been previously constructed.
data – The dataset being indexed.
entry_point – The entry-point into the graph to begin searches.
distance_function – The distance function used to compare queries and elements of the dataset.
threadpool – The threadpool to use to conduct searches.

inline VamanaIndex(const VamanaBuildParameters &parameters, Graph graph, Data data, Idx entry_point, Dist distance_function, threads::NativeThreadPool threadpool)

Build a VamanaIndex over the given dataset.

This is a lower-level function that is meant to take a dataset and construct the graph-based index over the dataset. For a more “hands-free” approach, see the factory methods.

Preconditions:

graph.n_nodes() == data.size(): Graph and data should have the same number of entries.

See also

auto_build

Parameters:

parameters – The build parameters used to construct the graph.
graph – An unpopulated graph with the same size as data. This graph will be populated as part of the constructor operation.
data – The dataset to be indexed indexed.
entry_point – The entry-point into the graph to begin searches.
distance_function – The distance function used to compare queries and elements of the dataset.
threadpool – The threadpool to use to conduct searches.

inline void apply(const VamanaIndexParameters &parameters): Apply the given configuration parameters to the index.

inline scratchspace_type scratchspace(const VamanaSearchParameters &sp) const: Return scratch space resources for external threading.

inline scratchspace_type scratchspace() const

Return scratch-space resources for external threading with default parameters.

The default parameters can be accessed using get_search_parameters and set_search_parameters.

template<typename Query> inline void search(const Query &query, scratchspace_type &scratch, const lib::DefaultPredicate &cancel = lib::Returns(lib::Const<false>())) const

Perform a nearest neighbor search for query using the provided scratch space.

Operations performed:

Graph search to obtain k-nearest neighbors.
Search result reranking (if needed).

Results will be present in the data structures contained inside scratch. Extraction should pull out the search buffer for extra post-processing.

Note: It is the caller’s responsibility to ensure that the scratch space has been initialized properly to return the requested number of neighbors.

template<typename I, data::ImmutableMemoryDataset Queries> inline void search(QueryResultView<I> result, const Queries &queries, const search_parameters_type &search_parameters, const lib::DefaultPredicate &cancel = lib::Returns(lib::Const<false>()))

Fill the result with the num_neighbors nearest neighbors for each query.

After the initial graph search, a post-operation defined by the PostOp type parameter will be conducted which may conduct refinement on the candidates.

If the current value of get_search_window_size() is less than num_neighbors, it will temporarily be set to num_neighbors.

Preconditions:

The following pre-conditions must hold. Otherwise, the behavior is undefined.

result.n_queries() == queries.size()
result.n_neighbors() == num_neighbors.
The value type of queries is compatible with the value type of the index dataset with respect to the stored distance functor.

Template Parameters:

I – The integer type used to encode neighbors in the QueryResult.
QueryType – The element of the queries.

Parameters:

result – The result data structure to populate. Row i in the result corresponds to the neighbors for the ith query. Neighbors within each row are ordered from nearest to furthest. num_neighbors is computed from the number of columns in result.
queries – A dense collection of queries in R^n.
search_parameters – search parameters to use for the search.
cancel – A predicate called during the search to determine if the search should be cancelled. Perform a multi-threaded graph search over the index, overwriting the contents of result with the results of search.

inline size_t size() const: Return the number of vectors in the index.

inline size_t dimensions() const: Return the logical number aLf dimensions of the indexed vectors.

template<std::unsigned_integral I, svs::Arithmetic T> inline void reconstruct_at(data::SimpleDataView<T> dst, std::span<const I> ids)

Reconstruct vectors.

Reconstruct each vector indexed by an external ID and store the results into dst.

Preconditions:

ids.size() == svs::getsize<0>(dst): Each ID has a corresponding entry in the destination array.
0 <= i < size() for all i in ids: Each ID is in-bounds.
svs::getsize<1>(dst) == dimensions(): The space allocated for each vector in dst is correct.

An exception will be thrown if any of these pre-conditions does not hold. If such an exception is thrown, the argument dst will be left unmodified.

inline size_t get_num_threads() const

Return the current number of threads used for search.

See also

set_num_threads

inline void set_num_threads(size_t num_threads)

Set the number of threads used for search.

Implementation note: The number of threads cannot be zero. If zero is passed to this method, it will be silently changed to 1.

See also

get_num_threads

Parameters:: num_threads – The new number of threads to use.

inline threads::NativeThreadPool &borrow_threadpool()

Obtain the underlying threadpool.

N.B.: Jobs may be run on the thread pool but it may not be resized safely.

inline VamanaSearchParameters get_search_parameters() const

Return the current search parameters stored by the index.

These parameters include

inline void reset_performance_parameters()

Reset performance parameters to their default values for this index.

Parameters affected are only those that modify throughput on a given architecture. Accuracy results should not change as a side-effect of calling this function.

inline float get_alpha() const: Return the value of alpha used during graph construction.

inline size_t get_max_candidates() const: Return the max candidate pool size that was used for graph construction.

inline size_t get_construction_window_size() const: Return the search window size that was used for graph construction.

inline void set_full_search_history(bool enable): Enable using the full search history for candidate generation while building.

inline bool get_full_search_history() const: Return whether the full search history is being used for index construction.

inline void save(const std::filesystem::path &config_directory, const std::filesystem::path &graph_directory, const std::filesystem::path &data_directory) const

Save the whole index to disk to enable reloading in the future.

In general, the save locations must be directories since each data structure (config, graph, and data) may require an arbitrary number of auxiliary files in order to by completely saved to disk. The given directories must be different.

Each directory may be created as a side-effect of this method call provided that the parent directory exists. Data in existing directories will be overwritten without warning.

The choice to use a multi-directory structure is to enable design-space exploration with different data quantization techniques or graph implementations. That is, the save format for the different components is designed to be orthogonal to allow mixing and matching of different types upon reloading.

Parameters:

config_directory – Directory where the index metadata will be saved. The contents of the metadata include the configured search window size, entry point etc.
graph_directory – Directory where the graph will be saved.
data_directory – Directory where the vector dataset will be saved.

Public Static Functions

static inline bool can_change_threads(): Return whether this implementation can dynamically change the number of threads.

Public Static Attributes

static constexpr size_t extent = Data::extent: The static dimensionality of the dataset.

Vamana Entry Point

Instantiating an instance of the VamanaIndex can be tricky and has many different pieces that need to come together correctly. To assist with this operation, the factor methods are supplied that can handle many different (both documented and documented) combinations of data set types, graph types, and distances. These methods are documented below.

template<typename GraphProto, typename DataProto, typename Distance, typename ThreadPoolProto> auto svs::index::vamana::auto_assemble(const std::filesystem::path &config_path, GraphProto graph_loader, DataProto data_proto, Distance distance, ThreadPoolProto threadpool_proto)

Entry point for loading a Vamana graph-index from disk.

This method provides much of the heavy lifting for instantiating a Vamana index from a collection of files on disk (or perhaps a mix-and-match of existing data in-memory and on disk).

Refer to the examples for use of this interface.

Parameters:

config_path – The directory where the index configuration file resides.
graph_loader – A svs::GraphLoader for loading the graph.
data_proto – A dispatch loadable class yielding a dataset.
distance – The distance functor to use to compare queries with elements of the dataset.
threadpool_proto – Precursor for the thread pool to use. Can either be a threadpool instance of an integer specifying the number of threads to use.

template<typename DataProto, typename Distance, typename ThreadpoolProto, typename Allocator = HugepageAllocator<uint32_t>> auto svs::index::vamana::auto_build(const VamanaBuildParameters &parameters, DataProto data_proto, Distance distance, ThreadpoolProto threadpool_proto, const Allocator &graph_allocator = {})

Entry point for loading a Vamana graph-index from disk.

Parameters:

parameters – The parameters to use for graph construction.
data_proto – A dispatch loadable class yielding a dataset.
distance – The distance functor to use to compare queries with elements of the dataset.
threadpool_proto – Precursor for the thread pool to use. Can either be a threadpool instance of an integer specifying the number of threads to use.
graph_allocator – The allocator to use for the graph data structure.