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