Debian Codegraph @

c_api/IndexIVF_c.h

raw
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