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