IVF-Flat#

The IVF-Flat method is an ANN algorithm. It uses an inverted file index (IVF) with unmodified (that is, flat) vectors. This algorithm provides simple knobs to reduce the overall search space and to trade-off accuracy for speed.

#include <raft/neighbors/ivf_flat.h>

Index build parameters#

typedef struct cuvsIvfFlatIndexParams *cuvsIvfFlatIndexParams_t#
cuvsError_t cuvsIvfFlatIndexParamsCreate(cuvsIvfFlatIndexParams_t *index_params)#

Allocate IVF-Flat Index params, and populate with default values.

Parameters:

index_params – [in] cuvsIvfFlatIndexParams_t to allocate

Returns:

cuvsError_t

cuvsError_t cuvsIvfFlatIndexParamsDestroy(cuvsIvfFlatIndexParams_t index_params)#

De-allocate IVF-Flat Index params.

Parameters:

index_params – [in]

Returns:

cuvsError_t

struct cuvsIvfFlatIndexParams#
#include <ivf_flat.h>

Supplemental parameters to build IVF-Flat 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)

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.

bool adaptive_centers#

By default (adaptive_centers = false), the cluster centers are trained in ivf_flat::build, and never modified in ivf_flat::extend. As a result, you may need to retrain the index from scratch after invoking (ivf_flat::extend) a few times with new data, the distribution of which is no longer representative of the original training set.

The alternative behavior (adaptive_centers = true) is to update the cluster centers for new data when it is added. In this case, index.centers() are always exactly the centroids of the data in the corresponding clusters. The drawback of this behavior is that the centroids depend on the order of adding new data (through the classification of the added data); that is, index.centers() “drift” together with the changing distribution of the newly added data.

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.

Index search parameters#

typedef struct cuvsIvfFlatSearchParams *cuvsIvfFlatSearchParams_t#
cuvsError_t cuvsIvfFlatSearchParamsCreate(cuvsIvfFlatSearchParams_t *params)#

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

Parameters:

params – [in] cuvsIvfFlatSearchParams_t to allocate

Returns:

cuvsError_t

cuvsError_t cuvsIvfFlatSearchParamsDestroy(cuvsIvfFlatSearchParams_t params)#

De-allocate IVF-Flat search params.

Parameters:

params – [in]

Returns:

cuvsError_t

struct cuvsIvfFlatSearchParams#
#include <ivf_flat.h>

Supplemental parameters to search IVF-Flat index.

Public Members

uint32_t n_probes#

The number of clusters to search.

Index#

typedef cuvsIvfFlatIndex *cuvsIvfFlatIndex_t#
cuvsError_t cuvsIvfFlatIndexCreate(cuvsIvfFlatIndex_t *index)#

Allocate IVF-Flat index.

Parameters:

index – [in] cuvsIvfFlatIndex_t to allocate

Returns:

cuvsError_t

cuvsError_t cuvsIvfFlatIndexDestroy(cuvsIvfFlatIndex_t index)#

De-allocate IVF-Flat index.

Parameters:

index – [in] cuvsIvfFlatIndex_t to de-allocate

struct cuvsIvfFlatIndex#
#include <ivf_flat.h>

Struct to hold address of cuvs::neighbors::ivf_flat::index and its active trained dtype.

Index build#

cuvsError_t cuvsIvfFlatBuild(cuvsResources_t res, cuvsIvfFlatIndexParams_t index_params, DLManagedTensor *dataset, cuvsIvfFlatIndex_t index)#

Build a IVF-Flat 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_flat.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
cuvsIvfFlatIndexParams_t index_params;
cuvsError_t params_create_status = cuvsIvfFlatIndexParamsCreate(&index_params);

// Create IVF-Flat index
cuvsIvfFlatIndex_t index;
cuvsError_t index_create_status = cuvsIvfFlatIndexCreate(&index);

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

// de-allocate `index_params`, `index` and `res`
cuvsError_t params_destroy_status = cuvsIvfFlatIndexParamsDestroy(index_params);
cuvsError_t index_destroy_status = cuvsIvfFlatIndexDestroy(index);
cuvsError_t res_destroy_status = cuvsResourcesDestroy(res);
Parameters:

  • res – [in] cuvsResources_t opaque C handle

  • index_params – [in] cuvsIvfFlatIndexParams_t used to build IVF-Flat index

  • dataset – [in] DLManagedTensor* training dataset

  • index – [out] cuvsIvfFlatIndex_t Newly built IVF-Flat index

Returns:

cuvsError_t