Faiss

- Main Page
- Namespaces
- Classes
- Files

- File List

All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends
/data/users/matthijs/github_faiss/faiss/Index.h
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 // -*- c++ -*-
11
12 #ifndef FAISS_INDEX_H
13 #define FAISS_INDEX_H
14
15
16 #include <cstdio>
17 #include <typeinfo>
18 #include <string>
19 #include <sstream>
20
21
22 /**
23 * @namespace faiss
24 *
25 * Throughout the library, vectors are provided as float * pointers.
26 * Most algorithms can be optimized when several vectors are processed
27 * (added/searched) together in a batch. In this case, they are passed
28 * in as a matrix. When n vectors of size d are provided as float * x,
29 * component j of vector i is
30 *
31 * x[ i * d + j ]
32 *
33 * where 0 <= i < n and 0 <= j < d. In other words, matrices are
34 * always compact. When specifying the size of the matrix, we call it
35 * an n*d matrix, which implies a row-major storage.
36 */
37
38
39 namespace faiss {
40
41
42 /// Some algorithms support both an inner product version and a L2 search version.
43 enum MetricType {
44 METRIC_INNER_PRODUCT = 0,
45 METRIC_L2 = 1,
46 };
47
48
49 /// Forward declarations see AuxIndexStructures.h
50 struct IDSelector;
51 struct RangeSearchResult;
52
53 /** Abstract structure for an index
54 *
55 * Supports adding vertices and searching them.
56 *
57 * Currently only asymmetric queries are supported:
58 * database-to-database queries are not implemented.
59 */
60 struct Index {
61
62 typedef long idx_t; ///< all indices are this type
63
64 int d; ///< vector dimension
65 idx_t ntotal; ///< total nb of indexed vectors
66 bool verbose; ///< verbosity level
67
68 /// set if the Index does not require training, or if training is done already
69 bool is_trained;
70
71 /// type of metric this index uses for search
72 MetricType metric_type;
73
74 explicit Index (idx_t d = 0, MetricType metric = METRIC_L2):
75 d(d),
76 ntotal(0),
77 verbose(false),
78 is_trained(true),
79 metric_type (metric) {}
80
81 virtual ~Index ();
82
83
84 /** Perform training on a representative set of vectors
85 *
86 * @param n nb of training vectors
87 * @param x training vecors, size n * d
88 */
89 virtual void train(idx_t n, const float* x);
90
91 /** Add n vectors of dimension d to the index.
92 *
93 * Vectors are implicitly assigned labels ntotal .. ntotal + n - 1
94 * This function slices the input vectors in chuncks smaller than
95 * blocksize_add and calls add_core.
96 * @param x input matrix, size n * d
97 */
98 virtual void add (idx_t n, const float *x) = 0;
99
100 /** Same as add, but stores xids instead of sequential ids.
101 *
102 * The default implementation fails with an assertion, as it is
103 * not supported by all indexes.
104 *
105 * @param xids if non-null, ids to store for the vectors (size n)
106 */
107 virtual void add_with_ids (idx_t n, const float * x, const long *xids);
108
109 /** query n vectors of dimension d to the index.
110 *
111 * return at most k vectors. If there are not enough results for a
112 * query, the result array is padded with -1s.
113 *
114 * @param x input vectors to search, size n * d
115 * @param labels output labels of the NNs, size n*k
116 * @param distances output pairwise distances, size n*k
117 */
118 virtual void search (idx_t n, const float *x, idx_t k,
119 float *distances, idx_t *labels) const = 0;
120
121 /** query n vectors of dimension d to the index.
122 *
123 * return all vectors with distance < radius. Note that many
124 * indexes do not implement the range_search (only the k-NN search
125 * is mandatory).
126 *
127 * @param x input vectors to search, size n * d
128 * @param radius search radius
129 * @param result result table
130 */
131 virtual void range_search (idx_t n, const float *x, float radius,
132 RangeSearchResult *result) const;
133
134 /** return the indexes of the k vectors closest to the query x.
135 *
136 * This function is identical as search but only return labels of neighbors.
137 * @param x input vectors to search, size n * d
138 * @param labels output labels of the NNs, size n*k
139 */
140 void assign (idx_t n, const float * x, idx_t * labels, idx_t k = 1);
141
142 /// removes all elements from the database.
143 virtual void reset() = 0;
144
145 /** removes IDs from the index. Not supported by all indexes
146 */
147 virtual long remove_ids (const IDSelector & sel);
148
149 /** Reconstruct a stored vector (or an approximation if lossy coding)
150 *
151 * this function may not be defined for some indexes
152 * @param key id of the vector to reconstruct
153 * @param recons reconstucted vector (size d)
154 */
155 virtual void reconstruct (idx_t key, float * recons) const;
156
157
158 /** Reconstruct vectors i0 to i0 + ni - 1
159 *
160 * this function may not be defined for some indexes
161 * @param recons reconstucted vector (size ni * d)
162 */
163 virtual void reconstruct_n (idx_t i0, idx_t ni, float *recons) const;
164
165 /** Similar to search, but also reconstructs the stored vectors (or an
166 * approximation in the case of lossy coding) for the search results.
167 *
168 * If there are not enough results for a query, the resulting arrays
169 * is padded with -1s.
170 *
171 * @param recons reconstructed vectors size (n, k, d)
172 **/
173 virtual void search_and_reconstruct (idx_t n, const float *x, idx_t k,
174 float *distances, idx_t *labels,
175 float *recons) const;
176
177 /** Computes a residual vector after indexing encoding.
178 *
179 * The residual vector is the difference between a vector and the
180 * reconstruction that can be decoded from its representation in
181 * the index. The residual can be used for multiple-stage indexing
182 * methods, like IndexIVF's methods.
183 *
184 * @param x input vector, size d
185 * @param residual output residual vector, size d
186 * @param key encoded index, as returned by search and assign
187 */
188 void compute_residual (const float * x, float * residual, idx_t key) const;
189
190 /** Display the actual class name and some more info */
191 void display () const;
192
193
194
195 };
196
197 }
198
199
200 #endif
faiss::Index::reset
virtual void reset()=0
removes all elements from the database.
faiss::Index::search_and_reconstruct
virtual void search_and_reconstruct(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, float *recons) const
Definition: Index.cpp:66
faiss::Index::assign
void assign(idx_t n, const float *x, idx_t *labels, idx_t k=1)
Definition: Index.cpp:34
faiss::IDSelector
Definition: AuxIndexStructures.h:52
faiss::Index::train
virtual void train(idx_t n, const float *x)
Definition: Index.cpp:23
faiss::Index::add_with_ids
virtual void add_with_ids(idx_t n, const float *x, const long *xids)
Definition: Index.cpp:41
faiss::Index::d
int d
vector dimension
Definition: Index.h:64
faiss::Index::reconstruct_n
virtual void reconstruct_n(idx_t i0, idx_t ni, float *recons) const
Definition: Index.cpp:59
faiss::Index::add
virtual void add(idx_t n, const float *x)=0
faiss::Index::idx_t
long idx_t
all indices are this type
Definition: Index.h:62
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::Index::remove_ids
virtual long remove_ids(const IDSelector &sel)
Definition: Index.cpp:48
faiss::Index::search
virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels) const =0
faiss::RangeSearchResult
Definition: AuxIndexStructures.h:29
faiss::Index::display
void display() const
Definition: Index.cpp:94
faiss::Index::metric_type
MetricType metric_type
type of metric this index uses for search
Definition: Index.h:72
faiss::Index
Definition: Index.h:60
faiss::Index::range_search
virtual void range_search(idx_t n, const float *x, float radius, RangeSearchResult *result) const
Definition: Index.cpp:28
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::Index::compute_residual
void compute_residual(const float *x, float *residual, idx_t key) const
Definition: Index.cpp:86
faiss::Index::reconstruct
virtual void reconstruct(idx_t key, float *recons) const
Definition: Index.cpp:54
faiss::MetricType
MetricType
Some algorithms support both an inner product version and a L2 search version.
Definition: Index.h:43