Faiss

- Main Page
- Namespaces
- Classes
- Files

- File List

All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends
/data/users/matthijs/github_faiss/faiss/IndexScalarQuantizer.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 #ifndef FAISS_INDEX_SCALAR_QUANTIZER_H
10 #define FAISS_INDEX_SCALAR_QUANTIZER_H
11
12 #include <stdint.h>
13
14
15 #include <vector>
16
17
18 #include "IndexIVF.h"
19
20
21 namespace faiss {
22
23 /**
24 * The uniform quantizer has a range [vmin, vmax]. The range can be
25 * the same for all dimensions (uniform) or specific per dimension
26 * (default).
27 */
28
29
30 struct ScalarQuantizer {
31
32 enum QuantizerType {
33 QT_8bit, ///< 8 bits per component
34 QT_4bit, ///< 4 bits per component
35 QT_8bit_uniform, ///< same, shared range for all dimensions
36 QT_4bit_uniform,
37 };
38
39 QuantizerType qtype;
40
41 /** The uniform encoder can estimate the range of representable
42 * values of the unform encoder using different statistics. Here
43 * rs = rangestat_arg */
44
45 // rangestat_arg.
46 enum RangeStat {
47 RS_minmax, ///< [min - rs*(max-min), max + rs*(max-min)]
48 RS_meanstd, ///< [mean - std * rs, mean + std * rs]
49 RS_quantiles, ///< [Q(rs), Q(1-rs)]
50 RS_optim, ///< alternate optimization of reconstruction error
51 };
52
53 RangeStat rangestat;
54 float rangestat_arg;
55
56 /// dimension of input vectors
57 size_t d;
58
59 /// bytes per vector
60 size_t code_size;
61
62 /// trained values (including the range)
63 std::vector<float> trained;
64
65 ScalarQuantizer (size_t d, QuantizerType qtype);
66 ScalarQuantizer ();
67
68 void train (size_t n, const float *x);
69
70
71 /// same as compute_code for several vectors
72 void compute_codes (const float * x,
73 uint8_t * codes,
74 size_t n) const ;
75
76 /// decode a vector from a given code (or n vectors if third argument)
77 void decode (const uint8_t *code, float *x, size_t n) const;
78
79 };
80
81
82 struct IndexScalarQuantizer: Index {
83 /// Used to encode the vectors
84 ScalarQuantizer sq;
85
86 /// Codes. Size ntotal * pq.code_size
87 std::vector<uint8_t> codes;
88
89 size_t code_size;
90
91 /** Constructor.
92 *
93 * @param d dimensionality of the input vectors
94 * @param M number of subquantizers
95 * @param nbits number of bit per subvector index
96 */
97 IndexScalarQuantizer (int d,
98 ScalarQuantizer::QuantizerType qtype,
99 MetricType metric = METRIC_L2);
100
101 IndexScalarQuantizer ();
102
103 void train(idx_t n, const float* x) override;
104
105 void add(idx_t n, const float* x) override;
106
107 void search(
108 idx_t n,
109 const float* x,
110 idx_t k,
111 float* distances,
112 idx_t* labels) const override;
113
114 void reset() override;
115
116 void reconstruct_n(idx_t i0, idx_t ni, float* recons) const override;
117
118 void reconstruct(idx_t key, float* recons) const override;
119
120 };
121
122
123 /** An IVF implementation where the components of the residuals are
124 * encoded with a scalar uniform quantizer. All distance computations
125 * are asymmetric, so the encoded vectors are decoded and approximate
126 * distances are computed.
127 */
128
129 struct IndexIVFScalarQuantizer:IndexIVF {
130 ScalarQuantizer sq;
131
132 size_t code_size;
133
134 /// inverted list codes.
135 std::vector<std::vector<uint8_t> > codes;
136
137 IndexIVFScalarQuantizer(Index *quantizer, size_t d, size_t nlist,
138 ScalarQuantizer::QuantizerType qtype,
139 MetricType metric = METRIC_L2);
140
141 IndexIVFScalarQuantizer();
142
143 void train_residual(idx_t n, const float* x) override;
144
145 void add_with_ids(idx_t n, const float* x, const long* xids) override;
146
147 void search(
148 idx_t n,
149 const float* x,
150 idx_t k,
151 float* distances,
152 idx_t* labels) const override;
153
154 void merge_from_residuals(IndexIVF& other) override;
155 };
156
157
158 }
159
160
161 #endif
faiss::IndexIVF
Definition: IndexIVF.h:45
faiss::ScalarQuantizer::code_size
size_t code_size
bytes per vector
Definition: IndexScalarQuantizer.h:60
faiss::ScalarQuantizer::QuantizerType
QuantizerType
Definition: IndexScalarQuantizer.h:32
faiss::IndexScalarQuantizer::search
void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels) const override
Definition: IndexScalarQuantizer.cpp:727
faiss::IndexIVFScalarQuantizer::train_residual
void train_residual(idx_t n, const float *x) override
Definition: IndexScalarQuantizer.cpp:824
faiss::ScalarQuantizer::RS_optim
alternate optimization of reconstruction error
Definition: IndexScalarQuantizer.h:50
faiss::IndexScalarQuantizer
Definition: IndexScalarQuantizer.h:82
faiss::ScalarQuantizer::QT_8bit_uniform
same, shared range for all dimensions
Definition: IndexScalarQuantizer.h:35
faiss::IndexScalarQuantizer::add
void add(idx_t n, const float *x) override
Definition: IndexScalarQuantizer.cpp:719
faiss::ScalarQuantizer::QT_4bit
4 bits per component
Definition: IndexScalarQuantizer.h:34
faiss::IndexScalarQuantizer::reset
void reset() override
removes all elements from the database.
Definition: IndexScalarQuantizer.cpp:783
faiss::IndexIVFScalarQuantizer::search
void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels) const override
Definition: IndexScalarQuantizer.cpp:959
faiss::IndexIVFScalarQuantizer::codes
std::vector< std::vector< uint8_t > > codes
inverted list codes.
Definition: IndexScalarQuantizer.h:135
faiss::IndexIVFScalarQuantizer::merge_from_residuals
void merge_from_residuals(IndexIVF &other) override
Definition: IndexScalarQuantizer.cpp:992
faiss::ScalarQuantizer
Definition: IndexScalarQuantizer.h:30
faiss::IndexIVFScalarQuantizer::add_with_ids
void add_with_ids(idx_t n, const float *x, const long *xids) override
Definition: IndexScalarQuantizer.cpp:843
faiss::Index::d
int d
vector dimension
Definition: Index.h:64
faiss::IndexIVF::quantizer
Index * quantizer
quantizer that maps vectors to inverted lists
Definition: IndexIVF.h:49
faiss::IndexScalarQuantizer::codes
std::vector< uint8_t > codes
Codes. Size ntotal * pq.code_size.
Definition: IndexScalarQuantizer.h:87
faiss::IndexScalarQuantizer::sq
ScalarQuantizer sq
Used to encode the vectors.
Definition: IndexScalarQuantizer.h:84
faiss::Index::idx_t
long idx_t
all indices are this type
Definition: Index.h:62
faiss::ScalarQuantizer::RangeStat
RangeStat
Definition: IndexScalarQuantizer.h:46
faiss::IndexIVFScalarQuantizer
Definition: IndexScalarQuantizer.h:129
faiss::ScalarQuantizer::RS_quantiles
[Q(rs), Q(1-rs)]
Definition: IndexScalarQuantizer.h:49
faiss::ScalarQuantizer::RS_meanstd
[mean - std * rs, mean + std * rs]
Definition: IndexScalarQuantizer.h:48
faiss::ScalarQuantizer::decode
void decode(const uint8_t *code, float *x, size_t n) const
decode a vector from a given code (or n vectors if third argument)
Definition: IndexScalarQuantizer.cpp:685
faiss::ScalarQuantizer::compute_codes
void compute_codes(const float *x, uint8_t *codes, size_t n) const
same as compute_code for several vectors
Definition: IndexScalarQuantizer.cpp:674
faiss::IndexIVF::nlist
size_t nlist
number of possible key values
Definition: IndexIVF.h:46
faiss::ScalarQuantizer::QT_8bit
8 bits per component
Definition: IndexScalarQuantizer.h:33
faiss::Index
Definition: Index.h:60
faiss::IndexScalarQuantizer::reconstruct_n
void reconstruct_n(idx_t i0, idx_t ni, float *recons) const override
Definition: IndexScalarQuantizer.cpp:789
faiss::IndexScalarQuantizer::reconstruct
void reconstruct(idx_t key, float *recons) const override
Definition: IndexScalarQuantizer.cpp:799
faiss::ScalarQuantizer::RS_minmax
[min - rs*(max-min), max + rs*(max-min)]
Definition: IndexScalarQuantizer.h:47
faiss::ScalarQuantizer::trained
std::vector< float > trained
trained values (including the range)
Definition: IndexScalarQuantizer.h:63
faiss::IndexScalarQuantizer::train
void train(idx_t n, const float *x) override
Definition: IndexScalarQuantizer.cpp:713
faiss::ScalarQuantizer::d
size_t d
dimension of input vectors
Definition: IndexScalarQuantizer.h:57
faiss::MetricType
MetricType
Some algorithms support both an inner product vetsion and a L2 search version.
Definition: Index.h:43