Vamana Graph Index
In this section, we cover the API and usage of the Vamana graph-based index.
- class svs.Vamana
Top level class for the Vamana graph index.
- __init__(self: svs::python.Vamana, config_path: str, graph_loader: svs::python.GraphLoader, data_loader: Union[svs::python.VectorDataLoader, svs::python.LVQLoader, svs::python.LeanVecLoader, svs::python.SerializedObject], distance: svs::python.DistanceType = <DistanceType.L2: 0>, query_type: svs::python.DataType = <DataType.float32: 9>, enforce_dims: bool = False, num_threads: int = 1) None
Load a Vamana style index from disk.
- Parameters:
config_path – Path to the directory where the index configuration file was generated.
graph_loader – The loader class for the graph.
data_loader – The loader for the dataset. See comment below for accepted types.
distance – The distance function to use.
query_type – The data type of the queries.
enforce_dims –
Require that the compiled dimensionality of the returned index matches the dimensionality provided in the
data_loader
argument. If a match is not found, an exception is thrown.This is meant to ensure that specialized dimensionality is provided without falling back to generic implementations. Leaving the
dims
out when constructing thedata_loader
will with enable_dims = True will always attempt to use a generic implementation.num_threads – The number of threads to use for queries (can be changed after loading).
The top level type is an abstract type backed by various specialized backends that will be instantiated based on their applicability to the particular problem instance.
The arguments upon which specialization is conducted are:
data_loader: Both kind (type of loader) and inner aspects of the loader like data type, quantization type, and number of dimensions.
distance: The distance measure being used.
Specializations compiled into the binary are listed below.
- Method 0:
data_loader: VectorDataLoader with element type float32 and any dimension OR unknown – (union alternatives 0, 3)
distance: all values
- Method 1:
data_loader: VectorDataLoader with element type float16 and any dimension OR unknown – (union alternatives 0, 3)
distance: all values
- Method 2:
data_loader: VectorDataLoader with element type uint8 and any dimension OR unknown – (union alternatives 0, 3)
distance: all values
- Method 3:
data_loader: VectorDataLoader with element type int8 and any dimension OR unknown – (union alternatives 0, 3)
distance: all values
- Method 4:
data_loader: LVQLoader 4x0 (sequential) with any dimensions OR unknown – (union alternatives 1, 3)
distance: L2
- Method 5:
data_loader: LVQLoader 4x0 (sequential) with any dimensions OR unknown – (union alternatives 1, 3)
distance: MIP
- Method 6:
data_loader: LVQLoader 4x8 (sequential) with any dimensions OR unknown – (union alternatives 1, 3)
distance: L2
- Method 7:
data_loader: LVQLoader 4x8 (sequential) with any dimensions OR unknown – (union alternatives 1, 3)
distance: MIP
- Method 8:
data_loader: LVQLoader 4x8 (turbo<16x8>) with any dimensions OR unknown – (union alternatives 1, 3)
distance: L2
- Method 9:
data_loader: LVQLoader 4x8 (turbo<16x8>) with any dimensions OR unknown – (union alternatives 1, 3)
distance: MIP
- Method 10:
data_loader: LVQLoader 8x0 (sequential) with any dimensions OR unknown – (union alternatives 1, 3)
distance: L2
- Method 11:
data_loader: LVQLoader 8x0 (sequential) with any dimensions OR unknown – (union alternatives 1, 3)
distance: MIP
- Method 12:
data_loader: LVQLoader 8x8 (sequential) with any dimensions OR unknown – (union alternatives 1, 3)
distance: L2
- Method 13:
data_loader: LVQLoader 8x8 (sequential) with any dimensions OR unknown – (union alternatives 1, 3)
distance: MIP
- Method 14:
data_loader: LeanVecLoader dims-anyxany OR unknown – (union alternatives 2, 3)
distance: L2
- Method 15:
data_loader: LeanVecLoader dims-anyxany OR unknown – (union alternatives 2, 3)
distance: MIP
- Method 16:
data_loader: LeanVecLoader dims-anyxany OR unknown – (union alternatives 2, 3)
distance: L2
- Method 17:
data_loader: LeanVecLoader dims-anyxany OR unknown – (union alternatives 2, 3)
distance: MIP
- Method 18:
data_loader: LeanVecLoader dims-anyxany OR unknown – (union alternatives 2, 3)
distance: L2
- Method 19:
data_loader: LeanVecLoader dims-anyxany OR unknown – (union alternatives 2, 3)
distance: MIP
- Method 20:
data_loader: LeanVecLoader dims-anyxany OR unknown – (union alternatives 2, 3)
distance: L2
- Method 21:
data_loader: LeanVecLoader dims-anyx64 OR unknown – (union alternatives 2, 3)
distance: L2
- Method 22:
data_loader: LeanVecLoader dims-anyxany OR unknown – (union alternatives 2, 3)
distance: MIP
- Method 23:
data_loader: LeanVecLoader dims-768x160 OR unknown – (union alternatives 2, 3)
distance: MIP
- static build(*args, **kwargs)
Overloaded function.
build(parameters: svs::python.VamanaBuildParameters, py_data: numpy.ndarray[float16], distance_type: svs::python.DistanceType, num_threads: int = 1) -> svs::python.Vamana
Construct a Vamana index over the given data, returning a searchable index.
- Parameters:
parameters – Parameters controlling graph construction. See the documentation of this class.
py_data – The dataset to index. NOTE: SVS will maintain an internal copy of the dataset. This may change in future releases.
distance_type – The distance type to use for this dataset.
num_threads – The number of threads to use for index construction. Default: 1.
build(parameters: svs::python.VamanaBuildParameters, py_data: numpy.ndarray[numpy.float32], distance_type: svs::python.DistanceType, num_threads: int = 1) -> svs::python.Vamana
Construct a Vamana index over the given data, returning a searchable index.
- Parameters:
parameters – Parameters controlling graph construction. See the documentation of this class.
py_data – The dataset to index. NOTE: SVS will maintain an internal copy of the dataset. This may change in future releases.
distance_type – The distance type to use for this dataset.
num_threads – The number of threads to use for index construction. Default: 1.
build(parameters: svs::python.VamanaBuildParameters, py_data: numpy.ndarray[numpy.uint8], distance_type: svs::python.DistanceType, num_threads: int = 1) -> svs::python.Vamana
Construct a Vamana index over the given data, returning a searchable index.
- Parameters:
parameters – Parameters controlling graph construction. See the documentation of this class.
py_data – The dataset to index. NOTE: SVS will maintain an internal copy of the dataset. This may change in future releases.
distance_type – The distance type to use for this dataset.
num_threads – The number of threads to use for index construction. Default: 1.
build(parameters: svs::python.VamanaBuildParameters, py_data: numpy.ndarray[numpy.int8], distance_type: svs::python.DistanceType, num_threads: int = 1) -> svs::python.Vamana
Construct a Vamana index over the given data, returning a searchable index.
- Parameters:
parameters – Parameters controlling graph construction. See the documentation of this class.
py_data – The dataset to index. NOTE: SVS will maintain an internal copy of the dataset. This may change in future releases.
distance_type – The distance type to use for this dataset.
num_threads – The number of threads to use for index construction. Default: 1.
build(build_parameters: svs::python.VamanaBuildParameters, data_loader: Union[svs::python.VectorDataLoader, svs::python.LVQLoader, svs::python.LeanVecLoader], distance_type: svs::python.DistanceType, num_threads: int = 1) -> svs::python.Vamana
Construct a Vamana index over the given data file, returning a searchable index.
- Parameters:
build_parameters (
svs.VamanaBuildParameters
) – Hyper-parameters controlling index build.data_loader – The source of the data on-disk. Can either be
svs.DataFile
to represent a standard uncompressed dataset, or a compressed loader.distance_type – The similarity-function to use for this index.
num_threads – The number of threads to use for index construction. Default: 1.
The top level type is an abstract type backed by various specialized backends that will be instantiated based on their applicability to the particular problem instance.
The arguments upon which specialization is conducted are:
data_loader: Both kind (type of loader) and inner aspects of the loader like data type, quantization type, and number of dimensions.
distance: The distance measure being used.
Specializations compiled into the binary are listed below.
- Method 0:
data_loader: VectorDataLoader with element type float32 and any dimension – (union alternative 0)
distance: all values
- Method 1:
data_loader: VectorDataLoader with element type float16 and any dimension – (union alternative 0)
distance: all values
- Method 2:
data_loader: VectorDataLoader with element type uint8 and any dimension – (union alternative 0)
distance: all values
- Method 3:
data_loader: VectorDataLoader with element type int8 and any dimension – (union alternative 0)
distance: all values
- Method 4:
data_loader: LVQLoader 4x0 (sequential) with any dimensions – (union alternative 1)
distance: L2
- Method 5:
data_loader: LVQLoader 4x0 (sequential) with any dimensions – (union alternative 1)
distance: MIP
- Method 6:
data_loader: LVQLoader 4x8 (sequential) with any dimensions – (union alternative 1)
distance: L2
- Method 7:
data_loader: LVQLoader 4x8 (sequential) with any dimensions – (union alternative 1)
distance: MIP
- Method 8:
data_loader: LVQLoader 4x8 (turbo<16x8>) with any dimensions – (union alternative 1)
distance: L2
- Method 9:
data_loader: LVQLoader 4x8 (turbo<16x8>) with any dimensions – (union alternative 1)
distance: MIP
- Method 10:
data_loader: LVQLoader 8x0 (sequential) with any dimensions – (union alternative 1)
distance: L2
- Method 11:
data_loader: LVQLoader 8x0 (sequential) with any dimensions – (union alternative 1)
distance: MIP
- Method 12:
data_loader: LeanVecLoader dims-anyxany – (union alternative 2)
distance: L2
- Method 13:
data_loader: LeanVecLoader dims-anyxany – (union alternative 2)
distance: MIP
- Method 14:
data_loader: LeanVecLoader dims-anyxany – (union alternative 2)
distance: L2
- Method 15:
data_loader: LeanVecLoader dims-anyxany – (union alternative 2)
distance: MIP
- Method 16:
data_loader: LeanVecLoader dims-anyxany – (union alternative 2)
distance: L2
- Method 17:
data_loader: LeanVecLoader dims-anyxany – (union alternative 2)
distance: MIP
- Method 18:
data_loader: LeanVecLoader dims-anyxany – (union alternative 2)
distance: L2
- Method 19:
data_loader: LeanVecLoader dims-anyx64 – (union alternative 2)
distance: L2
- Method 20:
data_loader: LeanVecLoader dims-anyxany – (union alternative 2)
distance: MIP
- Method 21:
data_loader: LeanVecLoader dims-768x160 – (union alternative 2)
distance: MIP
- property dimensions
Return the logical number of dimensions for each vector in the dataset.
- property experimental_backend_string
Get a string identifying the full-type of the backend implementation.
This property is experimental and subject to change without a deprecation warning.
- Type:
Read Only (str)
- experimental_calibrate(*args, **kwargs)
Overloaded function.
experimental_calibrate(self: svs::python.Vamana, queries: numpy.ndarray[float16], groundtruth: numpy.ndarray[numpy.uint32], num_neighbors: int, target_recall: float, calibration_parameters: svs::python.VamanaCalibrationParameters = <svs::python.VamanaCalibrationParameters object at 0x7f6749ecb1f0>) -> svs::python.VamanaSearchParameters
NOTE: This method is experimental and subject to change or removal without notice.
Run an experimental calibration routine to select the best search parameters.
- Parameters:
queries – Queries used to drive the calibration process.
groundtruth – The groundtruth for the given query set.
num_neighbors – The number of nearest neighbors to calibrate for.
target_recall – The target num_neighbors-recall-at-num_neighbors. If such a recall is possible, then calibration will find parameters that optimize performance at this recall level.
calibration_parameters – The hyper-parameters to use during calibration.
- Returns:
The best svs.VamanaSearchParameters found.
The calibration routine will also configure the index with the best found parameters. Note that calibration will use the number of threads already assigned to the index and can therefore be used to tune the algorithm to different threading amounts.
See also: svs.VamanaCalibrationParameters
experimental_calibrate(self: svs::python.Vamana, queries: numpy.ndarray[numpy.float32], groundtruth: numpy.ndarray[numpy.uint32], num_neighbors: int, target_recall: float, calibration_parameters: svs::python.VamanaCalibrationParameters = <svs::python.VamanaCalibrationParameters object at 0x7f674b828e70>) -> svs::python.VamanaSearchParameters
NOTE: This method is experimental and subject to change or removal without notice.
Run an experimental calibration routine to select the best search parameters.
- Parameters:
queries – Queries used to drive the calibration process.
groundtruth – The groundtruth for the given query set.
num_neighbors – The number of nearest neighbors to calibrate for.
target_recall – The target num_neighbors-recall-at-num_neighbors. If such a recall is possible, then calibration will find parameters that optimize performance at this recall level.
calibration_parameters – The hyper-parameters to use during calibration.
- Returns:
The best svs.VamanaSearchParameters found.
The calibration routine will also configure the index with the best found parameters. Note that calibration will use the number of threads already assigned to the index and can therefore be used to tune the algorithm to different threading amounts.
See also: svs.VamanaCalibrationParameters
- experimental_reset_performance_parameters(self: svs::python.Vamana) None
Reset the internal performance-only parameters to built-in heuristics. This can be useful if experimenting with different dataset implementations which may need different values for performance-only parameters (such as prefetchers).
Calling this method should not affect recall.
- property num_threads
Get and set the number of threads used to process queries.
- Type:
Read/Write (int)
- property query_types
Return the query element types this index is specialized for.
- reconstruct(self: svs::python.Vamana, ids: numpy.ndarray[numpy.uint64]) numpy.ndarray[numpy.float32]
- save(self: svs::python.Vamana, config_directory: str, graph_directory: str, data_directory: str) None
Save a constructed index to disk (useful following index construction).
- Parameters:
config_directory – Directory where index configuration information will be saved.
graph_directory – Directory where graph will be saved.
data_directory – Directory where the dataset will be saved.
Note: All directories should be separate to avoid accidental name collision with any auxiliary files that are needed when saving the various components of the index.
If the directory does not exist, it will be created if its parent exists.
It is the caller’s responsibilty to ensure that no existing data will be overwritten when saving the index to this directory.
- search(*args, **kwargs)
Overloaded function.
search(self: svs::python.Vamana, queries: numpy.ndarray[float16], n_neighbors: int) -> tuple
Perform a search to return the n_neighbors approximate nearest neighbors to the query.
- Parameters:
queries – Numpy Vector or Matrix representing the queries. If the argument is a vector, it will be treated as a single query. If the argument is a matrix, individual queries are assumed to the rows of the matrix. Returned results will have a position-wise correspondence with the queries. That is, the N-th row of the returned IDs and distances will correspond to the N-th row in the query matrix.
n_neighbors – The number of neighbors to return for this search job.
- Returns:
A tuple (I, D) where I contains the n_neighbors approximate (or exact) nearest neighbors to the queries and D contains the approximate distances.
Note: This form is returned regardless of whether the given query was a vector or a matrix.
search(self: svs::python.Vamana, queries: numpy.ndarray[numpy.float32], n_neighbors: int) -> tuple
Perform a search to return the n_neighbors approximate nearest neighbors to the query.
- Parameters:
queries – Numpy Vector or Matrix representing the queries. If the argument is a vector, it will be treated as a single query. If the argument is a matrix, individual queries are assumed to the rows of the matrix. Returned results will have a position-wise correspondence with the queries. That is, the N-th row of the returned IDs and distances will correspond to the N-th row in the query matrix.
n_neighbors – The number of neighbors to return for this search job.
- Returns:
A tuple (I, D) where I contains the n_neighbors approximate (or exact) nearest neighbors to the queries and D contains the approximate distances.
Note: This form is returned regardless of whether the given query was a vector or a matrix.
search(self: svs::python.Vamana, queries: numpy.ndarray[numpy.uint8], n_neighbors: int) -> tuple
Perform a search to return the n_neighbors approximate nearest neighbors to the query.
- Parameters:
queries – Numpy Vector or Matrix representing the queries. If the argument is a vector, it will be treated as a single query. If the argument is a matrix, individual queries are assumed to the rows of the matrix. Returned results will have a position-wise correspondence with the queries. That is, the N-th row of the returned IDs and distances will correspond to the N-th row in the query matrix.
n_neighbors – The number of neighbors to return for this search job.
- Returns:
A tuple (I, D) where I contains the n_neighbors approximate (or exact) nearest neighbors to the queries and D contains the approximate distances.
Note: This form is returned regardless of whether the given query was a vector or a matrix.
search(self: svs::python.Vamana, queries: numpy.ndarray[numpy.int8], n_neighbors: int) -> tuple
Perform a search to return the n_neighbors approximate nearest neighbors to the query.
- Parameters:
queries – Numpy Vector or Matrix representing the queries. If the argument is a vector, it will be treated as a single query. If the argument is a matrix, individual queries are assumed to the rows of the matrix. Returned results will have a position-wise correspondence with the queries. That is, the N-th row of the returned IDs and distances will correspond to the N-th row in the query matrix.
n_neighbors – The number of neighbors to return for this search job.
- Returns:
A tuple (I, D) where I contains the n_neighbors approximate (or exact) nearest neighbors to the queries and D contains the approximate distances.
Note: This form is returned regardless of whether the given query was a vector or a matrix.
- property search_parameters
Get/set the current search parameters for the index. These parameters modify both the algorithmic properties of search (affecting recall) and non-algorthmic properties of search (affecting queries-per-second).
See also: svs.VamanaSearchParameters.
- Type:
“Read/Write (svs.VamanaSearchParameters)
- property search_window_size
Get/set the size of the internal search buffer. A larger value will likely yield more accurate results at the cost of speed.
- Type:
Read/Write (int)
- property size
Return the number of elements in the indexed dataset.
- property visited_set_enabled
Deprecated
Read/Write (bool): Get/set whether the visited set is used. Enabling the visited set can be helpful if the distance computations required are relatively expensive as it can reduce redundant computations.
In general, through, it’s probably faster to leave this disabled.
- class svs.VamanaBuildParameters
Build parameters for Vamana index construction.
- __init__(self: svs::python.VamanaBuildParameters, alpha: float = 1.2, graph_max_degree: int = 32, window_size: int = 64, max_candidate_pool_size: int = 80, prune_to: int = 18446744073709551615, num_threads: int = 18446744073709551615) None
Construct a new instance from keyword arguments.
- Parameters:
alpha – Prune threshold degree for graph construction. For distance types favoring minimization, set this to a number greater than 1.0 (typically, 1.2 is sufficient). For distance types preferring maximization, set to a value less than 1.0 (such as 0.95).
graph_max_degree – The maximum out-degree in the final graph. Graphs with a higher degree tend to yield better accuracy and performance at the cost of a larger memory footprint.
window_size – Parameter controlling the quality of graph construction. A larger window size will yield a higher-quality index at the cost of longer construction time. Should be larger than graph_max_degree.
max_candidate_pool_size – Limit on the number of candidates to consider for neighbor updates. Should be larger than window_size.
prune_to – Amount candidate lists will be pruned to when exceeding the target max degree. In general, setting this to slightly less than graph_max_degree will yield faster index building times. Default: graph_max_degree.
- class svs.VamanaSearchParameters
Parameters controlling recall and performance of the VamanaIndex. See also:
Vamana.search_parameters
.- buffer_config
Configuration state for the underlying search buffer.
- Type:
svs.SearchBufferConfig
, read/write
- search_buffer_visited_set
Enable/disable status of the search buffer visited set.
- Type:
bool, read/write
- prefetch_lookahead
The number of iterations ahead to prefetch during graph search.
- Type:
unsigned int, read/write
- prefetch_step
The maximum number of iterations to prefetch at a time until the desired prefetch_lookahead is achieved. Setting this to 1 is special and has the same effect setting this to prefetch_lookahead + 1.
- Type:
unsigned int, read/write
Setting either
prefetch_lookahead
orprefetch_step
to zero disables candidate prefetching during search.- __init__(self: svs::python.VamanaSearchParameters, buffer_config: svs::python.SearchBufferConfig = <svs::python.SearchBufferConfig object at 0x7f6749ec8070>, search_buffer_visited_set: bool = False, prefetch_lookahead: int = 4, prefetch_step: int = 1) None
- class svs.SearchBufferConfig
Size configuration for the Vamana index search buffer.` See also:
svs.VamanaSearchParameters
,svs.Vamana.search_parameters()
.- search_window_size
The number of valid entries in the buffer that will be used to determine stopping conditions for graph search.
- Type:
int, read-only
- search_buffer_capacity
The (expected) number of valid entries that will be available. Must be at least as large as search_window_size.
- Type:
int, read-only
- __init__(*args, **kwargs)
Overloaded function.
__init__(self: svs::python.SearchBufferConfig) -> None
__init__(self: svs::python.SearchBufferConfig, search_window_size: int) -> None
Configure with a given search window size. This constructor implicitly defaults
search_buffer_capacity
tosearch_window_size
.__init__(self: svs::python.SearchBufferConfig, search_window_size: int, search_buffer_capacity: int) -> None
Configure with a given search window size and capacity. Raises
svs.ANNException
ifsearch_buffer_capacity < search_window_size
.
- class svs.VamanaCalibrationParameters
Hyper-parameters controlling performance tuning of the Vamana and DynamicVamana indexes. See also:
Vamana.experimental_calibrate()
andDynamicVamana.experimental_calibrate()
.- search_window_size_upper
The maximum search window size to check.
- Type:
int
- search_window_capacity_upper
The maximum search capacity to check.
- Type:
int
- timing_iterations
The maximum number iterations an indexed will be searched at a time for purposes of obtaining a measurement of search performance.
- Type:
int
- search_timeout
A search bound (in seconds). Obtaining performance measurements will terminate early if the aggregate search time for a given setting exceeds this bound.
- Type:
float
- prefetch_steps
Steps to try when optimizing Prefetching.
- Type:
List[int]
- search_buffer_optimization
Setting for optimizing the index search buffer.
Disable: Do not optimize the search buffer at all.
All: Optimize both search window size and capacity.
ROIOnly: Only optimize the search window size. Capacity will always be equal to the search window size.
- train_prefetchers
Flag to train prefetch parameters.
- Type:
bool
- use_existing_parameter_values
Should optimization use existing search parameters or should it use defaults instead.
- Type:
bool
- __init__(self: svs::python.VamanaCalibrationParameters) None
Instantiate with default parameters.
- class svs.VamanaSearchBufferOptimization
How should calibration optimize the search buffer.
Members:
Disable : Disable search buffer optimization.
All : Optimize both search window size and capacity (if helpful).
ROIOnly : Only optimize the search window size, setting the capacity equal to the search window size.
ROITuneUp : Optimize the search buffer while keeping the capacity fixed. This routine can be used to slightly tweak accuracy numbers without relying on performance information.
- property name
Example
This example will cover the following topics:
Building a
svs.Vamana
index from a dataset.Performing queries to retrieve neighbors from a
svs.Vamana
.Saving the index to disk.
Loading a
svs.Vamana
from disk.Compressing an on-disk dataset and loading/searching with a compressed
svs.Vamana
.
The complete example is included at the end of this file.
Preamble
First, it is assumed that svs
is installed and available to Python.
We first need to perform a couple of imports.
import os
import svs
Then, we generate a sample dataset using the svs.generate_test_dataset()
generation function.
This function generates a data file, a query file, and the ground truth.
Note
The svs.generate_test_dataset()
function generates datasets randomly
with no semantic meaning for the elements within it.
Recall values for this dataset are usually lower than for real datasets.
# Create a test dataset.
# This will create a directory "example_data_vamana" and populate it with three
# entries:
# - data.fvecs: The test dataset.
# - queries.fvecs: The test queries.
# - groundtruth.ivecs: The groundtruth.
test_data_dir = "./example_data_vamana"
svs.generate_test_dataset(
10000, # Create 10000 vectors in the dataset.
1000, # Generate 1000 query vectors.
128, # Set the vector dimensionality to 128.
test_data_dir, # The directory where results will be generated.
data_seed = 1234, # Random number seed for reproducibility.
query_seed = 5678, # Random number seed for reproducibility.
num_threads = 4, # Number of threads to use.
distance = svs.DistanceType.L2, # The distance type to use.
)
Building and Index
Now that data has been generated, we need to construct an index over that data.
The index is a graph connecting related data vectors in such a way that searching for nearest neighbors yields good results.
The first step is to construct an instance of svs.VamanaBuildParameters
to describe the hyper-parameters of the graph we wish to construct.
Don’t worry too much about selecting the correct values for these hyper-parameters right now.
This usually involves a bit of experimentation and is dataset dependent.
Now that we’ve established our parameters, it is time to construct the index.
Note the use of svs.VectorDataLoader
to indicate both the file path and the element type of the fvecs
file on disk.
Passing the dims
is optional, but may yield performance benefits if given.
# Build the index.
index = svs.Vamana.build(
parameters,
svs.VectorDataLoader(
os.path.join(test_data_dir, "data.fvecs"), svs.DataType.float32
),
svs.DistanceType.L2,
num_threads = 4,
)
Searching the Index
The graph is now built and we can perform queries over the graph.
First, we load the queries and the computed ground truth for our example dataset using svs.read_vecs()
.
# Load the queries and ground truth.
queries = svs.read_vecs(os.path.join(test_data_dir, "queries.fvecs"))
groundtruth = svs.read_vecs(os.path.join(test_data_dir, "groundtruth.ivecs"))
Performing queries is easy.
First establish a base-line search window size (svs.Vamana.search_window_size
).
This provides a parameter by which performance and accuracy can be traded.
The larger search_window_size
is, the higher the accuracy but the lower the performance.
Note that search_window_size
must be at least as large as the desired number of neighbors.
# Set the search window size of the index and perform queries.
index.search_window_size = 30
I, D = index.search(queries, 10)
# Compare with the groundtruth.
recall = svs.k_recall_at(groundtruth, I, 10, 10)
print(f"Recall = {recall}")
assert(recall == 0.8288)
We use svs.Vamana.search()
to find the 10 approximate nearest neighbors to each query.
Then, we use svs.k_recall_at()
to compute the 10-recall at 10 of the returned neighbors, checking to confirm the accuracy.
The code snippet below demonstrates how to vary the search window size to change the achieved recall.
# Set the search window size of the index and perform queries.
index.search_window_size = 30
I, D = index.search(queries, 10)
# Compare with the groundtruth.
recall = svs.k_recall_at(groundtruth, I, 10, 10)
print(f"Recall = {recall}")
assert(recall == 0.8288)
Saving the Index
If you are satisfied with the performance of the generated index, you can save it to disk to avoid rebuilding it in the future.
This is done with svs.Vamana.save()
.
# Finally, we can save the results.
index.save(
os.path.join(test_data_dir, "example_config"),
os.path.join(test_data_dir, "example_graph"),
os.path.join(test_data_dir, "example_data"),
)
Note
The svs.Vamana
index currently uses three files for saving.
All three are needed to be able to reload the index.
One file for the graph.
One file for the data (in a different form from
fvecs
).One small metadata file.
This is subject to change in the future.
Reloading a Saved Index
To reload the index from file, use svs.Vamana.__init__()
with a svs.VectorDataLoader
for the second argument.
This informs the dispatch mechanisms that we’re loading an uncompressed data file from disk.
# We can reload an index from a previously saved set of files.
index = svs.Vamana(
os.path.join(test_data_dir, "example_config"),
svs.GraphLoader(os.path.join(test_data_dir, "example_graph")),
svs.VectorDataLoader(
os.path.join(test_data_dir, "example_data"), svs.DataType.float32
),
svs.DistanceType.L2,
num_threads = 4,
)
# We can rerun the queries to ensure everything works properly.
index.search_window_size = 30
I, D = index.search(queries, 10)
# Compare with the groundtruth.
recall = svs.k_recall_at(groundtruth, I, 10, 10)
print(f"Recall = {recall}")
assert(recall == 0.8288)
Performing queries is identical to before.
Using Vector Compression
The library has experimental support for performing online vector compression.
The second argument to svs.Vamana.__init__()
can be one of the compressed loaders (Loaders), which will compress an uncompressed dataset on the fly.
To see which loaders are applicable to which methods, study the signature in svs.vamana.__init__()
carefully.
Specifying the loader is all that is required to use vector compression. Note that vector compression is usually accompanied by an accuracy loss for the same search window size and may require increasing the window size to compensate.
index = svs.Vamana(
os.path.join(test_data_dir, "example_config"),
svs.GraphLoader(os.path.join(test_data_dir, "example_graph")),
compressed_loader,
# Optional keyword arguments
distance = svs.DistanceType.L2,
num_threads = 4
)
# Compare with the groundtruth..
index.search_window_size = 30
I, D = index.search(queries, 10)
recall = svs.k_recall_at(groundtruth, I, 10, 10)
print(f"Compressed recall: {recall}")
assert(recall == 0.8223)
Entire Example
This ends the example demonstrating the features of the svs.Vamana
index.
The entire executable code is shown below.
Please reach out with any questions.
# Import `unittest` to allow for automated testing.
import unittest
# [imports]
import os
import svs
# [imports]
DEBUG_MODE = False
def assert_equal(lhs, rhs, message: str = ""):
if DEBUG_MODE:
print(f"{message}: {lhs} == {rhs}")
else:
assert lhs == rhs, message
def run_test_float(index, queries, groundtruth):
expected = {
10: 0.5664,
20: 0.7397,
30: 0.8288,
40: 0.8837,
}
for window_size in range(10, 50, 10):
index.search_window_size = window_size
I, D = index.search(queries, 10)
recall = svs.k_recall_at(groundtruth, I, 10, 10)
assert_equal(
recall, expected[window_size], f"Standard Search Check ({window_size})"
)
def run_test_two_level4_8(index, queries, groundtruth):
expected = {
10: 0.5482,
20: 0.7294,
30: 0.8223,
40: 0.8756,
}
for window_size in range(10, 50, 10):
index.search_window_size = window_size
I, D = index.search(queries, 10)
recall = svs.k_recall_at(groundtruth, I, 10, 10)
assert_equal(
recall, expected[window_size], f"Compressed Search Check ({window_size})"
)
def run_test_build_two_level4_8(index, queries, groundtruth):
expected = {
10: 0.5484,
20: 0.7295,
30: 0.8221,
40: 0.8758,
}
for window_size in range(10, 50, 10):
index.search_window_size = window_size
I, D = index.search(queries, 10)
recall = svs.k_recall_at(groundtruth, I, 10, 10)
assert_equal(
recall, expected[window_size], f"Compressed Search Check ({window_size})"
)
# Shadow this as a global to make it available to the test-case clean-up.
test_data_dir = None
def run():
# ###
# Generating test data
# ###
# [generate-dataset]
# Create a test dataset.
# This will create a directory "example_data_vamana" and populate it with three
# entries:
# - data.fvecs: The test dataset.
# - queries.fvecs: The test queries.
# - groundtruth.ivecs: The groundtruth.
test_data_dir = "./example_data_vamana"
svs.generate_test_dataset(
10000, # Create 10000 vectors in the dataset.
1000, # Generate 1000 query vectors.
128, # Set the vector dimensionality to 128.
test_data_dir, # The directory where results will be generated.
data_seed = 1234, # Random number seed for reproducibility.
query_seed = 5678, # Random number seed for reproducibility.
num_threads = 4, # Number of threads to use.
distance = svs.DistanceType.L2, # The distance type to use.
)
# [generate-dataset]
# ###
# Building the index
# ###
# [build-parameters]
# Now, we can build a graph index over the data set.
parameters = svs.VamanaBuildParameters(
graph_max_degree = 64,
window_size = 128,
)
# [build-parameters]
# [build-index]
# Build the index.
index = svs.Vamana.build(
parameters,
svs.VectorDataLoader(
os.path.join(test_data_dir, "data.fvecs"), svs.DataType.float32
),
svs.DistanceType.L2,
num_threads = 4,
)
# [build-index]
# [build-index-fromNumpyArray]
# Build the index.
data = svs.read_vecs(os.path.join(test_data_dir, "data.fvecs"))
index = svs.Vamana.build(
parameters,
data,
svs.DistanceType.L2,
num_threads = 4,
)
# [build-index-fromNumpyArray]
# ###
# Searching the index
# ###
# [load-aux]
# Load the queries and ground truth.
queries = svs.read_vecs(os.path.join(test_data_dir, "queries.fvecs"))
groundtruth = svs.read_vecs(os.path.join(test_data_dir, "groundtruth.ivecs"))
# [load-aux]
# [perform-queries]
# Set the search window size of the index and perform queries.
index.search_window_size = 30
I, D = index.search(queries, 10)
# Compare with the groundtruth.
recall = svs.k_recall_at(groundtruth, I, 10, 10)
print(f"Recall = {recall}")
assert(recall == 0.8288)
# [perform-queries]
# [search-window-size]
# We can vary the search window size to demonstrate the trade off in accuracy.
for window_size in range(10, 50, 10):
index.search_window_size = window_size
I, D = index.search(queries, 10)
recall = svs.k_recall_at(groundtruth, I, 10, 10)
print(f"Window size = {window_size}, Recall = {recall}")
# [search-window-size]
##### Begin Test
run_test_float(index, queries, groundtruth)
##### End Test
# ###
# Saving the index
# ###
# [saving-results]
# Finally, we can save the results.
index.save(
os.path.join(test_data_dir, "example_config"),
os.path.join(test_data_dir, "example_graph"),
os.path.join(test_data_dir, "example_data"),
)
# [saving-results]
# ###
# Reloading a saved index
# ###
# [loading]
# We can reload an index from a previously saved set of files.
index = svs.Vamana(
os.path.join(test_data_dir, "example_config"),
svs.GraphLoader(os.path.join(test_data_dir, "example_graph")),
svs.VectorDataLoader(
os.path.join(test_data_dir, "example_data"), svs.DataType.float32
),
svs.DistanceType.L2,
num_threads = 4,
)
# We can rerun the queries to ensure everything works properly.
index.search_window_size = 30
I, D = index.search(queries, 10)
# Compare with the groundtruth.
recall = svs.k_recall_at(groundtruth, I, 10, 10)
print(f"Recall = {recall}")
assert(recall == 0.8288)
# [loading]
##### Begin Test
run_test_float(index, queries, groundtruth)
##### End Test
# [only-loading]
# We can reload an index from a previously saved set of files.
index = svs.Vamana(
os.path.join(test_data_dir, "example_config"),
svs.GraphLoader(os.path.join(test_data_dir, "example_graph")),
svs.VectorDataLoader(
os.path.join(test_data_dir, "example_data"), svs.DataType.float32
),
svs.DistanceType.L2,
num_threads = 4,
)
# [only-loading]
# [runtime-nthreads]
index.num_threads = 4
# [runtime-nthreads]
# ###
# Search using vector compression
# ###
# [search-compressed-loader]
data_loader = svs.VectorDataLoader(
os.path.join(test_data_dir, "example_data"), # Uncompressed data
svs.DataType.float32,
dims = 128 # Passing dimensionality is optional
)
B1 = 4 # Number of bits for the first level LVQ quantization
B2 = 8 # Number of bits for the residuals quantization
padding = 32
strategy = svs.LVQStrategy.Turbo
compressed_loader = svs.LVQLoader(data_loader,
primary=B1,
residual=B2,
strategy=strategy, # Passing the strategy is optional.
padding=padding # Passing padding is optional.
)
# [search-compressed-loader]
# [search-compressed]
index = svs.Vamana(
os.path.join(test_data_dir, "example_config"),
svs.GraphLoader(os.path.join(test_data_dir, "example_graph")),
compressed_loader,
# Optional keyword arguments
distance = svs.DistanceType.L2,
num_threads = 4
)
# Compare with the groundtruth..
index.search_window_size = 30
I, D = index.search(queries, 10)
recall = svs.k_recall_at(groundtruth, I, 10, 10)
print(f"Compressed recall: {recall}")
assert(recall == 0.8223)
# [search-compressed]
##### Begin Test
run_test_two_level4_8(index, queries, groundtruth)
##### End Test
# [build-index-compressed]
# Build the index.
index = svs.Vamana.build(
parameters,
compressed_loader,
svs.DistanceType.L2,
num_threads = 4
)
# [build-index-compressed]
# 1. Building Uncompressed
# 2. Loading Uncompressed
# 3. Loading with a recompressor
# We can rerun the queries to ensure everything works properly.
index.search_window_size = 30
I, D = index.search(queries, 10)
# Compare with the groundtruth.
recall = svs.k_recall_at(groundtruth, I, 10, 10)
print(f"Recall = {recall}")
assert(recall == 0.8221)
# [loading]
##### Begin Test
run_test_build_two_level4_8(index, queries, groundtruth)
##### End Test
#####
##### Main Executable
#####
if __name__ == "__main__":
run()
#####
##### As a unit test.
#####
class VamanaExampleTestCase(unittest.TestCase):
def tearDown(self):
if test_data_dir is not None:
print(f"Removing temporary directory {test_data_dir}")
os.rmdir(test_data_dir)
def test_all(self):
run()