Faiss

- Main Page
- Namespaces
- Classes
- Files

- File List

All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends
/data/users/matthijs/github_faiss/faiss/IndexIVF.cpp
1 /**
2 * Copyright (c) 2015-present, Facebook, Inc.
3 * All rights reserved.
4 *
5 * This source code is licensed under the BSD+Patents license found in the
6 * LICENSE file in the root directory of this source tree.
7 */
8
9 /* Copyright 2004-present Facebook. All Rights Reserved.
10 Inverted list structure.
11 */
12
13 #include "IndexIVF.h"
14
15 #include <cstdio>
16
17 #include "utils.h"
18 #include "hamming.h"
19
20 #include "FaissAssert.h"
21 #include "IndexFlat.h"
22 #include "AuxIndexStructures.h"
23
24 namespace faiss {
25
26 /*****************************************
27 * IndexIVF implementation
28 ******************************************/
29
30
31 IndexIVF::IndexIVF (Index * quantizer, size_t d, size_t nlist,
32 MetricType metric):
33 Index (d, metric),
34 nlist (nlist),
35 nprobe (1),
36 quantizer (quantizer),
37 quantizer_trains_alone (false),
38 own_fields (false),
39 ids (nlist),
40 maintain_direct_map (false)
41 {
42 FAISS_THROW_IF_NOT (d == quantizer->d);
43 is_trained = quantizer->is_trained && (quantizer->ntotal == nlist);
44 // Spherical by default if the metric is inner_product
45 if (metric_type == METRIC_INNER_PRODUCT) {
46 cp.spherical = true;
47 }
48 // here we set a low # iterations because this is typically used
49 // for large clusterings (nb this is not used for the MultiIndex,
50 // for which quantizer_trains_alone = true)
51 cp.niter = 10;
52 cp.verbose = verbose;
53 code_size = 0; // let sub-classes set this
54 codes.resize(nlist);
55 }
56
57 IndexIVF::IndexIVF ():
58 nlist (0), nprobe (1), quantizer (nullptr),
59 quantizer_trains_alone (false), own_fields (false),
60 maintain_direct_map (false)
61 {}
62
63
64 void IndexIVF::add (idx_t n, const float * x)
65 {
66 add_with_ids (n, x, nullptr);
67 }
68
69 void IndexIVF::make_direct_map (bool new_maintain_direct_map)
70 {
71 // nothing to do
72 if (new_maintain_direct_map == maintain_direct_map)
73 return;
74
75 if (new_maintain_direct_map) {
76 direct_map.resize (ntotal, -1);
77 for (size_t key = 0; key < nlist; key++) {
78 const std::vector<long> & idlist = ids[key];
79
80 for (long ofs = 0; ofs < idlist.size(); ofs++) {
81 FAISS_THROW_IF_NOT_MSG (
82 0 <= idlist [ofs] && idlist[ofs] < ntotal,
83 "direct map supported only for seuquential ids");
84 direct_map [idlist [ofs]] = key << 32 | ofs;
85 }
86 }
87 } else {
88 direct_map.clear ();
89 }
90 maintain_direct_map = new_maintain_direct_map;
91 }
92
93
94 void IndexIVF::search (idx_t n, const float *x, idx_t k,
95 float *distances, idx_t *labels) const
96 {
97 long * idx = new long [n * nprobe];
98 ScopeDeleter<long> del (idx);
99 float * coarse_dis = new float [n * nprobe];
100 ScopeDeleter<float> del2 (coarse_dis);
101
102 quantizer->search (n, x, nprobe, coarse_dis, idx);
103
104 search_preassigned (n, x, k, idx, coarse_dis,
105 distances, labels, false);
106
107 }
108
109
110 void IndexIVF::reset ()
111 {
112 ntotal = 0;
113 direct_map.clear();
114 for (size_t i = 0; i < ids.size(); i++) {
115 ids[i].clear();
116 codes[i].clear();
117 }
118 }
119
120
121 long IndexIVF::remove_ids (const IDSelector & sel)
122 {
123 FAISS_THROW_IF_NOT_MSG (!maintain_direct_map,
124 "direct map remove not implemented");
125 long nremove = 0;
126 #pragma omp parallel for reduction(+: nremove)
127 for (long i = 0; i < nlist; i++) {
128 std::vector<idx_t> & idsi = ids[i];
129 uint8_t * codesi = codes[i].data();
130
131 long l = idsi.size(), j = 0;
132 while (j < l) {
133 if (sel.is_member (idsi[j])) {
134 l--;
135 idsi [j] = idsi [l];
136 memmove (codesi + j * code_size,
137 codesi + l * code_size, code_size);
138 } else {
139 j++;
140 }
141 }
142 if (l < idsi.size()) {
143 nremove += idsi.size() - l;
144 idsi.resize (l);
145 codes[i].resize (l * code_size);
146 }
147 }
148 ntotal -= nremove;
149 return nremove;
150 }
151
152
153
154
155 void IndexIVF::train (idx_t n, const float *x)
156 {
157 if (quantizer->is_trained && (quantizer->ntotal == nlist)) {
158 if (verbose)
159 printf ("IVF quantizer does not need training.\n");
160 } else if (quantizer_trains_alone) {
161 if (verbose)
162 printf ("IVF quantizer trains alone...\n");
163 quantizer->train (n, x);
164 FAISS_THROW_IF_NOT_MSG (quantizer->ntotal == nlist,
165 "nlist not consistent with quantizer size");
166 } else {
167 if (verbose)
168 printf ("Training IVF quantizer on %ld vectors in %dD\n",
169 n, d);
170
171 Clustering clus (d, nlist, cp);
172
173 quantizer->reset();
174 clus.train (n, x, *quantizer);
175 quantizer->is_trained = true;
176 }
177 if (verbose)
178 printf ("Training IVF residual\n");
179
180 train_residual (n, x);
181 is_trained = true;
182 }
183
184 void IndexIVF::train_residual(idx_t /*n*/, const float* /*x*/) {
185 if (verbose)
186 printf("IndexIVF: no residual training\n");
187 // does nothing by default
188 }
189
190
191
192 double IndexIVF::imbalance_factor () const
193 {
194 std::vector<int> hist (nlist);
195 for (int i = 0; i < nlist; i++) {
196 hist[i] = ids[i].size();
197 }
198 return faiss::imbalance_factor (nlist, hist.data());
199 }
200
201 void IndexIVF::print_stats () const
202 {
203 std::vector<int> sizes(40);
204 for (int i = 0; i < nlist; i++) {
205 for (int j = 0; j < sizes.size(); j++) {
206 if ((ids[i].size() >> j) == 0) {
207 sizes[j]++;
208 break;
209 }
210 }
211 }
212 for (int i = 0; i < sizes.size(); i++) {
213 if (sizes[i]) {
214 printf ("list size in < %d: %d instances\n",
215 1 << i, sizes[i]);
216 }
217 }
218
219 }
220
221 void IndexIVF::merge_from (IndexIVF &other, idx_t add_id)
222 {
223 // minimal sanity checks
224 FAISS_THROW_IF_NOT (other.d == d);
225 FAISS_THROW_IF_NOT (other.nlist == nlist);
226 FAISS_THROW_IF_NOT_MSG ((!maintain_direct_map &&
227 !other.maintain_direct_map),
228 "direct map copy not implemented");
229 FAISS_THROW_IF_NOT_MSG (typeid (*this) == typeid (other),
230 "can only merge indexes of the same type");
231 for (long i = 0; i < nlist; i++) {
232 std::vector<idx_t> & src = other.ids[i];
233 std::vector<idx_t> & dest = ids[i];
234 for (long j = 0; j < src.size(); j++)
235 dest.push_back (src[j] + add_id);
236 src.clear();
237 codes[i].insert (codes[i].end(),
238 other.codes[i].begin(),
239 other.codes[i].end());
240 other.codes[i].clear();
241 }
242
243 ntotal += other.ntotal;
244 other.ntotal = 0;
245 }
246
247
248 void IndexIVF::copy_subset_to (IndexIVF & other, int subset_type,
249 long a1, long a2) const
250 {
251 FAISS_THROW_IF_NOT (nlist == other.nlist);
252 FAISS_THROW_IF_NOT (!other.maintain_direct_map);
253 FAISS_THROW_IF_NOT_MSG (subset_type == 0 || subset_type == 2,
254 "this subset type is not implemented");
255
256 size_t accu_n = 0;
257 size_t accu_a1 = 0;
258 size_t accu_a2 = 0;
259
260 for (long list_no = 0; list_no < nlist; list_no++) {
261 const std::vector<idx_t> & ids_in = ids[list_no];
262 std::vector<idx_t> & ids_out = other.ids[list_no];
263 const std::vector<uint8_t> & codes_in = codes[list_no];
264 std::vector<uint8_t> & codes_out = other.codes[list_no];
265 size_t n = ids_in.size();
266
267 if (subset_type == 0) {
268 for (long i = 0; i < n; i++) {
269 idx_t id = ids_in[i];
270 if (a1 <= id && id < a2) {
271 ids_out.push_back (id);
272 codes_out.insert (codes_out.end(),
273 codes_in.begin() + i * code_size,
274 codes_in.begin() + (i + 1) * code_size);
275 other.ntotal++;
276 }
277 }
278 } else if (subset_type == 2) {
279 // see what is allocated to a1 and to a2
280 size_t next_accu_n = accu_n + n;
281 size_t next_accu_a1 = next_accu_n * a1 / ntotal;
282 size_t i1 = next_accu_a1 - accu_a1;
283 accu_a1 = next_accu_a1;
284 size_t next_accu_a2 = next_accu_n * a2 / ntotal;
285 size_t i2 = next_accu_a2 - accu_a2;
286 accu_a2 = next_accu_a2;
287 ids_out.insert(ids_out.end(),
288 ids_in.begin() + i1,
289 ids_in.begin() + i2);
290 codes_out.insert (codes_out.end(),
291 codes_in.begin() + i1 * code_size,
292 codes_in.begin() + i2 * code_size);
293 other.ntotal += i2 - i1;
294 }
295 accu_n += n;
296 }
297 FAISS_ASSERT(accu_n == ntotal);
298 }
299
300
301
302 IndexIVF::~IndexIVF()
303 {
304 if (own_fields) delete quantizer;
305 }
306
307
308
309 /*****************************************
310 * IndexIVFFlat implementation
311 ******************************************/
312
313 IndexIVFFlat::IndexIVFFlat (Index * quantizer,
314 size_t d, size_t nlist, MetricType metric):
315 IndexIVF (quantizer, d, nlist, metric)
316 {
317 code_size = sizeof(float) * d;
318 }
319
320
321
322
323
324
325 void IndexIVFFlat::add_with_ids (idx_t n, const float * x, const long *xids)
326 {
327 add_core (n, x, xids, nullptr);
328 }
329
330 void IndexIVFFlat::add_core (idx_t n, const float * x, const long *xids,
331 const long *precomputed_idx)
332
333 {
334 FAISS_THROW_IF_NOT (is_trained);
335 FAISS_THROW_IF_NOT_MSG (!(maintain_direct_map && xids),
336 "cannot have direct map and add with ids");
337 const long * idx;
338 ScopeDeleter<long> del;
339
340 if (precomputed_idx) {
341 idx = precomputed_idx;
342 } else {
343 long * idx0 = new long [n];
344 quantizer->assign (n, x, idx0);
345 idx = idx0;
346 del.set (idx);
347 }
348 long n_add = 0;
349 for (size_t i = 0; i < n; i++) {
350 long id = xids ? xids[i] : ntotal + i;
351 long list_no = idx [i];
352 if (list_no < 0)
353 continue;
354 assert (list_no < nlist);
355
356 ids[list_no].push_back (id);
357 const float *xi = x + i * d;
358 /* store the vectors */
359 size_t ofs = codes[list_no].size();
360 codes[list_no].resize(ofs + code_size);
361 memcpy(codes[list_no].data() + ofs,
362 xi, code_size);
363
364 if (maintain_direct_map)
365 direct_map.push_back (list_no << 32 | (ids[list_no].size() - 1));
366 n_add++;
367 }
368 if (verbose) {
369 printf("IndexIVFFlat::add_core: added %ld / %ld vectors\n",
370 n_add, n);
371 }
372 ntotal += n_add;
373 }
374
375 void IndexIVFFlatStats::reset()
376 {
377 memset ((void*)this, 0, sizeof (*this));
378 }
379
380
381 IndexIVFFlatStats indexIVFFlat_stats;
382
383 namespace {
384
385 void search_knn_inner_product (const IndexIVFFlat & ivf,
386 size_t nx,
387 const float * x,
388 const long * keys,
389 float_minheap_array_t * res,
390 bool store_pairs)
391 {
392
393 const size_t k = res->k;
394 size_t nlistv = 0, ndis = 0;
395 size_t d = ivf.d;
396
397 #pragma omp parallel for reduction(+: nlistv, ndis)
398 for (size_t i = 0; i < nx; i++) {
399 const float * xi = x + i * d;
400 const long * keysi = keys + i * ivf.nprobe;
401 float * __restrict simi = res->get_val (i);
402 long * __restrict idxi = res->get_ids (i);
403 minheap_heapify (k, simi, idxi);
404
405 for (size_t ik = 0; ik < ivf.nprobe; ik++) {
406 long key = keysi[ik]; /* select the list */
407 if (key < 0) {
408 // not enough centroids for multiprobe
409 continue;
410 }
411 FAISS_THROW_IF_NOT_FMT (
412 key < (long) ivf.nlist,
413 "Invalid key=%ld at ik=%ld nlist=%ld\n",
414 key, ik, ivf.nlist);
415
416 nlistv++;
417 const size_t list_size = ivf.ids[key].size();
418 const float * list_vecs = (const float*)(ivf.codes[key].data());
419
420 for (size_t j = 0; j < list_size; j++) {
421 const float * yj = list_vecs + d * j;
422 float ip = fvec_inner_product (xi, yj, d);
423 if (ip > simi[0]) {
424 minheap_pop (k, simi, idxi);
425 long id = store_pairs ? (key << 32 | j) : ivf.ids[key][j];
426 minheap_push (k, simi, idxi, ip, id);
427 }
428 }
429 ndis += list_size;
430 }
431 minheap_reorder (k, simi, idxi);
432 }
433 indexIVFFlat_stats.nq += nx;
434 indexIVFFlat_stats.nlist += nlistv;
435 indexIVFFlat_stats.ndis += ndis;
436 }
437
438
439 void search_knn_L2sqr (const IndexIVFFlat &ivf,
440 size_t nx,
441 const float * x,
442 const long * keys,
443 float_maxheap_array_t * res,
444 bool store_pairs)
445 {
446 const size_t k = res->k;
447 size_t nlistv = 0, ndis = 0;
448 size_t d = ivf.d;
449 #pragma omp parallel for reduction(+: nlistv, ndis)
450 for (size_t i = 0; i < nx; i++) {
451 const float * xi = x + i * d;
452 const long * keysi = keys + i * ivf.nprobe;
453 float * __restrict disi = res->get_val (i);
454 long * __restrict idxi = res->get_ids (i);
455 maxheap_heapify (k, disi, idxi);
456
457 for (size_t ik = 0; ik < ivf.nprobe; ik++) {
458 long key = keysi[ik]; /* select the list */
459 if (key < 0) {
460 // not enough centroids for multiprobe
461 continue;
462 }
463 FAISS_THROW_IF_NOT_FMT (
464 key < (long) ivf.nlist,
465 "Invalid key=%ld at ik=%ld nlist=%ld\n",
466 key, ik, ivf.nlist);
467
468 nlistv++;
469 const size_t list_size = ivf.ids[key].size();
470 const float * list_vecs = (const float*)(ivf.codes[key].data());
471
472 for (size_t j = 0; j < list_size; j++) {
473 const float * yj = list_vecs + d * j;
474 float disij = fvec_L2sqr (xi, yj, d);
475 if (disij < disi[0]) {
476 maxheap_pop (k, disi, idxi);
477 long id = store_pairs ? (key << 32 | j) : ivf.ids[key][j];
478 maxheap_push (k, disi, idxi, disij, id);
479 }
480 }
481 ndis += list_size;
482 }
483 maxheap_reorder (k, disi, idxi);
484 }
485 indexIVFFlat_stats.nq += nx;
486 indexIVFFlat_stats.nlist += nlistv;
487 indexIVFFlat_stats.ndis += ndis;
488 }
489
490
491 } // anonymous namespace
492
493 void IndexIVFFlat::search_preassigned (idx_t n, const float *x, idx_t k,
494 const idx_t *idx,
495 const float * /* coarse_dis */,
496 float *distances, idx_t *labels,
497 bool store_pairs) const
498 {
499 if (metric_type == METRIC_INNER_PRODUCT) {
500 float_minheap_array_t res = {
501 size_t(n), size_t(k), labels, distances};
502 search_knn_inner_product (*this, n, x, idx, &res, store_pairs);
503
504 } else if (metric_type == METRIC_L2) {
505 float_maxheap_array_t res = {
506 size_t(n), size_t(k), labels, distances};
507 search_knn_L2sqr (*this, n, x, idx, &res, store_pairs);
508 }
509 }
510
511
512 void IndexIVFFlat::range_search (idx_t nx, const float *x, float radius,
513 RangeSearchResult *result) const
514 {
515 idx_t * keys = new idx_t [nx * nprobe];
516 ScopeDeleter<idx_t> del (keys);
517 quantizer->assign (nx, x, keys, nprobe);
518
519 #pragma omp parallel
520 {
521 RangeSearchPartialResult pres(result);
522
523 for (size_t i = 0; i < nx; i++) {
524 const float * xi = x + i * d;
525 const long * keysi = keys + i * nprobe;
526
527 RangeSearchPartialResult::QueryResult & qres =
528 pres.new_result (i);
529
530 for (size_t ik = 0; ik < nprobe; ik++) {
531 long key = keysi[ik]; /* select the list */
532 if (key < 0 || key >= (long) nlist) {
533 fprintf (stderr, "Invalid key=%ld at ik=%ld nlist=%ld\n",
534 key, ik, nlist);
535 throw;
536 }
537
538 const size_t list_size = ids[key].size();
539 const float * list_vecs = (const float *)(codes[key].data());
540
541 for (size_t j = 0; j < list_size; j++) {
542 const float * yj = list_vecs + d * j;
543 if (metric_type == METRIC_L2) {
544 float disij = fvec_L2sqr (xi, yj, d);
545 if (disij < radius) {
546 qres.add (disij, ids[key][j]);
547 }
548 } else if (metric_type == METRIC_INNER_PRODUCT) {
549 float disij = fvec_inner_product(xi, yj, d);
550 if (disij > radius) {
551 qres.add (disij, ids[key][j]);
552 }
553 }
554 }
555 }
556 }
557
558 pres.finalize ();
559 }
560 }
561
562 void IndexIVFFlat::update_vectors (int n, idx_t *new_ids, const float *x)
563 {
564 FAISS_THROW_IF_NOT (maintain_direct_map);
565 FAISS_THROW_IF_NOT (is_trained);
566 std::vector<idx_t> assign (n);
567 quantizer->assign (n, x, assign.data());
568
569 for (int i = 0; i < n; i++) {
570 idx_t id = new_ids[i];
571 FAISS_THROW_IF_NOT_MSG (0 <= id && id < ntotal,
572 "id to update out of range");
573 { // remove old one
574 long dm = direct_map[id];
575 long ofs = dm & 0xffffffff;
576 long il = dm >> 32;
577 size_t l = ids[il].size();
578 if (ofs != l - 1) {
579 long id2 = ids[il].back();
580 ids[il][ofs] = id2;
581 direct_map[id2] = (il << 32) | ofs;
582 float * vecs = (float*)codes[il].data();
583 memcpy (vecs + ofs * d,
584 vecs + (l - 1) * d,
585 d * sizeof(float));
586 }
587 ids[il].pop_back();
588 codes[il].resize((l - 1) * code_size);
589 }
590 { // insert new one
591 long il = assign[i];
592 size_t l = ids[il].size();
593 long dm = (il << 32) | l;
594 direct_map[id] = dm;
595 ids[il].push_back (id);
596 codes[il].resize((l + 1) * code_size);
597 float * vecs = (float*)codes[il].data();
598 memcpy (vecs + l * d,
599 x + i * d,
600 d * sizeof(float));
601 }
602 }
603
604 }
605
606
607
608
609
610 void IndexIVFFlat::reconstruct (idx_t key, float * recons) const
611 {
612 FAISS_THROW_IF_NOT_MSG (direct_map.size() == ntotal,
613 "direct map is not initialized");
614 int list_no = direct_map[key] >> 32;
615 int ofs = direct_map[key] & 0xffffffff;
616 memcpy (recons, &codes[list_no][ofs * code_size], d * sizeof(recons[0]));
617 }
618
619
620
621
622 } // namespace faiss
faiss::IndexIVF::search_preassigned
virtual void search_preassigned(idx_t n, const float *x, idx_t k, const idx_t *assign, const float *centroid_dis, float *distances, idx_t *labels, bool store_pairs) const =0
faiss::IndexIVF
Definition: IndexIVF.h:45
faiss::ClusteringParameters::niter
int niter
clustering iterations
Definition: Clustering.h:25
faiss::RangeSearchPartialResult::QueryResult
result structure for a single query
Definition: AuxIndexStructures.h:145
faiss::fvec_L2sqr
float fvec_L2sqr(const float *x, const float *y, size_t d)
Squared L2 distance between two vectors.
Definition: utils.cpp:481
faiss::IndexIVF::imbalance_factor
double imbalance_factor() const
1= perfectly balanced, &gt;1: imbalanced
Definition: IndexIVF.cpp:192
faiss::Index::reset
virtual void reset()=0
removes all elements from the database.
faiss::IndexIVF::copy_subset_to
virtual void copy_subset_to(IndexIVF &other, int subset_type, long a1, long a2) const
Definition: IndexIVF.cpp:248
faiss::IndexIVF::nprobe
size_t nprobe
number of probes at query time
Definition: IndexIVF.h:47
faiss::Index::train
virtual void train(idx_t, const float *)
Definition: Index.h:89
faiss::IndexIVFFlat::reconstruct
void reconstruct(idx_t key, float *recons) const override
Definition: IndexIVF.cpp:610
faiss::Index::assign
void assign(idx_t n, const float *x, idx_t *labels, idx_t k=1)
Definition: Index.cpp:23
faiss::IDSelector
Definition: AuxIndexStructures.h:52
faiss::IndexIVF::quantizer_trains_alone
bool quantizer_trains_alone
just pass over the trainset to quantizer
Definition: IndexIVF.h:50
faiss::IndexIVFFlat::range_search
void range_search(idx_t n, const float *x, float radius, RangeSearchResult *result) const override
Definition: IndexIVF.cpp:512
faiss::Index::add_with_ids
virtual void add_with_ids(idx_t n, const float *x, const long *xids)
Definition: Index.cpp:30
faiss::IndexIVF::train_residual
virtual void train_residual(idx_t n, const float *x)
Definition: IndexIVF.cpp:184
faiss::ScopeDeleter
Definition: FaissException.h:39
faiss::imbalance_factor
double imbalance_factor(int n, int k, const long *assign)
a balanced assignment has a IF of 1
Definition: utils.cpp:1593
faiss::IndexIVF::ids
std::vector< std::vector< long > > ids
Inverted lists for indexes.
Definition: IndexIVF.h:55
faiss::Index::d
int d
vector dimension
Definition: Index.h:64
faiss::IndexIVF::quantizer
Index * quantizer
quantizer that maps vectors to inverted lists
Definition: IndexIVF.h:49
faiss::IndexIVF::train
void train(idx_t n, const float *x) override
Trains the quantizer and calls train_residual to train sub-quantizers.
Definition: IndexIVF.cpp:155
faiss::IndexIVF::cp
ClusteringParameters cp
to override default clustering params
Definition: IndexIVF.h:53
faiss::IndexIVFFlat::add_with_ids
void add_with_ids(idx_t n, const float *x, const long *xids) override
implemented for all IndexIVF* classes
Definition: IndexIVF.cpp:325
faiss::Clustering
Definition: Clustering.h:56
faiss::IndexIVF::own_fields
bool own_fields
whether object owns the quantizer
Definition: IndexIVF.h:51
faiss::HeapArray
Definition: Heap.h:350
faiss::Index::idx_t
long idx_t
all indices are this type
Definition: Index.h:62
faiss::Index::ntotal
idx_t ntotal
total nb of indexed vectors
Definition: Index.h:65
faiss::Index::verbose
bool verbose
verbosity level
Definition: Index.h:66
faiss::IndexIVF::reset
void reset() override
removes all elements from the database.
Definition: IndexIVF.cpp:110
faiss::RangeSearchPartialResult::new_result
QueryResult & new_result(idx_t qno)
begin a new result
Definition: AuxIndexStructures.cpp:117
faiss::IndexIVFFlat::update_vectors
void update_vectors(int nv, idx_t *idx, const float *v)
Definition: IndexIVF.cpp:562
faiss::Index::search
virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels) const =0
faiss::RangeSearchPartialResult
the entries in the buffers are split per query
Definition: AuxIndexStructures.h:139
faiss::RangeSearchResult
Definition: AuxIndexStructures.h:29
faiss::IndexIVF::make_direct_map
void make_direct_map(bool new_maintain_direct_map=true)
Definition: IndexIVF.cpp:69
faiss::Index::metric_type
MetricType metric_type
type of metric this index uses for search
Definition: Index.h:72
faiss::IndexIVF::print_stats
void print_stats() const
display some stats about the inverted lists
Definition: IndexIVF.cpp:201
faiss::IndexIVF::nlist
size_t nlist
number of possible key values
Definition: IndexIVF.h:46
faiss::Index
Definition: Index.h:60
faiss::IndexIVF::add
void add(idx_t n, const float *x) override
Quantizes x and calls add_with_key.
Definition: IndexIVF.cpp:64
faiss::Clustering::train
virtual void train(idx_t n, const float *x, faiss::Index &index)
Index is used during the assignment stage.
Definition: Clustering.cpp:66
faiss::Index::is_trained
bool is_trained
set if the Index does not require training, or if training is done already
Definition: Index.h:69
faiss::IndexIVF::remove_ids
long remove_ids(const IDSelector &sel) override
Dataset manipulation functions.
Definition: IndexIVF.cpp:121
faiss::IndexIVF::maintain_direct_map
bool maintain_direct_map
map for direct access to the elements. Enables reconstruct().
Definition: IndexIVF.h:61
faiss::ClusteringParameters::spherical
bool spherical
do we want normalized centroids?
Definition: Clustering.h:29
faiss::IndexIVF::search
virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels) const override
Definition: IndexIVF.cpp:94
faiss::IndexIVFFlat::search_preassigned
void search_preassigned(idx_t n, const float *x, idx_t k, const idx_t *assign, const float *centroid_dis, float *distances, idx_t *labels, bool store_pairs) const override
Definition: IndexIVF.cpp:493
faiss::IndexIVF::merge_from
virtual void merge_from(IndexIVF &other, idx_t add_id)
Definition: IndexIVF.cpp:221
faiss::IndexIVF::code_size
size_t code_size
code size per vector in bytes
Definition: IndexIVF.h:57
faiss::MetricType
MetricType
Some algorithms support both an inner product vetsion and a L2 search version.
Definition: Index.h:43
faiss::IndexIVFFlat::add_core
virtual void add_core(idx_t n, const float *x, const long *xids, const long *precomputed_idx)
same as add_with_ids, with precomputed coarse quantizer
Definition: IndexIVF.cpp:330