#include <IndexIVF_HNSW.h>
Public Types | |
typedef uint32_t | idx_t |
all indices are this type | |
Public Member Functions | |
IndexIVF_HNSW (size_t dim, size_t ncentroids, size_t bytes_per_code, size_t nbits_per_idx) | |
void | build_quantizer (const char *path_data, const char *path_info, const char *path_edges, size_t M=16, size_t efConstruction=500) |
void | assign (size_t n, const float *x, idx_t *labels, size_t k=1) |
virtual void | search (size_t k, const float *x, float *distances, long *labels) |
virtual void | add_batch (size_t n, const float *x, const idx_t *xids, const idx_t *precomputed_idx=nullptr) |
virtual void | train_pq (size_t n, const float *x) |
virtual void | write (const char *path) |
Write index to the path. | |
virtual void | read (const char *path) |
Read index from the path. | |
void | compute_centroid_norms () |
Compute norms of the HNSW vertices. | |
void | rotate_quantizer () |
For correct search using OPQ encoding rotate points in the coarse quantizer. | |
Public Attributes | |
size_t | d |
Vector dimension. | |
size_t | nc |
Number of centroids. | |
size_t | code_size |
Code size per vector in bytes. | |
hnswlib::HierarchicalNSW * | quantizer |
Quantizer that maps vectors to inverted lists (HNSW [Y.Malkov]) | |
faiss::ProductQuantizer * | pq |
Produces the residual codes. | |
faiss::ProductQuantizer * | norm_pq |
Produces the norm codes of reconstructed base vectors. | |
faiss::LinearTransform * | opq_matrix |
Rotation matrix for OPQ encoding. | |
bool | do_opq |
Turn on/off OPQ encoding. | |
size_t | nprobe |
Number of probes at search time. | |
size_t | max_codes |
Max number of codes to visit to do a query. | |
std::vector< std::vector< idx_t > > | ids |
Inverted lists for indexes. | |
std::vector< std::vector < uint8_t > > | codes |
PQ codes of residuals. | |
std::vector< std::vector < uint8_t > > | norm_codes |
PQ codes of norms of reconstructed base vectors. | |
Protected Member Functions | |
float | pq_L2sqr (const uint8_t *code) |
L2 sqr distance function for PQ codes. | |
Protected Attributes | |
std::vector< float > | norms |
L2 square norms of reconstructed base vectors. | |
std::vector< float > | centroid_norms |
L2 square norms of coarse centroids. | |
std::vector< float > | precomputed_table |
Size pq.M * pq.ksub. | |
Index based on a inverted file (IVF) with Product Quantizer encoding.
In the inverted file, the quantizer (an HNSW instance) provides a quantization index for each vector to be added. The quantization index maps to a list (aka inverted list or posting list), where the id of the vector is then stored.
At search time, the vector to be searched is also quantized, and only the list corresponding to the quantization index is searched. This speeds up the search by making it non-exhaustive. This can be relaxed using multi-probe search: a few (nprobe) quantization indices are selected and several inverted lists are visited.
Supports HNSW quantizer construction, PQ training, adding vertices, serialization and searching.
Each residual vector is encoded as a product quantizer code.
Currently only asymmetric queries are supported: database-to-database queries are not implemented.
|
virtual |
Add n vectors of dimension d to the index.
n | number of base vectors in a batch |
x | base vectors to add, size n * d |
xids | ids to store for the vectors (size n) |
precomputed_idx | if non-null, assigned idxs to store for the vectors (size n) |
void ivfhnsw::IndexIVF_HNSW::assign | ( | size_t | n, |
const float * | x, | ||
idx_t * | labels, | ||
size_t | k = 1 |
||
) |
Return the indices of the k HNSW vertices closest to the query x.
n | number of input vectors |
x | query vectors, size n * d |
labels | output labels of the nearest neighbours, size n * k |
k | number of the closest HNSW vertices to the query x |
void ivfhnsw::IndexIVF_HNSW::build_quantizer | ( | const char * | path_data, |
const char * | path_info, | ||
const char * | path_edges, | ||
size_t | M = 16 , |
||
size_t | efConstruction = 500 |
||
) |
Construct from stretch or load the existing quantizer (HNSW) instance
if all files exist, quantizer will be loaded, else HNSW will be constructed
path_data | path to input vectors |
path_info | path to parameters for HNSW |
path_edges | path to edges for HNSW |
M | min number of edges per point, default: 16 |
efConstruction | max number of candidate vertices in queue to observe, default: 500 |
There has been removed parallel HNSW construction in order to make internal centroid ids equal to external ones. Construction time is still acceptable: ~5 minutes for 1 million 96-d vectors on Intel Xeon E5-2650 V2 2.60GHz.
|
virtual |
Query n vectors of dimension d to the index.
Return at most k vectors. If there are not enough results for a query, the result array is padded with -1s.
k | number of the closest vertices to search |
x | query vectors, size n * d |
distances | output pairwise distances, size n * k |
labels | output labels of the nearest neighbours, size n * k |
Search procedure
During IVF-HNSW-PQ search we compute
d = || x - y_C - y_R ||^2
where x is the query vector, y_C the coarse centroid, y_R the refined PQ centroid. The expression can be decomposed as:
d = || x - y_C ||^2 - || y_C ||^2 + || y_C + y_R ||^2 - 2 * (x|y_R)
term 1 term 2 term 3
We use the following decomposition:
Norms of centroids are precomputed and saved without compression, as their memory consumption is negligible. If it is necessary, the norms can be added to the term 3 and compressed to byte together. We do not think that it will lead to considerable decrease in accuracy.
Since y_R defined by a product quantizer, it is split across sub-vectors and stored separately for each subvector.
Reimplemented in ivfhnsw::IndexIVF_HNSW_Grouping.
|
virtual |
Train product quantizers
n | number of training vectors of dimension d |
x | learn vectors, size n * d |
Reimplemented in ivfhnsw::IndexIVF_HNSW_Grouping.