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 const_value_type = typename Data::const_value_type
The type of constant entries in the dataset.
-
using search_parameters_type = VamanaSearchParameters
The type of the configurable search parameters.
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
- 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 ¶meters, 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
- 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 ¶meters)
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
andset_search_parameters
.
-
template<typename Query>
inline void search(const Query &query, scratchspace_type &scratch) 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) Fill the result with the
num_neighbors
nearest neighbors for each query.Perform a multi-threaded graph search over the index, overwriting the contents of
result
with the results of search.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 thannum_neighbors
, it will temporarily be set tonum_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:
QueryType – The element of the queries.
I – The integer type used to encode neighbors in the QueryResult.
- Parameters:
queries – A dense collection of queries in R^n.
num_neighbors – The number of approximate nearest neighbors to return.
result – The result data structure to populate. Row
i
in the result corresponds to the neighbors for thei
th query. Neighbors within each row are ordered from nearest to furthest.
-
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 alli
inids
: Each ID is in-bounds.svs::getsize<1>(dst) == dimensions()
: The space allocated for each vector indst
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
-
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
- 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.
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 ¶meters, 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.