| 1 |
/* |
| 2 |
* Copyright (c) Meta Platforms, Inc. and affiliates. |
| 3 |
* |
| 4 |
* This source code is licensed under the MIT license found in the |
| 5 |
* LICENSE file in the root directory of this source tree. |
| 6 |
*/ |
| 7 |
|
| 8 |
// -*- c -*- |
| 9 |
|
| 10 |
#ifndef FAISS_INDEX_IVF_C_H |
| 11 |
#define FAISS_INDEX_IVF_C_H |
| 12 |
|
| 13 |
#include "Clustering_c.h" |
| 14 |
#include "Index_c.h" |
| 15 |
#include "faiss_c.h" |
| 16 |
#include "impl/AuxIndexStructures_c.h" |
| 17 |
|
| 18 |
#ifdef __cplusplus |
| 19 |
extern "C" { |
| 20 |
#endif |
| 21 |
|
| 22 |
FAISS_DECLARE_CLASS_INHERITED(SearchParametersIVF, SearchParameters) |
| 23 |
FAISS_DECLARE_DESTRUCTOR(SearchParametersIVF) |
| 24 |
FAISS_DECLARE_SEARCH_PARAMETERS_DOWNCAST(SearchParametersIVF) |
| 25 |
|
| 26 |
int faiss_SearchParametersIVF_new(FaissSearchParametersIVF** p_sp); |
| 27 |
int faiss_SearchParametersIVF_new_with( |
| 28 |
FaissSearchParametersIVF** p_sp, |
| 29 |
FaissIDSelector* sel, |
| 30 |
size_t nprobe, |
| 31 |
size_t max_codes); |
| 32 |
|
| 33 |
FAISS_DECLARE_GETTER(SearchParametersIVF, const FaissIDSelector*, sel) |
| 34 |
FAISS_DECLARE_GETTER_SETTER(SearchParametersIVF, size_t, nprobe) |
| 35 |
FAISS_DECLARE_GETTER_SETTER(SearchParametersIVF, size_t, max_codes) |
| 36 |
|
| 37 |
/** Index based on a inverted file (IVF) |
| 38 |
* |
| 39 |
* In the inverted file, the quantizer (an Index instance) provides a |
| 40 |
* quantization index for each vector to be added. The quantization |
| 41 |
* index maps to a list (aka inverted list or posting list), where the |
| 42 |
* id of the vector is then stored. |
| 43 |
* |
| 44 |
* At search time, the vector to be searched is also quantized, and |
| 45 |
* only the list corresponding to the quantization index is |
| 46 |
* searched. This speeds up the search by making it |
| 47 |
* non-exhaustive. This can be relaxed using multi-probe search: a few |
| 48 |
* (nprobe) quantization indices are selected and several inverted |
| 49 |
* lists are visited. |
| 50 |
* |
| 51 |
* Sub-classes implement a post-filtering of the index that refines |
| 52 |
* the distance estimation from the query to database vectors. |
| 53 |
*/ |
| 54 |
FAISS_DECLARE_CLASS_INHERITED(IndexIVF, Index) |
| 55 |
FAISS_DECLARE_DESTRUCTOR(IndexIVF) |
| 56 |
FAISS_DECLARE_INDEX_DOWNCAST(IndexIVF) |
| 57 |
|
| 58 |
/// number of possible key values |
| 59 |
FAISS_DECLARE_GETTER(IndexIVF, size_t, nlist) |
| 60 |
/// number of probes at query time |
| 61 |
FAISS_DECLARE_GETTER_SETTER(IndexIVF, size_t, nprobe) |
| 62 |
/// quantizer that maps vectors to inverted lists |
| 63 |
FAISS_DECLARE_GETTER(IndexIVF, FaissIndex*, quantizer) |
| 64 |
/** |
| 65 |
* = 0: use the quantizer as index in a kmeans training |
| 66 |
* = 1: just pass on the training set to the train() of the quantizer |
| 67 |
* = 2: kmeans training on a flat index + add the centroids to the quantizer |
| 68 |
*/ |
| 69 |
FAISS_DECLARE_GETTER(IndexIVF, char, quantizer_trains_alone) |
| 70 |
|
| 71 |
/// whether object owns the quantizer |
| 72 |
FAISS_DECLARE_GETTER_SETTER(IndexIVF, int, own_fields) |
| 73 |
|
| 74 |
/** moves the entries from another dataset to self. On output, |
| 75 |
* other is empty. add_id is added to all moved ids (for |
| 76 |
* sequential ids, this would be this->ntotal */ |
| 77 |
int faiss_IndexIVF_merge_from( |
| 78 |
FaissIndexIVF* index, |
| 79 |
FaissIndexIVF* other, |
| 80 |
idx_t add_id); |
| 81 |
|
| 82 |
/** copy a subset of the entries index to the other index |
| 83 |
* |
| 84 |
* if subset_type == 0: copies ids in [a1, a2) |
| 85 |
* if subset_type == 1: copies ids if id % a1 == a2 |
| 86 |
* if subset_type == 2: copies inverted lists such that a1 |
| 87 |
* elements are left before and a2 elements are after |
| 88 |
*/ |
| 89 |
int faiss_IndexIVF_copy_subset_to( |
| 90 |
const FaissIndexIVF* index, |
| 91 |
FaissIndexIVF* other, |
| 92 |
int subset_type, |
| 93 |
idx_t a1, |
| 94 |
idx_t a2); |
| 95 |
|
| 96 |
/** search a set of vectors, that are pre-quantized by the IVF |
| 97 |
* quantizer. Fill in the corresponding heaps with the query |
| 98 |
* results. search() calls this. |
| 99 |
* |
| 100 |
* @param n nb of vectors to query |
| 101 |
* @param x query vectors, size nx * d |
| 102 |
* @param assign coarse quantization indices, size nx * nprobe |
| 103 |
* @param centroid_dis |
| 104 |
* distances to coarse centroids, size nx * nprobe |
| 105 |
* @param distance |
| 106 |
* output distances, size n * k |
| 107 |
* @param labels output labels, size n * k |
| 108 |
* @param store_pairs store inv list index + inv list offset |
| 109 |
* instead in upper/lower 32 bit of result, |
| 110 |
* instead of ids (used for reranking). |
| 111 |
*/ |
| 112 |
int faiss_IndexIVF_search_preassigned( |
| 113 |
const FaissIndexIVF* index, |
| 114 |
idx_t n, |
| 115 |
const float* x, |
| 116 |
idx_t k, |
| 117 |
const idx_t* assign, |
| 118 |
const float* centroid_dis, |
| 119 |
float* distances, |
| 120 |
idx_t* labels, |
| 121 |
int store_pairs); |
| 122 |
|
| 123 |
size_t faiss_IndexIVF_get_list_size(const FaissIndexIVF* index, size_t list_no); |
| 124 |
|
| 125 |
/** initialize a direct map |
| 126 |
* |
| 127 |
* @param new_maintain_direct_map if true, create a direct map, |
| 128 |
* else clear it |
| 129 |
*/ |
| 130 |
int faiss_IndexIVF_make_direct_map( |
| 131 |
FaissIndexIVF* index, |
| 132 |
int new_maintain_direct_map); |
| 133 |
|
| 134 |
/** Check the inverted lists' imbalance factor. |
| 135 |
* |
| 136 |
* 1= perfectly balanced, >1: imbalanced |
| 137 |
*/ |
| 138 |
double faiss_IndexIVF_imbalance_factor(const FaissIndexIVF* index); |
| 139 |
|
| 140 |
/// display some stats about the inverted lists of the index |
| 141 |
void faiss_IndexIVF_print_stats(const FaissIndexIVF* index); |
| 142 |
|
| 143 |
/// Get the IDs in an inverted list. IDs are written to `invlist`, which must be |
| 144 |
/// large enough |
| 145 |
//// to accommodate the full list. |
| 146 |
/// |
| 147 |
/// @param list_no the list ID |
| 148 |
/// @param invlist output pointer to a slice of memory, at least as long as the |
| 149 |
/// list's size |
| 150 |
/// @see faiss_IndexIVF_get_list_size(size_t) |
| 151 |
void faiss_IndexIVF_invlists_get_ids( |
| 152 |
const FaissIndexIVF* index, |
| 153 |
size_t list_no, |
| 154 |
idx_t* invlist); |
| 155 |
|
| 156 |
int faiss_IndexIVF_train_encoder( |
| 157 |
FaissIndexIVF* index, |
| 158 |
idx_t n, |
| 159 |
const float* x, |
| 160 |
const idx_t* assign); |
| 161 |
|
| 162 |
typedef struct FaissIndexIVFStats { |
| 163 |
size_t nq; // nb of queries run |
| 164 |
size_t nlist; // nb of inverted lists scanned |
| 165 |
size_t ndis; // nb of distances computed |
| 166 |
size_t nheap_updates; // nb of times the heap was updated |
| 167 |
double quantization_time; // time spent quantizing vectors (in ms) |
| 168 |
double search_time; // time spent searching lists (in ms) |
| 169 |
} FaissIndexIVFStats; |
| 170 |
|
| 171 |
void faiss_IndexIVFStats_reset(FaissIndexIVFStats* stats); |
| 172 |
|
| 173 |
inline void faiss_IndexIVFStats_init(FaissIndexIVFStats* stats) { |
| 174 |
faiss_IndexIVFStats_reset(stats); |
| 175 |
} |
| 176 |
|
| 177 |
/// global var that collects all statistics |
| 178 |
FaissIndexIVFStats* faiss_get_indexIVF_stats(); |
| 179 |
|
| 180 |
#ifdef __cplusplus |
| 181 |
} |
| 182 |
#endif |
| 183 |
|
| 184 |
#endif |