1 /** 2 * Copyright (c) Facebook, Inc. and its affiliates. 3 * 4 * This source code is licensed under the MIT license found in the 5 * LICENSE file in the root directory of this source tree. 6 */ 7 8 // -*- c++ -*- 9 10 #ifndef INDEX_FLAT_H 11 #define INDEX_FLAT_H 12 13 #include <vector> 14 15 #include <faiss/Index.h> 16 17 namespace faiss { 18 19 /** Index that stores the full vectors and performs exhaustive search */ 20 struct IndexFlat : Index { 21 /// database vectors, size ntotal * d 22 std::vector<float> xb; 23 24 explicit IndexFlat(idx_t d, MetricType metric = METRIC_L2); 25 26 void add(idx_t n, const float* x) override; 27 28 void reset() override; 29 30 void search( 31 idx_t n, 32 const float* x, 33 idx_t k, 34 float* distances, 35 idx_t* labels) const override; 36 37 void range_search( 38 idx_t n, 39 const float* x, 40 float radius, 41 RangeSearchResult* result) const override; 42 43 void reconstruct(idx_t key, float* recons) const override; 44 45 /** compute distance with a subset of vectors 46 * 47 * @param x query vectors, size n * d 48 * @param labels indices of the vectors that should be compared 49 * for each query vector, size n * k 50 * @param distances 51 * corresponding output distances, size n * k 52 */ 53 void compute_distance_subset( 54 idx_t n, 55 const float* x, 56 idx_t k, 57 float* distances, 58 const idx_t* labels) const; 59 60 /** remove some ids. NB that Because of the structure of the 61 * indexing structure, the semantics of this operation are 62 * different from the usual ones: the new ids are shifted */ 63 size_t remove_ids(const IDSelector& sel) override; 64 IndexFlatIndexFlat65 IndexFlat() {} 66 67 DistanceComputer* get_distance_computer() const override; 68 69 /* The stanadlone codec interface (just memcopies in this case) */ 70 size_t sa_code_size() const override; 71 72 void sa_encode(idx_t n, const float* x, uint8_t* bytes) const override; 73 74 void sa_decode(idx_t n, const uint8_t* bytes, float* x) const override; 75 }; 76 77 struct IndexFlatIP : IndexFlat { IndexFlatIPIndexFlatIP78 explicit IndexFlatIP(idx_t d) : IndexFlat(d, METRIC_INNER_PRODUCT) {} IndexFlatIPIndexFlatIP79 IndexFlatIP() {} 80 }; 81 82 struct IndexFlatL2 : IndexFlat { IndexFlatL2IndexFlatL283 explicit IndexFlatL2(idx_t d) : IndexFlat(d, METRIC_L2) {} IndexFlatL2IndexFlatL284 IndexFlatL2() {} 85 }; 86 87 /// optimized version for 1D "vectors". 88 struct IndexFlat1D : IndexFlatL2 { 89 bool continuous_update; ///< is the permutation updated continuously? 90 91 std::vector<idx_t> perm; ///< sorted database indices 92 93 explicit IndexFlat1D(bool continuous_update = true); 94 95 /// if not continuous_update, call this between the last add and 96 /// the first search 97 void update_permutation(); 98 99 void add(idx_t n, const float* x) override; 100 101 void reset() override; 102 103 /// Warn: the distances returned are L1 not L2 104 void search( 105 idx_t n, 106 const float* x, 107 idx_t k, 108 float* distances, 109 idx_t* labels) const override; 110 }; 111 112 } // namespace faiss 113 114 #endif 115