File IndexHNSW.h

namespace faiss

Copyright (c) Facebook, Inc. and its affiliates.

This source code is licensed under the MIT license found in the LICENSE file in the root directory of this source tree.

Copyright (c) Facebook, Inc. and its affiliates.

This source code is licensed under the MIT license found in the LICENSE file in the root directory of this source tree. Implementation of k-means clustering with many variants.

Copyright (c) Facebook, Inc. and its affiliates.

This source code is licensed under the MIT license found in the LICENSE file in the root directory of this source tree. IDSelector is intended to define a subset of vectors to handle (for removal or as subset to search)

Copyright (c) Facebook, Inc. and its affiliates.

This source code is licensed under the MIT license found in the LICENSE file in the root directory of this source tree. PQ4 SIMD packing and accumulation functions

The basic kernel accumulates nq query vectors with bbs = nb * 2 * 16 vectors and produces an output matrix for that. It is interesting for nq * nb <= 4, otherwise register spilling becomes too large.

The implementation of these functions is spread over 3 cpp files to reduce parallel compile times. Templates are instantiated explicitly.

Copyright (c) Facebook, Inc. and its affiliates.

This source code is licensed under the MIT license found in the LICENSE file in the root directory of this source tree. This file contains callbacks for kernels that compute distances.

The SIMDResultHandler object is intended to be templated and inlined. Methods:

• handle(): called when 32 distances are computed and provided in two simd16uint16. (q, b) indicate which entry it is in the block.

• set_block_origin(): set the sub-matrix that is being computed

Throughout the library, vectors are provided as float * pointers. Most algorithms can be optimized when several vectors are processed (added/searched) together in a batch. In this case, they are passed in as a matrix. When n vectors of size d are provided as float * x, component j of vector i is

x[ i * d + j ]

where 0 <= i < n and 0 <= j < d. In other words, matrices are always compact. When specifying the size of the matrix, we call it an n*d matrix, which implies a row-major storage.

Copyright (c) Facebook, Inc. and its affiliates.

This source code is licensed under the MIT license found in the LICENSE file in the root directory of this source tree. I/O functions can read/write to a filename, a file handle or to an object that abstracts the medium.

The read functions return objects that should be deallocated with delete. All references within these objectes are owned by the object.

Copyright (c) Facebook, Inc. and its affiliates.

This source code is licensed under the MIT license found in the LICENSE file in the root directory of this source tree. Definition of inverted lists + a few common classes that implement the interface.

Copyright (c) Facebook, Inc. and its affiliates.

This source code is licensed under the MIT license found in the LICENSE file in the root directory of this source tree. Since IVF (inverted file) indexes are of so much use for large-scale use cases, we group a few functions related to them in this small library. Most functions work both on IndexIVFs and IndexIVFs embedded within an IndexPreTransform.

Copyright (c) Facebook, Inc. and its affiliates.

This source code is licensed under the MIT license found in the LICENSE file in the root directory of this source tree. In this file are the implementations of extra metrics beyond L2 and inner product

Copyright (c) Facebook, Inc. and its affiliates.

This source code is licensed under the MIT license found in the LICENSE file in the root directory of this source tree. Defines a few objects that apply transformations to a set of vectors Often these are pre-processing steps.

struct ReconstructFromNeighbors

Public Types

typedef HNSW::storage_idx_t storage_idx_t

Public Functions

explicit ReconstructFromNeighbors(const IndexHNSW &index, size_t k = 256, size_t nsq = 1)

void add_codes(size_t n, const float *x)

codes must be added in the correct order and the IndexHNSW must be populated and sorted

size_t compute_distances(size_t n, const idx_t *shortlist, const float *query, float *distances) const

void estimate_code(const float *x, storage_idx_t i, uint8_t *code) const

called by add_codes

void reconstruct(storage_idx_t i, float *x, float *tmp) const

called by compute_distances

void reconstruct_n(storage_idx_t n0, storage_idx_t ni, float *x) const

void get_neighbor_table(storage_idx_t i, float *out) const

get the M+1 -by-d table for neighbor coordinates for vector i

Public Members

const IndexHNSW &index

size_t M

size_t k

size_t nsq

size_t code_size

int k_reorder

std::vector<float> codebook

std::vector<uint8_t> codes

size_t ntotal

size_t d

size_t dsub

struct IndexHNSW : public faiss::Index

#include <IndexHNSW.h>

The HNSW index is a normal random-access index with a HNSW link structure built on top

Subclassed by faiss::IndexHNSW2Level, faiss::IndexHNSWFlat, faiss::IndexHNSWPQ, faiss::IndexHNSWSQ

Public Types

typedef HNSW::storage_idx_t storage_idx_t

Public Functions

explicit IndexHNSW(int d = 0, int M = 32, MetricType metric = METRIC_L2)

explicit IndexHNSW(Index *storage, int M = 32)

~IndexHNSW() override

virtual void add(idx_t n, const float *x) override

Add n vectors of dimension d to the index.

Vectors are implicitly assigned labels ntotal .. ntotal + n - 1 This function slices the input vectors in chunks smaller than blocksize_add and calls add_core.

Parameters:

x – input matrix, size n * d

virtual void train(idx_t n, const float *x) override

Trains the storage if needed.

virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const override

entry point for search

virtual void reconstruct(idx_t key, float *recons) const override

Reconstruct a stored vector (or an approximation if lossy coding)

this function may not be defined for some indexes

Parameters:

• key – id of the vector to reconstruct

• recons – reconstucted vector (size d)

virtual void reset() override

removes all elements from the database.

void shrink_level_0_neighbors(int size)

void search_level_0(idx_t n, const float *x, idx_t k, const storage_idx_t *nearest, const float *nearest_d, float *distances, idx_t *labels, int nprobe = 1, int search_type = 1) const

Perform search only on level 0, given the starting points for each vertex.

Parameters:

search_type – 1:perform one search per nprobe, 2: enqueue all entry points

void init_level_0_from_knngraph(int k, const float *D, const idx_t *I)

alternative graph building

void init_level_0_from_entry_points(int npt, const storage_idx_t *points, const storage_idx_t *nearests)

alternative graph building

void reorder_links()

void link_singletons()

void permute_entries(const idx_t *perm)

Public Members

HNSW hnsw

bool own_fields = false

Index *storage = nullptr

ReconstructFromNeighbors *reconstruct_from_neighbors = nullptr

struct IndexHNSWFlat : public faiss::IndexHNSW

#include <IndexHNSW.h>

Flat index topped with with a HNSW structure to access elements more efficiently.

Public Types

typedef HNSW::storage_idx_t storage_idx_t

Public Functions

IndexHNSWFlat()

IndexHNSWFlat(int d, int M, MetricType metric = METRIC_L2)

virtual void add(idx_t n, const float *x) override

Add n vectors of dimension d to the index.

Vectors are implicitly assigned labels ntotal .. ntotal + n - 1 This function slices the input vectors in chunks smaller than blocksize_add and calls add_core.

Parameters:

x – input matrix, size n * d

virtual void train(idx_t n, const float *x) override

Trains the storage if needed.

virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const override

entry point for search

virtual void reconstruct(idx_t key, float *recons) const override

Reconstruct a stored vector (or an approximation if lossy coding)

this function may not be defined for some indexes

Parameters:

• key – id of the vector to reconstruct

• recons – reconstucted vector (size d)

virtual void reset() override

removes all elements from the database.

void shrink_level_0_neighbors(int size)

void search_level_0(idx_t n, const float *x, idx_t k, const storage_idx_t *nearest, const float *nearest_d, float *distances, idx_t *labels, int nprobe = 1, int search_type = 1) const

Perform search only on level 0, given the starting points for each vertex.

Parameters:

search_type – 1:perform one search per nprobe, 2: enqueue all entry points

void init_level_0_from_knngraph(int k, const float *D, const idx_t *I)

alternative graph building

void init_level_0_from_entry_points(int npt, const storage_idx_t *points, const storage_idx_t *nearests)

alternative graph building

void reorder_links()

void link_singletons()

void permute_entries(const idx_t *perm)

Public Members

HNSW hnsw

bool own_fields = false

Index *storage = nullptr

ReconstructFromNeighbors *reconstruct_from_neighbors = nullptr

struct IndexHNSWPQ : public faiss::IndexHNSW

#include <IndexHNSW.h>

PQ index topped with with a HNSW structure to access elements more efficiently.

Public Types

typedef HNSW::storage_idx_t storage_idx_t

Public Functions

IndexHNSWPQ()

IndexHNSWPQ(int d, int pq_m, int M, int pq_nbits = 8)

virtual void train(idx_t n, const float *x) override

Trains the storage if needed.

virtual void add(idx_t n, const float *x) override

Add n vectors of dimension d to the index.

Vectors are implicitly assigned labels ntotal .. ntotal + n - 1 This function slices the input vectors in chunks smaller than blocksize_add and calls add_core.

Parameters:

x – input matrix, size n * d

virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const override

entry point for search

virtual void reconstruct(idx_t key, float *recons) const override

Reconstruct a stored vector (or an approximation if lossy coding)

this function may not be defined for some indexes

Parameters:

• key – id of the vector to reconstruct

• recons – reconstucted vector (size d)

virtual void reset() override

removes all elements from the database.

void shrink_level_0_neighbors(int size)

void search_level_0(idx_t n, const float *x, idx_t k, const storage_idx_t *nearest, const float *nearest_d, float *distances, idx_t *labels, int nprobe = 1, int search_type = 1) const

Perform search only on level 0, given the starting points for each vertex.

Parameters:

search_type – 1:perform one search per nprobe, 2: enqueue all entry points

void init_level_0_from_knngraph(int k, const float *D, const idx_t *I)

alternative graph building

void init_level_0_from_entry_points(int npt, const storage_idx_t *points, const storage_idx_t *nearests)

alternative graph building

void reorder_links()

void link_singletons()

void permute_entries(const idx_t *perm)

Public Members

HNSW hnsw

bool own_fields = false

Index *storage = nullptr

ReconstructFromNeighbors *reconstruct_from_neighbors = nullptr

struct IndexHNSWSQ : public faiss::IndexHNSW

#include <IndexHNSW.h>

SQ index topped with with a HNSW structure to access elements more efficiently.

Public Types

typedef HNSW::storage_idx_t storage_idx_t

Public Functions

IndexHNSWSQ()

IndexHNSWSQ(int d, ScalarQuantizer::QuantizerType qtype, int M, MetricType metric = METRIC_L2)

virtual void add(idx_t n, const float *x) override

Add n vectors of dimension d to the index.

Vectors are implicitly assigned labels ntotal .. ntotal + n - 1 This function slices the input vectors in chunks smaller than blocksize_add and calls add_core.

Parameters:

x – input matrix, size n * d

virtual void train(idx_t n, const float *x) override

Trains the storage if needed.

virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const override

entry point for search

virtual void reconstruct(idx_t key, float *recons) const override

Reconstruct a stored vector (or an approximation if lossy coding)

this function may not be defined for some indexes

Parameters:

• key – id of the vector to reconstruct

• recons – reconstucted vector (size d)

virtual void reset() override

removes all elements from the database.

void shrink_level_0_neighbors(int size)

void search_level_0(idx_t n, const float *x, idx_t k, const storage_idx_t *nearest, const float *nearest_d, float *distances, idx_t *labels, int nprobe = 1, int search_type = 1) const

Perform search only on level 0, given the starting points for each vertex.

Parameters:

search_type – 1:perform one search per nprobe, 2: enqueue all entry points

void init_level_0_from_knngraph(int k, const float *D, const idx_t *I)

alternative graph building

void init_level_0_from_entry_points(int npt, const storage_idx_t *points, const storage_idx_t *nearests)

alternative graph building

void reorder_links()

void link_singletons()

void permute_entries(const idx_t *perm)

Public Members

HNSW hnsw

bool own_fields = false

Index *storage = nullptr

ReconstructFromNeighbors *reconstruct_from_neighbors = nullptr

struct IndexHNSW2Level : public faiss::IndexHNSW

#include <IndexHNSW.h>

2-level code structure with fast random access

Public Types

typedef HNSW::storage_idx_t storage_idx_t

Public Functions

IndexHNSW2Level()

IndexHNSW2Level(Index *quantizer, size_t nlist, int m_pq, int M)

void flip_to_ivf()

virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const override

entry point for search

virtual void add(idx_t n, const float *x) override

Add n vectors of dimension d to the index.

Vectors are implicitly assigned labels ntotal .. ntotal + n - 1 This function slices the input vectors in chunks smaller than blocksize_add and calls add_core.

Parameters:

x – input matrix, size n * d

virtual void train(idx_t n, const float *x) override

Trains the storage if needed.

virtual void reconstruct(idx_t key, float *recons) const override

Reconstruct a stored vector (or an approximation if lossy coding)

this function may not be defined for some indexes

Parameters:

• key – id of the vector to reconstruct

• recons – reconstucted vector (size d)

virtual void reset() override

removes all elements from the database.

void shrink_level_0_neighbors(int size)

void search_level_0(idx_t n, const float *x, idx_t k, const storage_idx_t *nearest, const float *nearest_d, float *distances, idx_t *labels, int nprobe = 1, int search_type = 1) const

Perform search only on level 0, given the starting points for each vertex.

Parameters:

search_type – 1:perform one search per nprobe, 2: enqueue all entry points

void init_level_0_from_knngraph(int k, const float *D, const idx_t *I)

alternative graph building

void init_level_0_from_entry_points(int npt, const storage_idx_t *points, const storage_idx_t *nearests)

alternative graph building

void reorder_links()

void link_singletons()

void permute_entries(const idx_t *perm)

Public Members

HNSW hnsw

bool own_fields = false

Index *storage = nullptr

ReconstructFromNeighbors *reconstruct_from_neighbors = nullptr