Faiss

- Main Page
- Namespaces
- Classes
- Files

- File List

All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends
/data/users/matthijs/github_faiss/faiss/AutoTune.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 implementation of Hyper-parameter auto-tuning
11 */
12
13 #include "AutoTune.h"
14
15 #include "FaissAssert.h"
16 #include "utils.h"
17
18 #include "IndexFlat.h"
19 #include "VectorTransform.h"
20 #include "IndexLSH.h"
21 #include "IndexPQ.h"
22 #include "IndexIVF.h"
23 #include "IndexIVFPQ.h"
24 #include "MetaIndexes.h"
25 #include "IndexScalarQuantizer.h"
26
27
28 namespace faiss {
29
30
31 AutoTuneCriterion::AutoTuneCriterion (idx_t nq, idx_t nnn):
32 nq (nq), nnn (nnn), gt_nnn (0)
33 {}
34
35
36 void AutoTuneCriterion::set_groundtruth (
37 int gt_nnn, const float *gt_D_in, const idx_t *gt_I_in)
38 {
39 this->gt_nnn = gt_nnn;
40 if (gt_D_in) { // allow null for this, as it is often not used
41 gt_D.resize (nq * gt_nnn);
42 memcpy (gt_D.data(), gt_D_in, sizeof (gt_D[0]) * nq * gt_nnn);
43 }
44 gt_I.resize (nq * gt_nnn);
45 memcpy (gt_I.data(), gt_I_in, sizeof (gt_I[0]) * nq * gt_nnn);
46 }
47
48
49
50 OneRecallAtRCriterion::OneRecallAtRCriterion (idx_t nq, idx_t R):
51 AutoTuneCriterion(nq, R), R(R)
52 {}
53
54 double OneRecallAtRCriterion::evaluate(const float* /*D*/, const idx_t* I)
55 const {
56 FAISS_THROW_IF_NOT_MSG(
57 (gt_I.size() == gt_nnn * nq && gt_nnn >= 1 && nnn >= R),
58 "ground truth not initialized");
59 idx_t n_ok = 0;
60 for (idx_t q = 0; q < nq; q++) {
61 idx_t gt_nn = gt_I[q * gt_nnn];
62 const idx_t* I_line = I + q * nnn;
63 for (int i = 0; i < R; i++) {
64 if (I_line[i] == gt_nn) {
65 n_ok++;
66 break;
67 }
68 }
69 }
70 return n_ok / double(nq);
71 }
72
73
74 IntersectionCriterion::IntersectionCriterion (idx_t nq, idx_t R):
75 AutoTuneCriterion(nq, R), R(R)
76 {}
77
78 double IntersectionCriterion::evaluate(const float* /*D*/, const idx_t* I)
79 const {
80 FAISS_THROW_IF_NOT_MSG(
81 (gt_I.size() == gt_nnn * nq && gt_nnn >= R && nnn >= R),
82 "ground truth not initialized");
83 long n_ok = 0;
84 #pragma omp parallel for reduction(+: n_ok)
85 for (idx_t q = 0; q < nq; q++) {
86 n_ok += ranklist_intersection_size (
87 R, &gt_I [q * gt_nnn],
88 R, I + q * nnn);
89 }
90 return n_ok / double (nq * R);
91 }
92
93 /***************************************************************
94 * OperatingPoints
95 ***************************************************************/
96
97 OperatingPoints::OperatingPoints ()
98 {
99 clear();
100 }
101
102 void OperatingPoints::clear ()
103 {
104 all_pts.clear();
105 optimal_pts.clear();
106 /// default point: doing nothing gives 0 performance and takes 0 time
107 OperatingPoint op = {0, 0, "", -1};
108 optimal_pts.push_back(op);
109 }
110
111 /// add a performance measure
112 bool OperatingPoints::add (double perf, double t, const std::string & key,
113 size_t cno)
114 {
115 OperatingPoint op = {perf, t, key, long(cno)};
116 all_pts.push_back (op);
117 if (perf == 0) {
118 return false; // no method for 0 accuracy is faster than doing nothing
119 }
120 std::vector<OperatingPoint> & a = optimal_pts;
121 if (perf > a.back().perf) {
122 // keep unconditionally
123 a.push_back (op);
124 } else if (perf == a.back().perf) {
125 if (t < a.back ().t) {
126 a.back() = op;
127 } else {
128 return false;
129 }
130 } else {
131 int i;
132 // stricto sensu this should be a bissection
133 for (i = 0; i < a.size(); i++) {
134 if (a[i].perf >= perf) break;
135 }
136 assert (i < a.size());
137 if (t < a[i].t) {
138 if (a[i].perf == perf) {
139 a[i] = op;
140 } else {
141 a.insert (a.begin() + i, op);
142 }
143 } else {
144 return false;
145 }
146 }
147 { // remove non-optimal points from array
148 int i = a.size() - 1;
149 while (i > 0) {
150 if (a[i].t < a[i - 1].t)
151 a.erase (a.begin() + (i - 1));
152 i--;
153 }
154 }
155 return true;
156 }
157
158
159 int OperatingPoints::merge_with (const OperatingPoints &other,
160 const std::string & prefix)
161 {
162 int n_add = 0;
163 for (int i = 0; i < other.all_pts.size(); i++) {
164 const OperatingPoint & op = other.all_pts[i];
165 if (add (op.perf, op.t, prefix + op.key, op.cno))
166 n_add++;
167 }
168 return n_add;
169 }
170
171
172
173 /// get time required to obtain a given performance measure
174 double OperatingPoints::t_for_perf (double perf) const
175 {
176 const std::vector<OperatingPoint> & a = optimal_pts;
177 if (perf > a.back().perf) return 1e50;
178 int i0 = -1, i1 = a.size() - 1;
179 while (i0 + 1 < i1) {
180 int imed = (i0 + i1 + 1) / 2;
181 if (a[imed].perf < perf) i0 = imed;
182 else i1 = imed;
183 }
184 return a[i1].t;
185 }
186
187
188 void OperatingPoints::all_to_gnuplot (const char *fname) const
189 {
190 FILE *f = fopen(fname, "w");
191 if (!f) {
192 fprintf (stderr, "cannot open %s", fname);
193 perror("");
194 abort();
195 }
196 for (int i = 0; i < all_pts.size(); i++) {
197 const OperatingPoint & op = all_pts[i];
198 fprintf (f, "%g %g %s\n", op.perf, op.t, op.key.c_str());
199 }
200 fclose(f);
201 }
202
203 void OperatingPoints::optimal_to_gnuplot (const char *fname) const
204 {
205 FILE *f = fopen(fname, "w");
206 if (!f) {
207 fprintf (stderr, "cannot open %s", fname);
208 perror("");
209 abort();
210 }
211 double prev_perf = 0.0;
212 for (int i = 0; i < optimal_pts.size(); i++) {
213 const OperatingPoint & op = optimal_pts[i];
214 fprintf (f, "%g %g\n", prev_perf, op.t);
215 fprintf (f, "%g %g %s\n", op.perf, op.t, op.key.c_str());
216 prev_perf = op.perf;
217 }
218 fclose(f);
219 }
220
221 void OperatingPoints::display (bool only_optimal) const
222 {
223 const std::vector<OperatingPoint> &pts =
224 only_optimal ? optimal_pts : all_pts;
225 printf("Tested %ld operating points, %ld ones are optimal:\n",
226 all_pts.size(), optimal_pts.size());
227
228 for (int i = 0; i < pts.size(); i++) {
229 const OperatingPoint & op = pts[i];
230 const char *star = "";
231 if (!only_optimal) {
232 for (int j = 0; j < optimal_pts.size(); j++) {
233 if (op.cno == optimal_pts[j].cno) {
234 star = "*";
235 break;
236 }
237 }
238 }
239 printf ("cno=%ld key=%s perf=%.4f t=%.3f %s\n",
240 op.cno, op.key.c_str(), op.perf, op.t, star);
241 }
242
243 }
244
245 /***************************************************************
246 * ParameterSpace
247 ***************************************************************/
248
249 ParameterSpace::ParameterSpace ():
250 verbose (1), n_experiments (500),
251 batchsize (1<<30), thread_over_batches (false)
252 {
253 }
254
255 /* not keeping this constructor as inheritors will call the parent
256 initialize()
257 */
258
259 #if 0
260 ParameterSpace::ParameterSpace (Index *index):
261 verbose (1), n_experiments (500),
262 batchsize (1<<30), thread_over_batches (false)
263 {
264 initialize(index);
265 }
266 #endif
267
268 size_t ParameterSpace::n_combinations () const
269 {
270 size_t n = 1;
271 for (int i = 0; i < parameter_ranges.size(); i++)
272 n *= parameter_ranges[i].values.size();
273 return n;
274 }
275
276 /// get string representation of the combination
277 std::string ParameterSpace::combination_name (size_t cno) const {
278 char buf[1000], *wp = buf;
279 *wp = 0;
280 for (int i = 0; i < parameter_ranges.size(); i++) {
281 const ParameterRange & pr = parameter_ranges[i];
282 size_t j = cno % pr.values.size();
283 cno /= pr.values.size();
284 wp += snprintf (
285 wp, buf + 1000 - wp, "%s%s=%g", i == 0 ? "" : ",",
286 pr.name.c_str(), pr.values[j]);
287 }
288 return std::string (buf);
289 }
290
291
292 bool ParameterSpace::combination_ge (size_t c1, size_t c2) const
293 {
294 for (int i = 0; i < parameter_ranges.size(); i++) {
295 int nval = parameter_ranges[i].values.size();
296 size_t j1 = c1 % nval;
297 size_t j2 = c2 % nval;
298 if (!(j1 >= j2)) return false;
299 c1 /= nval;
300 c2 /= nval;
301 }
302 return true;
303 }
304
305
306
307 #define DC(classname) \
308 const classname *ix = dynamic_cast<const classname *>(index)
309
310 static void init_pq_ParameterRange (const ProductQuantizer & pq,
311 ParameterRange & pr)
312 {
313 if (pq.code_size % 4 == 0) {
314 // Polysemous not supported for code sizes that are not a
315 // multiple of 4
316 for (int i = 2; i <= pq.code_size * 8 / 2; i+= 2)
317 pr.values.push_back(i);
318 }
319 pr.values.push_back (pq.code_size * 8);
320 }
321
322 ParameterRange &ParameterSpace::add_range(const char * name)
323 {
324 parameter_ranges.push_back (ParameterRange ());
325 parameter_ranges.back ().name = name;
326 return parameter_ranges.back ();
327 }
328
329
330 /// initialize with reasonable parameters for the index
331 void ParameterSpace::initialize (const Index * index)
332 {
333 if (DC (IndexPreTransform)) {
334 index = ix->index;
335 }
336 if (DC (IndexRefineFlat)) {
337 ParameterRange & pr = add_range("k_factor_rf");
338 for (int i = 0; i <= 6; i++) {
339 pr.values.push_back (1 << i);
340 }
341 index = ix->base_index;
342 }
343 if (DC (IndexPreTransform)) {
344 index = ix->index;
345 }
346
347 if (DC (IndexIVF)) {
348 ParameterRange & pr = add_range("nprobe");
349 for (int i = 0; i < 13; i++) {
350 size_t nprobe = 1 << i;
351 if (nprobe >= ix->nlist) break;
352 pr.values.push_back (nprobe);
353 }
354 }
355 if (DC (IndexPQ)) {
356 ParameterRange & pr = add_range("ht");
357 init_pq_ParameterRange (ix->pq, pr);
358 }
359 if (DC (IndexIVFPQ)) {
360 ParameterRange & pr = add_range("ht");
361 init_pq_ParameterRange (ix->pq, pr);
362
363 const MultiIndexQuantizer *miq =
364 dynamic_cast<const MultiIndexQuantizer *> (ix->quantizer);
365 if (miq) {
366 ParameterRange & pr_max_codes = add_range("max_codes");
367 for (int i = 8; i < 20; i++) {
368 pr_max_codes.values.push_back (1 << i);
369 }
370 pr_max_codes.values.push_back (1.0 / 0.0);
371 }
372 }
373 if (DC (IndexIVFPQR)) {
374 assert (ix);
375 ParameterRange & pr = add_range("k_factor");
376 for (int i = 0; i <= 6; i++) {
377 pr.values.push_back (1 << i);
378 }
379 }
380 }
381
382 #undef DC
383
384 // non-const version
385 #define DC(classname) classname *ix = dynamic_cast<classname *>(index)
386
387
388 /// set a combination of parameters on an index
389 void ParameterSpace::set_index_parameters (Index *index, size_t cno) const
390 {
391
392 for (int i = 0; i < parameter_ranges.size(); i++) {
393 const ParameterRange & pr = parameter_ranges[i];
394 size_t j = cno % pr.values.size();
395 cno /= pr.values.size();
396 double val = pr.values [j];
397 set_index_parameter (index, pr.name, val);
398 }
399 }
400
401 /// set a combination of parameters on an index
402 void ParameterSpace::set_index_parameters (
403 Index *index, const char *description_in) const
404 {
405 char description[strlen(description_in) + 1];
406 char *ptr;
407 memcpy (description, description_in, strlen(description_in) + 1);
408
409 for (char *tok = strtok_r (description, " ,", &ptr);
410 tok;
411 tok = strtok_r (nullptr, " ,", &ptr)) {
412 char name[100];
413 double val;
414 int ret = sscanf (tok, "%100[^=]=%lf", name, &val);
415 FAISS_THROW_IF_NOT_FMT (
416 ret == 2, "could not interpret parameters %s", tok);
417 set_index_parameter (index, name, val);
418 }
419
420 }
421
422 void ParameterSpace::set_index_parameter (
423 Index * index, const std::string & name, double val) const
424 {
425 if (verbose > 1)
426 printf(" set %s=%g\n", name.c_str(), val);
427
428 if (name == "verbose") {
429 index->verbose = int(val);
430 }
431 if (DC (IndexPreTransform)) {
432 index = ix->index;
433 }
434 if (name == "verbose") {
435 index->verbose = int(val);
436 }
437 if (DC (IndexRefineFlat)) {
438 if (name == "k_factor_rf") {
439 ix->k_factor = int(val);
440 return;
441 }
442 index = ix->base_index;
443 }
444 if (DC (IndexPreTransform)) {
445 index = ix->index;
446 }
447 if (name == "verbose") {
448 index->verbose = int(val);
449 return; // last verbose that we could find
450 }
451 if (name == "nprobe") {
452 DC(IndexIVF);
453 ix->nprobe = int(val);
454 } else if (name == "ht") {
455 if (DC (IndexPQ)) {
456 if (val >= ix->pq.code_size * 8) {
457 ix->search_type = IndexPQ::ST_PQ;
458 } else {
459 ix->search_type = IndexPQ::ST_polysemous;
460 ix->polysemous_ht = int(val);
461 }
462 } else if (DC (IndexIVFPQ)) {
463 if (val >= ix->pq.code_size * 8) {
464 ix->polysemous_ht = 0;
465 } else {
466 ix->polysemous_ht = int(val);
467 }
468 }
469 } else if (name == "k_factor") {
470 DC (IndexIVFPQR);
471 ix->k_factor = val;
472 } else if (name == "max_codes") {
473 DC (IndexIVFPQ);
474 ix->max_codes = finite(val) ? size_t(val) : 0;
475 } else {
476 FAISS_THROW_FMT (
477 "ParameterSpace::set_index_parameter:"
478 "could not set parameter %s",
479 name.c_str());
480 }
481 }
482
483 void ParameterSpace::display () const
484 {
485 printf ("ParameterSpace, %ld parameters, %ld combinations:\n",
486 parameter_ranges.size (), n_combinations ());
487 for (int i = 0; i < parameter_ranges.size(); i++) {
488 const ParameterRange & pr = parameter_ranges[i];
489 printf (" %s: ", pr.name.c_str ());
490 char sep = '[';
491 for (int j = 0; j < pr.values.size(); j++) {
492 printf ("%c %g", sep, pr.values [j]);
493 sep = ',';
494 }
495 printf ("]\n");
496 }
497 }
498
499
500
501 void ParameterSpace::update_bounds (size_t cno, const OperatingPoint & op,
502 double *upper_bound_perf,
503 double *lower_bound_t) const
504 {
505 if (combination_ge (cno, op.cno)) {
506 if (op.t > *lower_bound_t) *lower_bound_t = op.t;
507 }
508 if (combination_ge (op.cno, cno)) {
509 if (op.perf < *upper_bound_perf) *upper_bound_perf = op.perf;
510 }
511 }
512
513
514
515 void ParameterSpace::explore (Index *index,
516 size_t nq, const float *xq,
517 const AutoTuneCriterion & crit,
518 OperatingPoints * ops) const
519 {
520 FAISS_THROW_IF_NOT_MSG (nq == crit.nq,
521 "criterion does not have the same nb of queries");
522
523 size_t n_comb = n_combinations ();
524
525 if (n_experiments == 0) {
526
527 for (size_t cno = 0; cno < n_comb; cno++) {
528 set_index_parameters (index, cno);
529 std::vector<Index::idx_t> I(nq * crit.nnn);
530 std::vector<float> D(nq * crit.nnn);
531
532 double t0 = getmillisecs ();
533 index->search (nq, xq, crit.nnn, D.data(), I.data());
534 double t_search = (getmillisecs() - t0) / 1e3;
535
536 double perf = crit.evaluate (D.data(), I.data());
537
538 bool keep = ops->add (perf, t_search, combination_name (cno), cno);
539
540 if (verbose)
541 printf(" %ld/%ld: %s perf=%.3f t=%.3f s %s\n", cno, n_comb,
542 combination_name (cno).c_str(), perf, t_search,
543 keep ? "*" : "");
544 }
545 return;
546 }
547
548 int n_exp = n_experiments;
549
550 if (n_exp > n_comb) n_exp = n_comb;
551 FAISS_THROW_IF_NOT (n_comb == 1 || n_exp > 2);
552 std::vector<int> perm (n_comb);
553 // make sure the slowest and fastest experiment are run
554 perm[0] = 0;
555 if (n_comb > 1) {
556 perm[1] = n_comb - 1;
557 rand_perm (&perm[2], n_comb - 2, 1234);
558 for (int i = 2; i < perm.size(); i++) perm[i] ++;
559 }
560
561 for (size_t xp = 0; xp < n_exp; xp++) {
562 size_t cno = perm[xp];
563
564 if (verbose)
565 printf(" %ld/%d: cno=%ld %s ", xp, n_exp, cno,
566 combination_name (cno).c_str());
567
568 {
569 double lower_bound_t = 0.0;
570 double upper_bound_perf = 1.0;
571 for (int i = 0; i < ops->all_pts.size(); i++) {
572 update_bounds (cno, ops->all_pts[i],
573 &upper_bound_perf, &lower_bound_t);
574 }
575 double best_t = ops->t_for_perf (upper_bound_perf);
576 if (verbose)
577 printf ("bounds [perf<=%.3f t>=%.3f] %s",
578 upper_bound_perf, lower_bound_t,
579 best_t <= lower_bound_t ? "skip\n" : "");
580 if (best_t <= lower_bound_t) continue;
581 }
582
583 set_index_parameters (index, cno);
584 std::vector<Index::idx_t> I(nq * crit.nnn);
585 std::vector<float> D(nq * crit.nnn);
586
587 double t0 = getmillisecs ();
588
589 if (thread_over_batches) {
590 #pragma omp parallel for
591 for (size_t q0 = 0; q0 < nq; q0 += batchsize) {
592 size_t q1 = q0 + batchsize;
593 if (q1 > nq) q1 = nq;
594 index->search (q1 - q0, xq + q0 * index->d,
595 crit.nnn,
596 D.data() + q0 * crit.nnn,
597 I.data() + q0 * crit.nnn);
598 }
599 } else {
600 for (size_t q0 = 0; q0 < nq; q0 += batchsize) {
601 size_t q1 = q0 + batchsize;
602 if (q1 > nq) q1 = nq;
603 index->search (q1 - q0, xq + q0 * index->d,
604 crit.nnn,
605 D.data() + q0 * crit.nnn,
606 I.data() + q0 * crit.nnn);
607 }
608 }
609
610 double t_search = (getmillisecs() - t0) / 1e3;
611
612 double perf = crit.evaluate (D.data(), I.data());
613
614 bool keep = ops->add (perf, t_search, combination_name (cno), cno);
615
616 if (verbose)
617 printf(" perf %.3f t %.3f %s\n", perf, t_search,
618 keep ? "*" : "");
619 }
620 }
621
622 /***************************************************************
623 * index_factory
624 ***************************************************************/
625
626 namespace {
627
628 struct VTChain {
629 std::vector<VectorTransform *> chain;
630 ~VTChain () {
631 for (int i = 0; i < chain.size(); i++) {
632 delete chain[i];
633 }
634 }
635 };
636
637 }
638
639 Index *index_factory (int d, const char *description_in, MetricType metric)
640 {
641 VTChain vts;
642 Index *coarse_quantizer = nullptr;
643 Index *index = nullptr;
644 bool add_idmap = false;
645 bool make_IndexRefineFlat = false;
646
647 ScopeDeleter1<Index> del_coarse_quantizer, del_index;
648
649 char description[strlen(description_in) + 1];
650 char *ptr;
651 memcpy (description, description_in, strlen(description_in) + 1);
652
653 int ncentroids = -1;
654
655 for (char *tok = strtok_r (description, " ,", &ptr);
656 tok;
657 tok = strtok_r (nullptr, " ,", &ptr)) {
658 int d_out, opq_M, nbit, M, M2;
659 std::string stok(tok);
660
661 // to avoid mem leaks with exceptions:
662 // do all tests before any instanciation
663
664 VectorTransform *vt_1 = nullptr;
665 Index *coarse_quantizer_1 = nullptr;
666 Index *index_1 = nullptr;
667
668 // VectorTransforms
669 if (sscanf (tok, "PCA%d", &d_out) == 1) {
670 vt_1 = new PCAMatrix (d, d_out);
671 d = d_out;
672 } else if (sscanf (tok, "PCAR%d", &d_out) == 1) {
673 vt_1 = new PCAMatrix (d, d_out, 0, true);
674 d = d_out;
675 } else if (sscanf (tok, "PCAW%d", &d_out) == 1) {
676 vt_1 = new PCAMatrix (d, d_out, -0.5, false);
677 d = d_out;
678 } else if (sscanf (tok, "PCAWR%d", &d_out) == 1) {
679 vt_1 = new PCAMatrix (d, d_out, -0.5, true);
680 d = d_out;
681 } else if (sscanf (tok, "OPQ%d_%d", &opq_M, &d_out) == 2) {
682 vt_1 = new OPQMatrix (d, opq_M, d_out);
683 d = d_out;
684 } else if (sscanf (tok, "OPQ%d", &opq_M) == 1) {
685 vt_1 = new OPQMatrix (d, opq_M);
686 } else if (stok == "L2norm") {
687 vt_1 = new NormalizationTransform (d, 2.0);
688
689 // coarse quantizers
690 } else if (!coarse_quantizer &&
691 sscanf (tok, "IVF%d", &ncentroids) == 1) {
692 if (metric == METRIC_L2) {
693 coarse_quantizer_1 = new IndexFlatL2 (d);
694 } else { // if (metric == METRIC_IP)
695 coarse_quantizer_1 = new IndexFlatIP (d);
696 }
697 } else if (!coarse_quantizer && sscanf (tok, "IMI2x%d", &nbit) == 1) {
698 FAISS_THROW_IF_NOT_MSG (metric == METRIC_L2,
699 "MultiIndex not implemented for inner prod search");
700 coarse_quantizer_1 = new MultiIndexQuantizer (d, 2, nbit);
701 ncentroids = 1 << (2 * nbit);
702 } else if (stok == "IDMap") {
703 add_idmap = true;
704
705 // IVFs
706 } else if (!index && stok == "Flat") {
707 if (coarse_quantizer) {
708 // if there was an IVF in front, then it is an IVFFlat
709 IndexIVF *index_ivf = new IndexIVFFlat (
710 coarse_quantizer, d, ncentroids, metric);
711 index_ivf->quantizer_trains_alone =
712 dynamic_cast<MultiIndexQuantizer*>(coarse_quantizer)
713 != nullptr;
714 index_ivf->cp.spherical = metric == METRIC_INNER_PRODUCT;
715 del_coarse_quantizer.release ();
716 index_ivf->own_fields = true;
717 index_1 = index_ivf;
718 } else {
719 index_1 = new IndexFlat (d, metric);
720 }
721 } else if (!index && (stok == "SQ8" || stok == "SQ4")) {
722 ScalarQuantizer::QuantizerType qt =
723 stok == "SQ8" ? ScalarQuantizer::QT_8bit :
724 stok == "SQ4" ? ScalarQuantizer::QT_4bit :
725 ScalarQuantizer::QT_4bit;
726 if (coarse_quantizer) {
727 IndexIVFScalarQuantizer *index_ivf =
728 new IndexIVFScalarQuantizer (
729 coarse_quantizer, d, ncentroids, qt, metric);
730 index_ivf->quantizer_trains_alone =
731 dynamic_cast<MultiIndexQuantizer*>(coarse_quantizer)
732 != nullptr;
733 del_coarse_quantizer.release ();
734 index_ivf->own_fields = true;
735 index_1 = index_ivf;
736 } else {
737 index_1 = new IndexScalarQuantizer (d, qt, metric);
738 }
739 } else if (!index && sscanf (tok, "PQ%d+%d", &M, &M2) == 2) {
740 FAISS_THROW_IF_NOT_MSG(coarse_quantizer,
741 "PQ with + works only with an IVF");
742 FAISS_THROW_IF_NOT_MSG(metric == METRIC_L2,
743 "IVFPQR not implemented for inner product search");
744 IndexIVFPQR *index_ivf = new IndexIVFPQR (
745 coarse_quantizer, d, ncentroids, M, 8, M2, 8);
746 index_ivf->quantizer_trains_alone =
747 dynamic_cast<MultiIndexQuantizer*>(coarse_quantizer)
748 != nullptr;
749 del_coarse_quantizer.release ();
750 index_ivf->own_fields = true;
751 index_1 = index_ivf;
752 } else if (!index && sscanf (tok, "PQ%d", &M) == 1) {
753 if (coarse_quantizer) {
754 IndexIVFPQ *index_ivf = new IndexIVFPQ (
755 coarse_quantizer, d, ncentroids, M, 8);
756 index_ivf->quantizer_trains_alone =
757 dynamic_cast<MultiIndexQuantizer*>(coarse_quantizer)
758 != nullptr;
759 index_ivf->metric_type = metric;
760 index_ivf->cp.spherical = metric == METRIC_INNER_PRODUCT;
761 del_coarse_quantizer.release ();
762 index_ivf->own_fields = true;
763 index_ivf->do_polysemous_training = true;
764 index_1 = index_ivf;
765 } else {
766 IndexPQ *index_pq = new IndexPQ (d, M, 8, metric);
767 index_pq->do_polysemous_training = true;
768 index_1 = index_pq;
769 }
770 } else if (stok == "RFlat") {
771 make_IndexRefineFlat = true;
772 } else {
773 FAISS_THROW_FMT( "could not parse token \"%s\" in %s\n",
774 tok, description_in);
775 }
776
777 if (index_1 && add_idmap) {
778 IndexIDMap *idmap = new IndexIDMap(index_1);
779 del_index.set (idmap);
780 idmap->own_fields = true;
781 index_1 = idmap;
782 add_idmap = false;
783 }
784
785 if (vt_1) {
786 vts.chain.push_back (vt_1);
787 }
788
789 if (coarse_quantizer_1) {
790 coarse_quantizer = coarse_quantizer_1;
791 del_coarse_quantizer.set (coarse_quantizer);
792 }
793
794 if (index_1) {
795 index = index_1;
796 del_index.set (index);
797 }
798 }
799
800 FAISS_THROW_IF_NOT_FMT(index, "descrption %s did not generate an index",
801 description_in);
802
803 // nothing can go wrong now
804 del_index.release ();
805 del_coarse_quantizer.release ();
806
807 if (add_idmap) {
808 fprintf(stderr, "index_factory: WARNING: "
809 "IDMap option not used\n");
810 }
811
812 if (vts.chain.size() > 0) {
813 IndexPreTransform *index_pt = new IndexPreTransform (index);
814 index_pt->own_fields = true;
815 // add from back
816 while (vts.chain.size() > 0) {
817 index_pt->prepend_transform (vts.chain.back());
818 vts.chain.pop_back ();
819 }
820 index = index_pt;
821 }
822
823 if (make_IndexRefineFlat) {
824 IndexRefineFlat *index_rf = new IndexRefineFlat (index);
825 index_rf->own_fields = true;
826 index = index_rf;
827 }
828
829 return index;
830 }
831
832
833
834
835 }; // namespace faiss
faiss::ParameterSpace::explore
void explore(Index *index, size_t nq, const float *xq, const AutoTuneCriterion &crit, OperatingPoints *ops) const
Definition: AutoTune.cpp:515
faiss::IndexIVF
Definition: IndexIVF.h:45
faiss::ParameterSpace::parameter_ranges
std::vector< ParameterRange > parameter_ranges
all tunable parameters
Definition: AutoTune.h:134
faiss::OperatingPoint::key
std::string key
key that identifies this op pt
Definition: AutoTune.h:89
faiss::ScalarQuantizer::QuantizerType
QuantizerType
Definition: IndexScalarQuantizer.h:32
faiss::IndexFlat
Definition: IndexFlat.h:23
faiss::OperatingPoint::cno
long cno
integer identifer
Definition: AutoTune.h:90
faiss::IndexIVFPQR
Definition: IndexIVFPQ.h:198
faiss::IndexPQ::do_polysemous_training
bool do_polysemous_training
false = standard PQ
Definition: IndexPQ.h:69
faiss::OperatingPoints::clear
void clear()
Definition: AutoTune.cpp:102
faiss::OperatingPoint
Definition: AutoTune.h:86
faiss::IndexScalarQuantizer
Definition: IndexScalarQuantizer.h:82
faiss::OperatingPoints::display
void display(bool only_optimal=true) const
easy-to-read output
Definition: AutoTune.cpp:221
faiss::IndexPQ
Definition: IndexPQ.h:28
faiss::OperatingPoint::perf
double perf
performance measure (output of a Criterion)
Definition: AutoTune.h:87
faiss::ScalarQuantizer::QT_4bit
4 bits per component
Definition: IndexScalarQuantizer.h:34
faiss::OperatingPoints
Definition: AutoTune.h:93
faiss::OperatingPoints::t_for_perf
double t_for_perf(double perf) const
get time required to obtain a given performance measure
Definition: AutoTune.cpp:174
faiss::AutoTuneCriterion::nnn
idx_t nnn
nb of NNs that the query should request
Definition: AutoTune.h:29
faiss::IndexIVF::quantizer_trains_alone
bool quantizer_trains_alone
just pass over the trainset to quantizer
Definition: IndexIVF.h:50
faiss::PCAMatrix
Definition: VectorTransform.h:124
faiss::IndexFlatL2
Definition: IndexFlat.h:79
faiss::OperatingPoints::add
bool add(double perf, double t, const std::string &key, size_t cno=0)
add a performance measure. Return whether it is an optimal point
Definition: AutoTune.cpp:112
faiss::OPQMatrix
Definition: VectorTransform.h:180
faiss::ScopeDeleter1
Definition: FaissException.h:52
faiss::IndexIVFPQ::do_polysemous_training
bool do_polysemous_training
reorder PQ centroids after training?
Definition: IndexIVFPQ.h:35
faiss::ParameterSpace::batchsize
size_t batchsize
maximum number of queries to submit at a time.
Definition: AutoTune.h:145
faiss::AutoTuneCriterion::evaluate
virtual double evaluate(const float *D, const idx_t *I) const =0
faiss::IndexPreTransform
Definition: VectorTransform.h:239
faiss::IndexIDMap
Definition: MetaIndexes.h:26
faiss::AutoTuneCriterion::nq
idx_t nq
nb of queries this criterion is evaluated on
Definition: AutoTune.h:28
faiss::IndexIVFFlat
Definition: IndexIVF.h:132
faiss::OperatingPoints::optimal_pts
std::vector< OperatingPoint > optimal_pts
optimal operating points, sorted by perf
Definition: AutoTune.h:98
faiss::IndexFlatIP
Definition: IndexFlat.h:73
faiss::AutoTuneCriterion::set_groundtruth
void set_groundtruth(int gt_nnn, const float *gt_D_in, const idx_t *gt_I_in)
Definition: AutoTune.cpp:36
faiss::ParameterSpace::add_range
ParameterRange & add_range(const char *name)
add a new parameter
Definition: AutoTune.cpp:322
faiss::IndexRefineFlat
Definition: IndexFlat.h:103
faiss::AutoTuneCriterion::gt_nnn
idx_t gt_nnn
nb of GT NNs required to evaluate crterion
Definition: AutoTune.h:30
faiss::OperatingPoints::all_to_gnuplot
void all_to_gnuplot(const char *fname) const
output to a format easy to digest by gnuplot
Definition: AutoTune.cpp:188
faiss::IndexRefineFlat::own_fields
bool own_fields
should the base index be deallocated?
Definition: IndexFlat.h:110
faiss::Index::d
int d
vector dimension
Definition: Index.h:64
faiss::ProductQuantizer::code_size
size_t code_size
byte per indexed vector
Definition: ProductQuantizer.h:34
faiss::IndexIVFPQ
Definition: IndexIVFPQ.h:29
faiss::IndexIVF::cp
ClusteringParameters cp
to override default clustering params
Definition: IndexIVF.h:53
faiss::ParameterSpace::thread_over_batches
bool thread_over_batches
Definition: AutoTune.h:149
faiss::IndexIVF::own_fields
bool own_fields
whether object owns the quantizer
Definition: IndexIVF.h:51
faiss::OperatingPoints::all_pts
std::vector< OperatingPoint > all_pts
all operating points
Definition: AutoTune.h:95
faiss::ranklist_intersection_size
size_t ranklist_intersection_size(size_t k1, const long *v1, size_t k2, const long *v2_in)
Definition: utils.cpp:1542
faiss::AutoTuneCriterion
Definition: AutoTune.h:26
faiss::Index::verbose
bool verbose
verbosity level
Definition: Index.h:66
faiss::getmillisecs
double getmillisecs()
ms elapsed since some arbitrary epoch
Definition: utils.cpp:70
faiss::AutoTuneCriterion::gt_D
std::vector< float > gt_D
Ground-truth distances (size nq * gt_nnn)
Definition: AutoTune.h:32
faiss::IndexIVFScalarQuantizer
Definition: IndexScalarQuantizer.h:129
faiss::ParameterSpace::combination_name
std::string combination_name(size_t cno) const
get string representation of the combination
Definition: AutoTune.cpp:277
faiss::Index::search
virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels) const =0
faiss::MultiIndexQuantizer
Definition: IndexPQ.h:135
faiss::ParameterSpace::update_bounds
void update_bounds(size_t cno, const OperatingPoint &op, double *upper_bound_perf, double *lower_bound_t) const
Definition: AutoTune.cpp:501
faiss::VectorTransform
Definition: VectorTransform.h:28
faiss::IndexPreTransform::own_fields
bool own_fields
! the sub-index
Definition: VectorTransform.h:244
faiss::ParameterSpace::initialize
virtual void initialize(const Index *index)
initialize with reasonable parameters for the index
Definition: AutoTune.cpp:331
faiss::ParameterSpace::verbose
int verbose
verbosity during exploration
Definition: AutoTune.h:139
faiss::OperatingPoints::merge_with
int merge_with(const OperatingPoints &other, const std::string &prefix="")
add operating points from other to this, with a prefix to the keys
Definition: AutoTune.cpp:159
faiss::ParameterSpace::set_index_parameter
virtual void set_index_parameter(Index *index, const std::string &name, double val) const
set one of the parameters
Definition: AutoTune.cpp:422
faiss::ParameterSpace::n_combinations
size_t n_combinations() const
nb of combinations, = product of values sizes
Definition: AutoTune.cpp:268
faiss::Index::metric_type
MetricType metric_type
type of metric this index uses for search
Definition: Index.h:72
faiss::ParameterSpace::set_index_parameters
void set_index_parameters(Index *index, size_t cno) const
set a combination of parameters on an index
Definition: AutoTune.cpp:389
faiss::ScalarQuantizer::QT_8bit
8 bits per component
Definition: IndexScalarQuantizer.h:33
faiss::Index
Definition: Index.h:60
faiss::IndexPQ::ST_PQ
asymmetric product quantizer (default)
Definition: IndexPQ.h:76
faiss::ParameterSpace::display
void display() const
print a description on stdout
Definition: AutoTune.cpp:483
faiss::IndexPQ::ST_polysemous
HE filter (using ht) + PQ combination.
Definition: IndexPQ.h:80
faiss::ProductQuantizer
Definition: ProductQuantizer.h:25
faiss::NormalizationTransform
Definition: VectorTransform.h:226
faiss::ParameterSpace::combination_ge
bool combination_ge(size_t c1, size_t c2) const
returns whether combinations c1 &gt;= c2 in the tuple sense
Definition: AutoTune.cpp:292
faiss::ClusteringParameters::spherical
bool spherical
do we want normalized centroids?
Definition: Clustering.h:29
faiss::ParameterRange
possible values of a parameter, sorted from least to most expensive/accurate
Definition: AutoTune.h:125
faiss::index_factory
Index * index_factory(int d, const char *description_in, MetricType metric)
Definition: AutoTune.cpp:639
faiss::ParameterSpace::n_experiments
int n_experiments
nb of experiments during optimization (0 = try all combinations)
Definition: AutoTune.h:142
faiss::AutoTuneCriterion::gt_I
std::vector< idx_t > gt_I
Ground-truth indexes (size nq * gt_nnn)
Definition: AutoTune.h:33
faiss::OperatingPoint::t
double t
corresponding execution time (ms)
Definition: AutoTune.h:88
faiss::MetricType
MetricType
Some algorithms support both an inner product vetsion and a L2 search version.
Definition: Index.h:43
faiss::IndexIDMap::own_fields
bool own_fields
! the sub-index
Definition: MetaIndexes.h:28