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 CC-by-NC 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
54 }
55
56 IndexIVF::IndexIVF ():
57 nlist (0), nprobe (1), quantizer (nullptr),
58 quantizer_trains_alone (false), own_fields (false),
59 maintain_direct_map (false)
60 {}
61
62
63 void IndexIVF::add (idx_t n, const float * x)
64 {
65 add_with_ids (n, x, nullptr);
66 }
67
68 void IndexIVF::make_direct_map (bool new_maintain_direct_map)
69 {
70 // nothing to do
71 if (new_maintain_direct_map == maintain_direct_map)
72 return;
73
74 if (new_maintain_direct_map) {
75 direct_map.resize (ntotal, -1);
76 for (size_t key = 0; key < nlist; key++) {
77 const std::vector<long> & idlist = ids[key];
78
79 for (long ofs = 0; ofs < idlist.size(); ofs++) {
80 FAISS_THROW_IF_NOT_MSG (
81 0 <= idlist [ofs] && idlist[ofs] < ntotal,
82 "direct map supported only for seuquential ids");
83 direct_map [idlist [ofs]] = key << 32 | ofs;
84 }
85 }
86 } else {
87 direct_map.clear ();
88 }
89 maintain_direct_map = new_maintain_direct_map;
90 }
91
92
93 void IndexIVF::reset ()
94 {
95 ntotal = 0;
96 direct_map.clear();
97 for (size_t i = 0; i < ids.size(); i++)
98 ids[i].clear();
99 }
100
101
102 void IndexIVF::train (idx_t n, const float *x)
103 {
104 if (quantizer->is_trained && (quantizer->ntotal == nlist)) {
105 if (verbose)
106 printf ("IVF quantizer does not need training.\n");
107 } else if (quantizer_trains_alone) {
108 if (verbose)
109 printf ("IVF quantizer trains alone...\n");
110 quantizer->train (n, x);
111 FAISS_THROW_IF_NOT_MSG (quantizer->ntotal == nlist,
112 "nlist not consistent with quantizer size");
113 } else {
114 if (verbose)
115 printf ("Training IVF quantizer on %ld vectors in %dD\n",
116 n, d);
117
118 Clustering clus (d, nlist, cp);
119
120 quantizer->reset();
121 clus.train (n, x, *quantizer);
122 quantizer->is_trained = true;
123 }
124 if (verbose)
125 printf ("Training IVF residual\n");
126
127 train_residual (n, x);
128 is_trained = true;
129 }
130
131 void IndexIVF::train_residual(idx_t /*n*/, const float* /*x*/) {
132 if (verbose)
133 printf("IndexIVF: no residual training\n");
134 // does nothing by default
135 }
136
137
138
139 double IndexIVF::imbalance_factor () const
140 {
141 std::vector<int> hist (nlist);
142 for (int i = 0; i < nlist; i++) {
143 hist[i] = ids[i].size();
144 }
145 return faiss::imbalance_factor (nlist, hist.data());
146 }
147
148 void IndexIVF::print_stats () const
149 {
150 std::vector<int> sizes(40);
151 for (int i = 0; i < nlist; i++) {
152 for (int j = 0; j < sizes.size(); j++) {
153 if ((ids[i].size() >> j) == 0) {
154 sizes[j]++;
155 break;
156 }
157 }
158 }
159 for (int i = 0; i < sizes.size(); i++) {
160 if (sizes[i]) {
161 printf ("list size in < %d: %d instances\n",
162 1 << i, sizes[i]);
163 }
164 }
165
166 }
167
168 void IndexIVF::merge_from (IndexIVF &other, idx_t add_id)
169 {
170 // minimal sanity checks
171 FAISS_THROW_IF_NOT (other.d == d);
172 FAISS_THROW_IF_NOT (other.nlist == nlist);
173 FAISS_THROW_IF_NOT_MSG ((!maintain_direct_map &&
174 !other.maintain_direct_map),
175 "direct map copy not implemented");
176 FAISS_THROW_IF_NOT_MSG (typeid (*this) == typeid (other),
177 "can only merge indexes of the same type");
178 for (long i = 0; i < nlist; i++) {
179 std::vector<idx_t> & src = other.ids[i];
180 std::vector<idx_t> & dest = ids[i];
181 for (long j = 0; j < src.size(); j++)
182 dest.push_back (src[j] + add_id);
183 src.clear();
184 }
185 merge_from_residuals (other);
186 ntotal += other.ntotal;
187 other.ntotal = 0;
188 }
189
190
191
192 IndexIVF::~IndexIVF()
193 {
194 if (own_fields) delete quantizer;
195 }
196
197
198
199 /*****************************************
200 * IndexIVFFlat implementation
201 ******************************************/
202
203 IndexIVFFlat::IndexIVFFlat (Index * quantizer,
204 size_t d, size_t nlist, MetricType metric):
205 IndexIVF (quantizer, d, nlist, metric)
206 {
207 vecs.resize (nlist);
208 }
209
210
211
212
213
214
215 void IndexIVFFlat::add_with_ids (idx_t n, const float * x, const long *xids)
216 {
217 add_core (n, x, xids, nullptr);
218 }
219
220 void IndexIVFFlat::add_core (idx_t n, const float * x, const long *xids,
221 const long *precomputed_idx)
222
223 {
224 FAISS_THROW_IF_NOT (is_trained);
225 FAISS_THROW_IF_NOT_MSG (!(maintain_direct_map && xids),
226 "cannot have direct map and add with ids");
227 const long * idx;
228 ScopeDeleter<long> del;
229
230 if (precomputed_idx) {
231 idx = precomputed_idx;
232 } else {
233 long * idx0 = new long [n];
234 quantizer->assign (n, x, idx0);
235 idx = idx0;
236 del.set (idx);
237 }
238 long n_add = 0;
239 for (size_t i = 0; i < n; i++) {
240 long id = xids ? xids[i] : ntotal + i;
241 long list_no = idx [i];
242 if (list_no < 0)
243 continue;
244 assert (list_no < nlist);
245
246 ids[list_no].push_back (id);
247 const float *xi = x + i * d;
248 /* store the vectors */
249 for (size_t j = 0 ; j < d ; j++)
250 vecs[list_no].push_back (xi [j]);
251
252 if (maintain_direct_map)
253 direct_map.push_back (list_no << 32 | (ids[list_no].size() - 1));
254 n_add++;
255 }
256 if (verbose) {
257 printf("IndexIVFFlat::add_core: added %ld / %ld vectors\n",
258 n_add, n);
259 }
260 ntotal += n_add;
261 }
262
263 void IndexIVFFlatStats::reset()
264 {
265 memset ((void*)this, 0, sizeof (*this));
266 }
267
268
269 IndexIVFFlatStats indexIVFFlat_stats;
270
271 void IndexIVFFlat::search_knn_inner_product (
272 size_t nx,
273 const float * x,
274 const long * __restrict keys,
275 float_minheap_array_t * res) const
276 {
277
278 const size_t k = res->k;
279 size_t nlistv = 0, ndis = 0;
280
281 #pragma omp parallel for reduction(+: nlistv, ndis)
282 for (size_t i = 0; i < nx; i++) {
283 const float * xi = x + i * d;
284 const long * keysi = keys + i * nprobe;
285 float * __restrict simi = res->get_val (i);
286 long * __restrict idxi = res->get_ids (i);
287 minheap_heapify (k, simi, idxi);
288
289 for (size_t ik = 0; ik < nprobe; ik++) {
290 long key = keysi[ik]; /* select the list */
291 if (key < 0) {
292 // not enough centroids for multiprobe
293 continue;
294 }
295 if (key >= (long) nlist) {
296 fprintf (stderr, "Invalid key=%ld at ik=%ld nlist=%ld\n",
297 key, ik, nlist);
298 throw;
299 }
300 nlistv++;
301 const size_t list_size = ids[key].size();
302 const float * list_vecs = vecs[key].data();
303
304 for (size_t j = 0; j < list_size; j++) {
305 const float * yj = list_vecs + d * j;
306 float ip = fvec_inner_product (xi, yj, d);
307 if (ip > simi[0]) {
308 minheap_pop (k, simi, idxi);
309 minheap_push (k, simi, idxi, ip, ids[key][j]);
310 }
311 }
312 ndis += list_size;
313 }
314 minheap_reorder (k, simi, idxi);
315 }
316 indexIVFFlat_stats.nq += nx;
317 indexIVFFlat_stats.nlist += nlistv;
318 indexIVFFlat_stats.ndis += ndis;
319 }
320
321
322 void IndexIVFFlat::search_knn_L2sqr (
323 size_t nx,
324 const float * x,
325 const long * __restrict keys,
326 float_maxheap_array_t * res) const
327 {
328 const size_t k = res->k;
329 size_t nlistv = 0, ndis = 0;
330
331 #pragma omp parallel for reduction(+: nlistv, ndis)
332 for (size_t i = 0; i < nx; i++) {
333 const float * xi = x + i * d;
334 const long * keysi = keys + i * nprobe;
335 float * __restrict disi = res->get_val (i);
336 long * __restrict idxi = res->get_ids (i);
337 maxheap_heapify (k, disi, idxi);
338
339 for (size_t ik = 0; ik < nprobe; ik++) {
340 long key = keysi[ik]; /* select the list */
341 if (key < 0) {
342 // not enough centroids for multiprobe
343 continue;
344 }
345 if (key >= (long) nlist) {
346 fprintf (stderr, "Invalid key=%ld at ik=%ld nlist=%ld\n",
347 key, ik, nlist);
348 throw;
349 }
350 nlistv++;
351 const size_t list_size = ids[key].size();
352 const float * list_vecs = vecs[key].data();
353
354 for (size_t j = 0; j < list_size; j++) {
355 const float * yj = list_vecs + d * j;
356 float disij = fvec_L2sqr (xi, yj, d);
357 if (disij < disi[0]) {
358 maxheap_pop (k, disi, idxi);
359 maxheap_push (k, disi, idxi, disij, ids[key][j]);
360 }
361 }
362 ndis += list_size;
363 }
364 maxheap_reorder (k, disi, idxi);
365 }
366 indexIVFFlat_stats.nq += nx;
367 indexIVFFlat_stats.nlist += nlistv;
368 indexIVFFlat_stats.ndis += ndis;
369 }
370
371
372 void IndexIVFFlat::search (idx_t n, const float *x, idx_t k,
373 float *distances, idx_t *labels) const
374 {
375 idx_t * idx = new idx_t [n * nprobe];
376 ScopeDeleter <idx_t> del (idx);
377 quantizer->assign (n, x, idx, nprobe);
378 search_preassigned (n, x, k, idx, distances, labels);
379 }
380
381
382 void IndexIVFFlat::search_preassigned (idx_t n, const float *x, idx_t k,
383 const idx_t *idx,
384 float *distances, idx_t *labels) const
385 {
386 if (metric_type == METRIC_INNER_PRODUCT) {
387 float_minheap_array_t res = {
388 size_t(n), size_t(k), labels, distances};
389 search_knn_inner_product (n, x, idx, &res);
390
391 } else if (metric_type == METRIC_L2) {
392 float_maxheap_array_t res = {
393 size_t(n), size_t(k), labels, distances};
394 search_knn_L2sqr (n, x, idx, &res);
395 }
396
397 }
398
399
400 void IndexIVFFlat::range_search (idx_t nx, const float *x, float radius,
401 RangeSearchResult *result) const
402 {
403 idx_t * keys = new idx_t [nx * nprobe];
404 ScopeDeleter<idx_t> del (keys);
405 quantizer->assign (nx, x, keys, nprobe);
406
407 #pragma omp parallel
408 {
409 RangeSearchPartialResult pres(result);
410
411 for (size_t i = 0; i < nx; i++) {
412 const float * xi = x + i * d;
413 const long * keysi = keys + i * nprobe;
414
415 RangeSearchPartialResult::QueryResult & qres =
416 pres.new_result (i);
417
418 for (size_t ik = 0; ik < nprobe; ik++) {
419 long key = keysi[ik]; /* select the list */
420 if (key < 0 || key >= (long) nlist) {
421 fprintf (stderr, "Invalid key=%ld at ik=%ld nlist=%ld\n",
422 key, ik, nlist);
423 throw;
424 }
425
426 const size_t list_size = ids[key].size();
427 const float * list_vecs = vecs[key].data();
428
429 for (size_t j = 0; j < list_size; j++) {
430 const float * yj = list_vecs + d * j;
431 if (metric_type == METRIC_L2) {
432 float disij = fvec_L2sqr (xi, yj, d);
433 if (disij < radius) {
434 qres.add (disij, ids[key][j]);
435 }
436 } else if (metric_type == METRIC_INNER_PRODUCT) {
437 float disij = fvec_inner_product(xi, yj, d);
438 if (disij > radius) {
439 qres.add (disij, ids[key][j]);
440 }
441 }
442 }
443 }
444 }
445
446 pres.finalize ();
447 }
448 }
449
450 void IndexIVFFlat::merge_from_residuals (IndexIVF &other_in)
451 {
452 IndexIVFFlat &other = dynamic_cast<IndexIVFFlat &> (other_in);
453 for (int i = 0; i < nlist; i++) {
454 std::vector<float> & src = other.vecs[i];
455 std::vector<float> & dest = vecs[i];
456 for (int j = 0; j < src.size(); j++)
457 dest.push_back (src[j]);
458 src.clear();
459 }
460 }
461
462 void IndexIVFFlat::copy_subset_to (IndexIVFFlat & other, int subset_type,
463 long a1, long a2) const
464 {
465 FAISS_THROW_IF_NOT (nlist == other.nlist);
466 FAISS_THROW_IF_NOT (!other.maintain_direct_map);
467
468 for (long list_no = 0; list_no < nlist; list_no++) {
469 const std::vector<idx_t> & ids_in = ids[list_no];
470 std::vector<idx_t> & ids_out = other.ids[list_no];
471 const std::vector<float> & vecs_in = vecs[list_no];
472 std::vector<float> & vecs_out = other.vecs[list_no];
473
474 for (long i = 0; i < ids_in.size(); i++) {
475 idx_t id = ids_in[i];
476 if (subset_type == 0 && a1 <= id && id < a2) {
477 ids_out.push_back (id);
478 vecs_out.insert (vecs_out.end(),
479 vecs_in.begin() + i * d,
480 vecs_in.begin() + (i + 1) * d);
481 other.ntotal++;
482 }
483 }
484 }
485 }
486
487 void IndexIVFFlat::update_vectors (int n, idx_t *new_ids, const float *x)
488 {
489 FAISS_THROW_IF_NOT (maintain_direct_map);
490 FAISS_THROW_IF_NOT (is_trained);
491 std::vector<idx_t> assign (n);
492 quantizer->assign (n, x, assign.data());
493
494 for (int i = 0; i < n; i++) {
495 idx_t id = new_ids[i];
496 FAISS_THROW_IF_NOT_MSG (0 <= id && id < ntotal,
497 "id to update out of range");
498 { // remove old one
499 long dm = direct_map[id];
500 long ofs = dm & 0xffffffff;
501 long il = dm >> 32;
502 size_t l = ids[il].size();
503 if (ofs != l - 1) {
504 long id2 = ids[il].back();
505 ids[il][ofs] = id2;
506 direct_map[id2] = (il << 32) | ofs;
507 memcpy (vecs[il].data() + ofs * d,
508 vecs[il].data() + (l - 1) * d,
509 d * sizeof(vecs[il][0]));
510 }
511 ids[il].pop_back();
512 vecs[il].resize((l - 1) * d);
513 }
514 { // insert new one
515 long il = assign[i];
516 size_t l = ids[il].size();
517 long dm = (il << 32) | l;
518 direct_map[id] = dm;
519 ids[il].push_back (id);
520 vecs[il].resize((l + 1) * d);
521 memcpy (vecs[il].data() + l * d,
522 x + i * d,
523 d * sizeof(vecs[il][0]));
524 }
525 }
526
527 }
528
529
530
531
532 void IndexIVFFlat::reset()
533 {
534 IndexIVF::reset();
535 for (size_t key = 0; key < nlist; key++) {
536 vecs[key].clear();
537 }
538 }
539
540 long IndexIVFFlat::remove_ids (const IDSelector & sel)
541 {
542 FAISS_THROW_IF_NOT_MSG (!maintain_direct_map,
543 "direct map remove not implemented");
544 long nremove = 0;
545 #pragma omp parallel for reduction(+: nremove)
546 for (long i = 0; i < nlist; i++) {
547 std::vector<idx_t> & idsi = ids[i];
548 float *vecsi = vecs[i].data();
549
550 long l = idsi.size(), j = 0;
551 while (j < l) {
552 if (sel.is_member (idsi[j])) {
553 l--;
554 idsi [j] = idsi [l];
555 memmove (vecsi + j * d,
556 vecsi + l * d, d * sizeof (float));
557 } else {
558 j++;
559 }
560 }
561 if (l < idsi.size()) {
562 nremove += idsi.size() - l;
563 idsi.resize (l);
564 vecs[i].resize (l * d);
565 }
566 }
567 ntotal -= nremove;
568 return nremove;
569 }
570
571
572 void IndexIVFFlat::reconstruct (idx_t key, float * recons) const
573 {
574 FAISS_THROW_IF_NOT_MSG (direct_map.size() == ntotal,
575 "direct map is not initialized");
576 int list_no = direct_map[key] >> 32;
577 int ofs = direct_map[key] & 0xffffffff;
578 memcpy (recons, &vecs[list_no][ofs * d], d * sizeof(recons[0]));
579 }
580
581
582
583
584 /*****************************************
585 * IndexIVFFlatIPBounds implementation
586 ******************************************/
587
588 IndexIVFFlatIPBounds::IndexIVFFlatIPBounds (
589 Index * quantizer, size_t d, size_t nlist,
590 size_t fsize):
591 IndexIVFFlat(quantizer, d, nlist, METRIC_INNER_PRODUCT), fsize(fsize)
592 {
593 part_norms.resize(nlist);
594 }
595
596
597
598 void IndexIVFFlatIPBounds::add_core (idx_t n, const float * x, const long *xids,
599 const long *precomputed_idx) {
600
601 FAISS_THROW_IF_NOT (is_trained);
602 const long * idx;
603 ScopeDeleter<long> del;
604
605 if (precomputed_idx) {
606 idx = precomputed_idx;
607 } else {
608 long * idx0 = new long [n];
609 quantizer->assign (n, x, idx0);
610 idx = idx0;
611 del.set (idx);
612 }
613 IndexIVFFlat::add_core(n, x, xids, idx);
614
615 // compute
616 const float * xi = x + fsize;
617 for (size_t i = 0; i < n; i++) {
618 float norm = std::sqrt (fvec_norm_L2sqr (xi, d - fsize));
619 part_norms[idx[i]].push_back(norm);
620 xi += d;
621 }
622
623
624 }
625
626 namespace {
627
628 void search_bounds_knn_inner_product (
629 const IndexIVFFlatIPBounds & ivf,
630 const float *x,
631 const long *keys,
632 float_minheap_array_t *res,
633 const float *qnorms)
634 {
635
636 size_t k = res->k, nx = res->nh, nprobe = ivf.nprobe;
637 size_t d = ivf.d;
638 int fsize = ivf.fsize;
639
640 size_t nlistv = 0, ndis = 0, npartial = 0;
641
642 #pragma omp parallel for reduction(+: nlistv, ndis, npartial)
643 for (size_t i = 0; i < nx; i++) {
644 const float * xi = x + i * d;
645 const long * keysi = keys + i * nprobe;
646 float qnorm = qnorms[i];
647 float * __restrict simi = res->get_val (i);
648 long * __restrict idxi = res->get_ids (i);
649 minheap_heapify (k, simi, idxi);
650
651 for (size_t ik = 0; ik < nprobe; ik++) {
652 long key = keysi[ik]; /* select the list */
653 if (key < 0) {
654 // not enough centroids for multiprobe
655 continue;
656 }
657 assert (key < (long) ivf.nlist);
658 nlistv++;
659
660 const size_t list_size = ivf.ids[key].size();
661 const float * yj = ivf.vecs[key].data();
662 const float * bnorms = ivf.part_norms[key].data();
663
664 for (size_t j = 0; j < list_size; j++) {
665 float ip_part = fvec_inner_product (xi, yj, fsize);
666 float bound = ip_part + bnorms[j] * qnorm;
667
668 if (bound > simi[0]) {
669 float ip = ip_part + fvec_inner_product (
670 xi + fsize, yj + fsize, d - fsize);
671 if (ip > simi[0]) {
672 minheap_pop (k, simi, idxi);
673 minheap_push (k, simi, idxi, ip, ivf.ids[key][j]);
674 }
675 ndis ++;
676 }
677 yj += d;
678 }
679 npartial += list_size;
680 }
681 minheap_reorder (k, simi, idxi);
682 }
683 indexIVFFlat_stats.nq += nx;
684 indexIVFFlat_stats.nlist += nlistv;
685 indexIVFFlat_stats.ndis += ndis;
686 indexIVFFlat_stats.npartial += npartial;
687 }
688
689
690 }
691
692
693 void IndexIVFFlatIPBounds::search (
694 idx_t n, const float *x, idx_t k,
695 float *distances, idx_t *labels) const
696 {
697 // compute query remainder norms and distances
698 idx_t * idx = new idx_t [n * nprobe];
699 ScopeDeleter<idx_t> del (idx);
700 quantizer->assign (n, x, idx, nprobe);
701
702 float * qnorms = new float [n];
703 ScopeDeleter <float> del2 (qnorms);
704
705 #pragma omp parallel for
706 for (size_t i = 0; i < n; i++) {
707 qnorms[i] = std::sqrt (fvec_norm_L2sqr (
708 x + i * d + fsize, d - fsize));
709 }
710
711 float_minheap_array_t res = {
712 size_t(n), size_t(k), labels, distances};
713
714 search_bounds_knn_inner_product (*this, x, idx, &res, qnorms);
715
716 }
717
718 } // namespace faiss
faiss::IndexIVF
Definition: IndexIVF.h:45
faiss::IndexIVFFlat::search_preassigned
void search_preassigned(idx_t n, const float *x, idx_t k, const idx_t *assign, float *distances, idx_t *labels) const
perform search, without computing the assignment to the quantizer
Definition: IndexIVF.cpp:382
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::IndexIVFFlat::search_knn_L2sqr
void search_knn_L2sqr(size_t nx, const float *x, const long *keys, float_maxheap_array_t *res) const
Implementation of the search for the L2 metric.
Definition: IndexIVF.cpp:322
faiss::HeapArray::get_val
T * get_val(size_t key)
Return the list of values for a heap.
Definition: Heap.h:360
faiss::IndexIVF::imbalance_factor
double imbalance_factor() const
1= perfectly balanced, &gt;1: imbalanced
Definition: IndexIVF.cpp:139
faiss::Index::reset
virtual void reset()=0
removes all elements from the database.
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:572
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:400
faiss::IndexIVFFlat::copy_subset_to
void copy_subset_to(IndexIVFFlat &other, int subset_type, long a1, long a2) const
Definition: IndexIVF.cpp:462
faiss::IndexIVFFlat::merge_from_residuals
void merge_from_residuals(IndexIVF &other) override
Definition: IndexIVF.cpp:450
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:131
faiss::HeapArray::k
size_t k
allocated size per heap
Definition: Heap.h:355
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::IndexIVFFlat::remove_ids
long remove_ids(const IDSelector &sel) override
Definition: IndexIVF.cpp:540
faiss::IndexIVFFlat
Definition: IndexIVF.h:132
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:102
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:215
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::IndexIVFFlat::reset
void reset() override
removes all elements from the database.
Definition: IndexIVF.cpp:532
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:93
faiss::RangeSearchPartialResult::new_result
QueryResult & new_result(idx_t qno)
begin a new result
Definition: AuxIndexStructures.cpp:113
faiss::IndexIVFFlat::update_vectors
void update_vectors(int nv, idx_t *idx, const float *v)
Definition: IndexIVF.cpp:487
faiss::IndexIVFFlatIPBounds::search
void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels) const override
Definition: IndexIVF.cpp:693
faiss::IndexIVFFlatIPBounds::part_norms
std::vector< std::vector< float > > part_norms
norm of remainder (dimensions fsize:d)
Definition: IndexIVF.h:213
faiss::fvec_norm_L2sqr
float fvec_norm_L2sqr(const float *x, size_t d)
Definition: utils.cpp:538
faiss::IndexIVFFlatIPBounds
Definition: IndexIVF.h:207
faiss::IndexIVFFlatIPBounds::fsize
size_t fsize
nb of dimensions of pre-filter
Definition: IndexIVF.h:210
faiss::RangeSearchPartialResult
the entries in the buffers are split per query
Definition: AuxIndexStructures.h:139
faiss::RangeSearchResult
Definition: AuxIndexStructures.h:29
faiss::IndexIVF::merge_from_residuals
virtual void merge_from_residuals(IndexIVF &other)=0
faiss::IndexIVF::make_direct_map
void make_direct_map(bool new_maintain_direct_map=true)
Definition: IndexIVF.cpp:68
faiss::HeapArray::get_ids
TI * get_ids(size_t key)
Correspponding identifiers.
Definition: Heap.h:363
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:148
faiss::IndexIVFFlatIPBounds::add_core
void add_core(idx_t n, const float *x, const long *xids, const long *precomputed_idx) override
same as add_with_ids, with precomputed coarse quantizer
Definition: IndexIVF.cpp:598
faiss::HeapArray::nh
size_t nh
number of heaps
Definition: Heap.h:354
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:63
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::IndexIVFFlat::search_knn_inner_product
void search_knn_inner_product(size_t nx, const float *x, const long *keys, float_minheap_array_t *res) const
Implementation of the search for the inner product metric.
Definition: IndexIVF.cpp:271
faiss::IndexIVF::maintain_direct_map
bool maintain_direct_map
map for direct access to the elements. Enables reconstruct().
Definition: IndexIVF.h:58
faiss::ClusteringParameters::spherical
bool spherical
do we want normalized centroids?
Definition: Clustering.h:29
faiss::IndexIVF::merge_from
virtual void merge_from(IndexIVF &other, idx_t add_id)
Definition: IndexIVF.cpp:168
faiss::MetricType
MetricType
Some algorithms support both an inner product vetsion and a L2 search version.
Definition: Index.h:43
faiss::IndexIVFFlat::vecs
std::vector< std::vector< float > > vecs
Definition: IndexIVF.h:135
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:220
faiss::IndexIVFFlat::search
void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels) const override
Definition: IndexIVF.cpp:372