IVF-PQ#

The IVF-PQ method is an ANN algorithm. Like IVF-Flat, IVF-PQ 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#
typedef struct cuvsIvfPqIndexParams *cuvsIvfPqIndexParams_t#
cuvsError_t cuvsIvfPqIndexParamsCreate(cuvsIvfPqIndexParams_t *index_params)#

Allocate IVF-PQ 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)#

De-allocate IVF-PQ Index params.

Parameters:

index_params – [in]

Returns:

cuvsError_t

struct cuvsIvfPqIndexParams#
#include <ivf_pq.h>

Supplemental parameters to build IVF-PQ 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 calling build.

  • false means build only trains the underlying model (e.g. quantizer or clustering), but the index is left empty; you’d need to call extend 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 of pq_dim, a random rotation is always applied to the input data and queries to transform the working space from dim to rot_dim, which may be slightly larger than the original space and and is a multiple of pq_dim (rot_dim % pq_dim == 0). However, this transform is not necessary when dim is multiple of pq_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. When force_random_rotation == true, a random orthogonal transform matrix is generated regardless of the values of dim and pq_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 to extend (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.

Index search parameters#

typedef struct cuvsIvfPqSearchParams *cuvsIvfPqSearchParams_t#
cuvsError_t cuvsIvfPqSearchParamsCreate(cuvsIvfPqSearchParams_t *params)#

Allocate IVF-PQ search params, and populate with default values.

Parameters:

params – [in] cuvsIvfPqSearchParams_t to allocate

Returns:

cuvsError_t

cuvsError_t cuvsIvfPqSearchParamsDestroy(cuvsIvfPqSearchParams_t params)#

De-allocate IVF-PQ search params.

Parameters:

params – [in]

Returns:

cuvsError_t

struct cuvsIvfPqSearchParams#
#include <ivf_pq.h>

Supplemental parameters to search IVF-PQ 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 low-precision 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 low-precision 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 low-level tuning parameter that can have drastic negative effects on the search performance if tweaked incorrectly.

Index#

typedef cuvsIvfPqIndex *cuvsIvfPqIndex_t#
cuvsError_t cuvsIvfPqIndexCreate(cuvsIvfPqIndex_t *index)#

Allocate IVF-PQ index.

Parameters:

index – [in] cuvsIvfPqIndex_t to allocate

Returns:

cuvsError_t

cuvsError_t cuvsIvfPqIndexDestroy(cuvsIvfPqIndex_t index)#

De-allocate IVF-PQ index.

Parameters:

index – [in] cuvsIvfPqIndex_t to de-allocate

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 IVF-PQ index with a DLManagedTensor which has underlying DLDeviceType equal to kDLCUDA, kDLCUDAHost, kDLCUDAManaged, or kDLCPU. Also, acceptable underlying types are:

  1. kDLDataType.code == kDLFloat and kDLDataType.bits = 32

  2. kDLDataType.code == kDLInt and kDLDataType.bits = 8

  3. kDLDataType.code == kDLUInt and kDLDataType.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 IVF-PQ index
cuvsIvfPqIndex_t index;
cuvsError_t index_create_status = cuvsIvfPqIndexCreate(&index);

// Build the IVF-PQ Index
cuvsError_t build_status = cuvsIvfPqBuild(res, index_params, &dataset, index);

// de-allocate `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 IVF-PQ index

  • dataset – [in] DLManagedTensor* training dataset

  • index – [out] cuvsIvfPqIndex_t Newly built IVF-PQ index

Returns:

cuvsError_t