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 internal_id_type = Idx

The integer type used internally for IDs.

using external_id_type = Idx

The integer type used for external IDs.

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.

template<typename ThreadPoolProto>
inline VamanaIndex(Graph graph, Data data, Idx entry_point, Dist distance_function, ThreadPoolProto threadpool_proto, svs::logging::logger_ptr logger = svs::logging::get())

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.

ThreadPool

An acceptable thread pool should implement two methods:

• size_t size(). This method should return the number of threads used in the thread pool.

• void parallel_for(std::function<void(size_t)> f, size_t n). This method should execute f. Here, f(i) represents a task on the i^th partition, and n represents the number of partitions that need to be executed.

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_proto – Precursor for the thread pool to use. Can either be an acceptable thread pool instance or an integer specifying the number of threads to use. In the latter case, a new default thread pool will be constructed using threadpool_proto as the number of threads to create.

• logger_ – Spd logger for per-index logging customization.

template<threads::ThreadPool Pool>
inline VamanaIndex(const VamanaBuildParameters &parameters, Graph graph, Data data, Idx entry_point, Dist distance_function, Pool threadpool, svs::logging::logger_ptr logger = svs::logging::get())

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 acceptable threadpool to use to conduct searches.

• logger_ – Spd logger for per-index logging customization.

inline svs::logging::logger_ptr get_logger() const

Getter method for logger.

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

template<threads::ThreadPool Pool>
inline void set_threadpool(Pool threadpool)

Destroy the original thread pool and set to the provided one.

ThreadPool

An acceptable thread pool should implement two methods:

• size_t size(). This method should return the number of threads used in the thread pool.

• void parallel_for(std::function<void(size_t)> f, size_t n). This method should execute f. Here, f(i) represents a task on the i^th partition, and n represents the number of partitions that need to be executed.

Parameters:

threadpool – An acceptable thread pool.

inline threads::ThreadPoolHandle &get_threadpool_handle()

Return the current thread pool handle.

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

Get the value of alpha used during graph construction.

inline void set_alpha(float alpha)

Set the value of alpha to be used during graph construction.

inline size_t get_graph_max_degree() const

Get the graph_max_degree that was used for graph construction.

inline size_t get_max_candidates() const

Get the max candidate pool size that was used for graph construction.

inline void set_max_candidates(size_t max_candidates)

Set the max candidate pool size to be used for graph construction.

inline size_t get_prune_to() const

Get the prune_to value that was used for graph construction.

inline void set_prune_to(size_t prune_to)

Set the prune_to value to be used for graph construction.

inline size_t get_construction_window_size() const

Get the search window size that was used for graph construction.

inline void set_construction_window_size(size_t construction_window_size)

Set the search window size to be used for graph construction.

inline bool get_full_search_history() const

Return whether the full search history is being used for index construction.

inline void set_full_search_history(bool enable)

Enable using the full search history for candidate generation while building.

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.

template<typename F>
inline void experimental_escape_hatch(F &&f) const

Invoke the provided callable with constant references to the contained graph, data, and entry points.

This function is meant to provide a means for implementing experimental algorithms on the contained data structures.

template<typename Query>
inline double get_distance(size_t id, const Query &query) const

Compute the distance between a vector in the index and a query vector.

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, svs::logging::logger_ptr logger = svs::logging::get())

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.

ThreadPool

An acceptable thread pool should implement two methods:

• size_t size(). This method should return the number of threads used in the thread pool.

• void parallel_for(std::function<void(size_t)> f, size_t n). This method should execute f. Here, f(i) represents a task on the i^th partition, and n represents the number of partitions that need to be executed.

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 an acceptable thread pool instance or an integer specifying the number of threads to use.

• logger_ – Spd logger for per-index logging customization.

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 = {}, svs::logging::logger_ptr logger = svs::logging::get())

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

ThreadPool

An acceptable thread pool should implement two methods:

• size_t size(). This method should return the number of threads used in the thread pool.

• void parallel_for(std::function<void(size_t)> f, size_t n). This method should execute f. Here, f(i) represents a task on the i^th partition, and n represents the number of partitions that need to be executed.

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 an acceptable thread pool instance or an integer specifying the number of threads to use. In the latter case, a new default thread pool will be constructed using threadpool_proto as the number of threads to create.

• graph_allocator – The allocator to use for the graph data structure.

• logger_ – Spd logger for per-index logging customization.