IVFPQ#
The IVFPQ method is an ANN algorithm. Like IVFFlat, IVFPQ splits the points into a number of clusters (also specified by a parameter called n_lists) and searches the closest clusters to compute the nearest neighbors (also specified by a parameter called n_probes), but it shrinks the sizes of the vectors using a technique called product quantization.
#include <raft/neighbors/ivf_pq.h>
Index build parameters#

enum codebook_gen#
A type for specifying how PQ codebooks are created.
Values:

enumerator PER_SUBSPACE#

enumerator PER_CLUSTER#

enumerator PER_SUBSPACE#

typedef struct cuvsIvfPqIndexParams *cuvsIvfPqIndexParams_t#

cuvsError_t cuvsIvfPqIndexParamsCreate(cuvsIvfPqIndexParams_t *index_params)#
Allocate IVFPQ Index params, and populate with default values.
 Parameters:
index_params – [in] cuvsIvfPqIndexParams_t to allocate
 Returns:
cuvsError_t

cuvsError_t cuvsIvfPqIndexParamsDestroy(cuvsIvfPqIndexParams_t index_params)#
Deallocate IVFPQ Index params.
 Parameters:
index_params – [in]
 Returns:
cuvsError_t

struct cuvsIvfPqIndexParams#
 #include <ivf_pq.h>
Supplemental parameters to build IVFPQ Index.
Public Members

cuvsDistanceType metric#
Distance type.

float metric_arg#
The argument used by some distance metrics.

bool add_data_on_build#
Whether to add the dataset content to the index, i.e.:
true
means the index is filled with the dataset vectors and ready to search after callingbuild
.false
meansbuild
only trains the underlying model (e.g. quantizer or clustering), but the index is left empty; you’d need to callextend
on the index afterwards to populate it.

uint32_t n_lists#
The number of inverted lists (clusters)
Hint: the number of vectors per cluster (
n_rows/n_lists
) should be approximately 1,000 to 10,000.

uint32_t kmeans_n_iters#
The number of iterations searching for kmeans centers (index building).

double kmeans_trainset_fraction#
The fraction of data to use during iterative kmeans building.

uint32_t pq_bits#
The bit length of the vector element after compression by PQ.
Possible values: [4, 5, 6, 7, 8].
Hint: the smaller the ‘pq_bits’, the smaller the index size and the better the search performance, but the lower the recall.

uint32_t pq_dim#
The dimensionality of the vector after compression by PQ. When zero, an optimal value is selected using a heuristic.
NB:
pq_dim * pq_bits
must be a multiple of 8.Hint: a smaller ‘pq_dim’ results in a smaller index size and better search performance, but lower recall. If ‘pq_bits’ is 8, ‘pq_dim’ can be set to any number, but multiple of 8 are desirable for good performance. If ‘pq_bits’ is not 8, ‘pq_dim’ should be a multiple of 8. For good performance, it is desirable that ‘pq_dim’ is a multiple of 32. Ideally, ‘pq_dim’ should be also a divisor of the dataset dim.

enum codebook_gen codebook_kind#
How PQ codebooks are created.

bool force_random_rotation#
Apply a random rotation matrix on the input data and queries even if
dim % pq_dim == 0
.Note: if
dim
is not multiple ofpq_dim
, a random rotation is always applied to the input data and queries to transform the working space fromdim
torot_dim
, which may be slightly larger than the original space and and is a multiple ofpq_dim
(rot_dim % pq_dim == 0
). However, this transform is not necessary whendim
is multiple ofpq_dim
(dim == rot_dim
, hence no need in adding “extra” data columns / features).By default, if
dim == rot_dim
, the rotation transform is initialized with the identity matrix. Whenforce_random_rotation == true
, a random orthogonal transform matrix is generated regardless of the values ofdim
andpq_dim
.

bool conservative_memory_allocation#
By default, the algorithm allocates more space than necessary for individual clusters (
list_data
). This allows to amortize the cost of memory allocation and reduce the number of data copies during repeated calls toextend
(extending the database).The alternative is the conservative allocation behavior; when enabled, the algorithm always allocates the minimum amount of memory required to store the given number of records. Set this flag to
true
if you prefer to use as little GPU memory for the database as possible.

uint32_t max_train_points_per_pq_code#
The max number of data points to use per PQ code during PQ codebook training. Using more data points per PQ code may increase the quality of PQ codebook but may also increase the build time. The parameter is applied to both PQ codebook generation methods, i.e., PER_SUBSPACE and PER_CLUSTER. In both cases, we will use
pq_book_size * max_train_points_per_pq_code
training points to train each codebook.

cuvsDistanceType metric#
Index search parameters#

typedef struct cuvsIvfPqSearchParams *cuvsIvfPqSearchParams_t#

cuvsError_t cuvsIvfPqSearchParamsCreate(cuvsIvfPqSearchParams_t *params)#
Allocate IVFPQ search params, and populate with default values.
 Parameters:
params – [in] cuvsIvfPqSearchParams_t to allocate
 Returns:
cuvsError_t

cuvsError_t cuvsIvfPqSearchParamsDestroy(cuvsIvfPqSearchParams_t params)#
Deallocate IVFPQ search params.
 Parameters:
params – [in]
 Returns:
cuvsError_t

struct cuvsIvfPqSearchParams#
 #include <ivf_pq.h>
Supplemental parameters to search IVFPQ index.
Public Members

uint32_t n_probes#
The number of clusters to search.

cudaDataType_t lut_dtype#
Data type of look up table to be created dynamically at search time.
Possible values: [CUDA_R_32F, CUDA_R_16F, CUDA_R_8U]
The use of lowprecision types reduces the amount of shared memory required at search time, so fast shared memory kernels can be used even for datasets with large dimansionality. Note that the recall is slightly degraded when lowprecision type is selected.

cudaDataType_t internal_distance_dtype#
Storage data type for distance/similarity computed at search time.
Possible values: [CUDA_R_16F, CUDA_R_32F]
If the performance limiter at search time is device memory access, selecting FP16 will improve performance slightly.

double preferred_shmem_carveout#
Preferred fraction of SM’s unified memory / L1 cache to be used as shared memory.
Possible values: [0.0  1.0] as a fraction of the
sharedMemPerMultiprocessor
.One wants to increase the carveout to make sure a good GPU occupancy for the main search kernel, but not to keep it too high to leave some memory to be used as L1 cache. Note, this value is interpreted only as a hint. Moreover, a GPU usually allows only a fixed set of cache configurations, so the provided value is rounded up to the nearest configuration. Refer to the NVIDIA tuning guide for the target GPU architecture.
Note, this is a lowlevel tuning parameter that can have drastic negative effects on the search performance if tweaked incorrectly.

uint32_t n_probes#
Index#

typedef cuvsIvfPqIndex *cuvsIvfPqIndex_t#

cuvsError_t cuvsIvfPqIndexCreate(cuvsIvfPqIndex_t *index)#
Allocate IVFPQ index.
 Parameters:
index – [in] cuvsIvfPqIndex_t to allocate
 Returns:
cuvsError_t

cuvsError_t cuvsIvfPqIndexDestroy(cuvsIvfPqIndex_t index)#
Deallocate IVFPQ index.
 Parameters:
index – [in] cuvsIvfPqIndex_t to deallocate

struct cuvsIvfPqIndex#
 #include <ivf_pq.h>
Struct to hold address of cuvs::neighbors::ivf_pq::index and its active trained dtype.
Index build#

cuvsError_t cuvsIvfPqBuild(cuvsResources_t res, cuvsIvfPqIndexParams_t params, DLManagedTensor *dataset, cuvsIvfPqIndex_t index)#
Build a IVFPQ index with a
DLManagedTensor
which has underlyingDLDeviceType
equal tokDLCUDA
,kDLCUDAHost
,kDLCUDAManaged
, orkDLCPU
. Also, acceptable underlying types are:kDLDataType.code == kDLFloat
andkDLDataType.bits = 32
kDLDataType.code == kDLInt
andkDLDataType.bits = 8
kDLDataType.code == kDLUInt
andkDLDataType.bits = 8
#include <cuvs/core/c_api.h> #include <cuvs/neighbors/ivf_pq.h> // Create cuvsResources_t cuvsResources_t res; cuvsError_t res_create_status = cuvsResourcesCreate(&res); // Assume a populated `DLManagedTensor` type here DLManagedTensor dataset; // Create default index params cuvsIvfPqIndexParams_t index_params; cuvsError_t params_create_status = cuvsIvfPqIndexParamsCreate(&index_params); // Create IVFPQ index cuvsIvfPqIndex_t index; cuvsError_t index_create_status = cuvsIvfPqIndexCreate(&index); // Build the IVFPQ Index cuvsError_t build_status = cuvsIvfPqBuild(res, index_params, &dataset, index); // deallocate `index_params`, `index` and `res` cuvsError_t params_destroy_status = cuvsIvfPqIndexParamsDestroy(index_params); cuvsError_t index_destroy_status = cuvsIvfPqIndexDestroy(index); cuvsError_t res_destroy_status = cuvsResourcesDestroy(res);
 Parameters:
res – [in] cuvsResources_t opaque C handle
params – [in] cuvsIvfPqIndexParams_t used to build IVFPQ index
dataset – [in] DLManagedTensor* training dataset
index – [out] cuvsIvfPqIndex_t Newly built IVFPQ index
 Returns:
cuvsError_t
Index search#

cuvsError_t cuvsIvfPqSearch(cuvsResources_t res, cuvsIvfPqSearchParams_t search_params, cuvsIvfPqIndex_t index, DLManagedTensor *queries, DLManagedTensor *neighbors, DLManagedTensor *distances)#
Search a IVFPQ index with a
DLManagedTensor
which has underlyingDLDeviceType
equal tokDLCUDA
,kDLCUDAHost
,kDLCUDAManaged
. It is also important to note that the IVFPQ Index must have been built with the same type ofqueries
, such thatindex.dtype.code == queries.dl_tensor.dtype.code
Types for input are:queries
:kDLDataType.code == kDLFloat
andkDLDataType.bits = 32
neighbors
:kDLDataType.code == kDLUInt
andkDLDataType.bits = 32
distances
:kDLDataType.code == kDLFloat
andkDLDataType.bits = 32
#include <cuvs/core/c_api.h> #include <cuvs/neighbors/ivf_pq.h> // Create cuvsResources_t cuvsResources_t res; cuvsError_t res_create_status = cuvsResourcesCreate(&res); // Assume a populated `DLManagedTensor` type here DLManagedTensor dataset; DLManagedTensor queries; DLManagedTensor neighbors; // Create default search params cuvsIvfPqSearchParams_t search_params; cuvsError_t params_create_status = cuvsIvfPqSearchParamsCreate(&search_params); // Search the `index` built using `cuvsIvfPqBuild` cuvsError_t search_status = cuvsIvfPqSearch(res, search_params, index, &queries, &neighbors, &distances); // deallocate `search_params` and `res` cuvsError_t params_destroy_status = cuvsIvfPqSearchParamsDestroy(search_params); cuvsError_t res_destroy_status = cuvsResourcesDestroy(res);
 Parameters:
res – [in] cuvsResources_t opaque C handle
search_params – [in] cuvsIvfPqSearchParams_t used to search IVFPQ index
index – [in] cuvsIvfPqIndex which has been returned by
cuvsIvfPqBuild
queries – [in] DLManagedTensor* queries dataset to search
neighbors – [out] DLManagedTensor* output
k
neighbors for queriesdistances – [out] DLManagedTensor* output
k
distances for queries