/root/doris/contrib/faiss/faiss/IndexIVFAdditiveQuantizer.cpp

Source
/*
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * This source code is licensed under the MIT license found in the
 * LICENSE file in the root directory of this source tree.
 */

#include <faiss/IndexIVFAdditiveQuantizer.h>

#include <algorithm>
#include <cmath>
#include <cstring>

#include <faiss/impl/FaissAssert.h>
#include <faiss/impl/ResidualQuantizer.h>
#include <faiss/impl/ResultHandler.h>
#include <faiss/utils/distances.h>
#include <faiss/utils/extra_distances.h>

namespace faiss {

/**************************************************************************************
 * IndexIVFAdditiveQuantizer
 **************************************************************************************/

IndexIVFAdditiveQuantizer::IndexIVFAdditiveQuantizer(
        AdditiveQuantizer* aq,
        Index* quantizer,
        size_t d,
        size_t nlist,
        MetricType metric)
        : IndexIVF(quantizer, d, nlist, 0, metric), aq(aq) {
    by_residual = true;
}

IndexIVFAdditiveQuantizer::IndexIVFAdditiveQuantizer(AdditiveQuantizer* aq)
        : IndexIVF(), aq(aq) {}

void IndexIVFAdditiveQuantizer::train_encoder(
        idx_t n,
        const float* x,
        const idx_t* assign) {
    aq->train(n, x);
}

idx_t IndexIVFAdditiveQuantizer::train_encoder_num_vectors() const {
    size_t max_train_points = 1024 * ((size_t)1 << aq->nbits[0]);
    // we need more data to train LSQ
    if (dynamic_cast<LocalSearchQuantizer*>(aq)) {
        max_train_points = 1024 * aq->M * ((size_t)1 << aq->nbits[0]);
    }
    return max_train_points;
}

void IndexIVFAdditiveQuantizer::encode_vectors(
        idx_t n,
        const float* x,
        const idx_t* list_nos,
        uint8_t* codes,
        bool include_listnos) const {
    FAISS_THROW_IF_NOT(is_trained);

    // first encode then possibly add listnos

    if (by_residual) {
        // subtract centroids
        std::vector<float> residuals(n * d);

#pragma omp parallel for if (n > 10000)
        for (idx_t i = 0; i < n; i++) {
            quantizer->compute_residual(
                    x + i * d,
                    residuals.data() + i * d,
                    list_nos[i] >= 0 ? list_nos[i] : 0);
        }
        aq->compute_codes(residuals.data(), codes, n);
    } else {
        aq->compute_codes(x, codes, n);
    }

    if (include_listnos) {
        // write back from the end, where there is enough space
        size_t coarse_size = coarse_code_size();
        for (idx_t i = n - 1; i >= 0; i--) {
            uint8_t* code = codes + i * (code_size + coarse_size);
            memmove(code + coarse_size, codes + i * code_size, code_size);
            encode_listno(list_nos[i], code);
        }
    }
}

void IndexIVFAdditiveQuantizer::sa_decode(
        idx_t n,
        const uint8_t* codes,
        float* x) const {
    const size_t coarse_size = coarse_code_size();

#pragma omp parallel if (n > 1000)
    {
        std::vector<float> residual(d);

#pragma omp for
        for (idx_t i = 0; i < n; i++) {
            const uint8_t* code = codes + i * (code_size + coarse_size);
            int64_t list_no = decode_listno(code);
            float* xi = x + i * d;
            aq->decode(code + coarse_size, xi, 1);
            if (by_residual) {
                quantizer->reconstruct(list_no, residual.data());
                for (size_t j = 0; j < d; j++) {
                    xi[j] += residual[j];
                }
            }
        }
    }
}

void IndexIVFAdditiveQuantizer::reconstruct_from_offset(
        int64_t list_no,
        int64_t offset,
        float* recons) const {
    const uint8_t* code = invlists->get_single_code(list_no, offset);
    aq->decode(code, recons, 1);
    if (by_residual) {
        std::vector<float> centroid(d);
        quantizer->reconstruct(list_no, centroid.data());
        for (int i = 0; i < d; ++i) {
            recons[i] += centroid[i];
        }
    }
}

IndexIVFAdditiveQuantizer::~IndexIVFAdditiveQuantizer() = default;

/*********************************************
 * AQInvertedListScanner
 *********************************************/

namespace {

using Search_type_t = AdditiveQuantizer::Search_type_t;

struct AQInvertedListScanner : InvertedListScanner {
    const IndexIVFAdditiveQuantizer& ia;
    const AdditiveQuantizer& aq;
    std::vector<float> tmp;

    AQInvertedListScanner(const IndexIVFAdditiveQuantizer& ia, bool store_pairs)
            : ia(ia), aq(*ia.aq) {
        this->store_pairs = store_pairs;
        this->code_size = ia.code_size;
        keep_max = is_similarity_metric(ia.metric_type);
        tmp.resize(ia.d);
    }

    const float* q0;

    /// from now on we handle this query.
    void set_query(const float* query_vector) override {
        q0 = query_vector;
    }

    const float* q;
    /// following codes come from this inverted list
    void set_list(idx_t list_no, float coarse_dis) override {
        this->list_no = list_no;
        if (ia.metric_type == METRIC_L2 && ia.by_residual) {
            ia.quantizer->compute_residual(q0, tmp.data(), list_no);
            q = tmp.data();
        } else {
            q = q0;
        }
    }

    ~AQInvertedListScanner() = default;
};

template <bool is_IP>
struct AQInvertedListScannerDecompress : AQInvertedListScanner {
    AQInvertedListScannerDecompress(
            const IndexIVFAdditiveQuantizer& ia,
            bool store_pairs)
            : AQInvertedListScanner(ia, store_pairs) {}

    float coarse_dis = 0;

    /// following codes come from this inverted list
    void set_list(idx_t list_no, float coarse_dis_2) override {
        AQInvertedListScanner::set_list(list_no, coarse_dis_2);
        if (ia.by_residual) {
            this->coarse_dis = coarse_dis_2;
        }
    }

    /// compute a single query-to-code distance
    float distance_to_code(const uint8_t* code) const final {
        std::vector<float> b(aq.d);
        aq.decode(code, b.data(), 1);
        FAISS_ASSERT(q);
        FAISS_ASSERT(b.data());

        return is_IP ? coarse_dis + fvec_inner_product(q, b.data(), aq.d)
                     : fvec_L2sqr(q, b.data(), aq.d);
    }

    ~AQInvertedListScannerDecompress() override = default;
};

template <bool is_IP, Search_type_t search_type>
struct AQInvertedListScannerLUT : AQInvertedListScanner {
    std::vector<float> LUT, tmp;
    float distance_bias;

    AQInvertedListScannerLUT(
            const IndexIVFAdditiveQuantizer& ia,
            bool store_pairs)
            : AQInvertedListScanner(ia, store_pairs) {
        LUT.resize(aq.total_codebook_size);
        tmp.resize(ia.d);
        distance_bias = 0;
    }

    /// from now on we handle this query.
    void set_query(const float* query_vector) override {
        AQInvertedListScanner::set_query(query_vector);
        if (!is_IP && !ia.by_residual) {
            distance_bias = fvec_norm_L2sqr(query_vector, ia.d);
        }
    }

    /// following codes come from this inverted list
    void set_list(idx_t list_no, float coarse_dis) override {
        AQInvertedListScanner::set_list(list_no, coarse_dis);
        // TODO find a way to provide the nprobes together to do a matmul
        // +  precompute tables
        aq.compute_LUT(1, q, LUT.data());

        if (ia.by_residual) {
            distance_bias = coarse_dis;
        }
    }

    /// compute a single query-to-code distance
    float distance_to_code(const uint8_t* code) const final {
        return distance_bias +
                aq.compute_1_distance_LUT<is_IP, search_type>(code, LUT.data());
    }

    ~AQInvertedListScannerLUT() override = default;
};

} // anonymous namespace

InvertedListScanner* IndexIVFAdditiveQuantizer::get_InvertedListScanner(
        bool store_pairs,
        const IDSelector* sel,
        const IVFSearchParameters*) const {
    FAISS_THROW_IF_NOT(!sel);
    if (metric_type == METRIC_INNER_PRODUCT) {
        if (aq->search_type == AdditiveQuantizer::ST_decompress) {
            return new AQInvertedListScannerDecompress<true>(
                    *this, store_pairs);
        } else {
            return new AQInvertedListScannerLUT<
                    true,
                    AdditiveQuantizer::ST_LUT_nonorm>(*this, store_pairs);
        }
    } else {
        switch (aq->search_type) {
            case AdditiveQuantizer::ST_decompress:
                return new AQInvertedListScannerDecompress<false>(
                        *this, store_pairs);
#define A(st)                                                              \
    case AdditiveQuantizer::st:                                            \
        return new AQInvertedListScannerLUT<false, AdditiveQuantizer::st>( \
                *this, store_pairs);
                A(ST_LUT_nonorm)
                A(ST_norm_from_LUT)
                A(ST_norm_float)
                A(ST_norm_qint8)
                A(ST_norm_qint4)
                A(ST_norm_cqint4)
            case AdditiveQuantizer::ST_norm_lsq2x4:
            case AdditiveQuantizer::ST_norm_rq2x4:
                A(ST_norm_cqint8)
#undef A
            default:
                FAISS_THROW_FMT(
                        "search type %d not supported", aq->search_type);
        }
    }
}

/**************************************************************************************
 * IndexIVFResidualQuantizer
 **************************************************************************************/

IndexIVFResidualQuantizer::IndexIVFResidualQuantizer(
        Index* quantizer,
        size_t d,
        size_t nlist,
        const std::vector<size_t>& nbits,
        MetricType metric,
        Search_type_t search_type)
        : IndexIVFAdditiveQuantizer(&rq, quantizer, d, nlist, metric),
          rq(d, nbits, search_type) {
    code_size = invlists->code_size = rq.code_size;
}

IndexIVFResidualQuantizer::IndexIVFResidualQuantizer()
        : IndexIVFAdditiveQuantizer(&rq) {}

IndexIVFResidualQuantizer::IndexIVFResidualQuantizer(
        Index* quantizer,
        size_t d,
        size_t nlist,
        size_t M,     /* number of subquantizers */
        size_t nbits, /* number of bit per subvector index */
        MetricType metric,
        Search_type_t search_type)
        : IndexIVFResidualQuantizer(
                  quantizer,
                  d,
                  nlist,
                  std::vector<size_t>(M, nbits),
                  metric,
                  search_type) {}

IndexIVFResidualQuantizer::~IndexIVFResidualQuantizer() = default;

/**************************************************************************************
 * IndexIVFLocalSearchQuantizer
 **************************************************************************************/

IndexIVFLocalSearchQuantizer::IndexIVFLocalSearchQuantizer(
        Index* quantizer,
        size_t d,
        size_t nlist,
        size_t M,     /* number of subquantizers */
        size_t nbits, /* number of bit per subvector index */
        MetricType metric,
        Search_type_t search_type)
        : IndexIVFAdditiveQuantizer(&lsq, quantizer, d, nlist, metric),
          lsq(d, M, nbits, search_type) {
    code_size = invlists->code_size = lsq.code_size;
}

IndexIVFLocalSearchQuantizer::IndexIVFLocalSearchQuantizer()
        : IndexIVFAdditiveQuantizer(&lsq) {}

IndexIVFLocalSearchQuantizer::~IndexIVFLocalSearchQuantizer() = default;

/**************************************************************************************
 * IndexIVFProductResidualQuantizer
 **************************************************************************************/

IndexIVFProductResidualQuantizer::IndexIVFProductResidualQuantizer(
        Index* quantizer,
        size_t d,
        size_t nlist,
        size_t nsplits,
        size_t Msub,
        size_t nbits,
        MetricType metric,
        Search_type_t search_type)
        : IndexIVFAdditiveQuantizer(&prq, quantizer, d, nlist, metric),
          prq(d, nsplits, Msub, nbits, search_type) {
    code_size = invlists->code_size = prq.code_size;
}

IndexIVFProductResidualQuantizer::IndexIVFProductResidualQuantizer()
        : IndexIVFAdditiveQuantizer(&prq) {}

IndexIVFProductResidualQuantizer::~IndexIVFProductResidualQuantizer() = default;

/**************************************************************************************
 * IndexIVFProductLocalSearchQuantizer
 **************************************************************************************/

IndexIVFProductLocalSearchQuantizer::IndexIVFProductLocalSearchQuantizer(
        Index* quantizer,
        size_t d,
        size_t nlist,
        size_t nsplits,
        size_t Msub,
        size_t nbits,
        MetricType metric,
        Search_type_t search_type)
        : IndexIVFAdditiveQuantizer(&plsq, quantizer, d, nlist, metric),
          plsq(d, nsplits, Msub, nbits, search_type) {
    code_size = invlists->code_size = plsq.code_size;
}

IndexIVFProductLocalSearchQuantizer::IndexIVFProductLocalSearchQuantizer()
        : IndexIVFAdditiveQuantizer(&plsq) {}

IndexIVFProductLocalSearchQuantizer::~IndexIVFProductLocalSearchQuantizer() =
        default;

} // namespace faiss

Coverage Report

Created: 2025-09-15 20:29

Line	Count	Source
1		/*
2		* Copyright (c) Meta Platforms, Inc. and 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		#include <faiss/IndexIVFAdditiveQuantizer.h>
9
10		#include <algorithm>
11		#include <cmath>
12		#include <cstring>
13
14		#include <faiss/impl/FaissAssert.h>
15		#include <faiss/impl/ResidualQuantizer.h>
16		#include <faiss/impl/ResultHandler.h>
17		#include <faiss/utils/distances.h>
18		#include <faiss/utils/extra_distances.h>
19
20		namespace faiss {
21
22		/**************************************************************************************
23		* IndexIVFAdditiveQuantizer
24		**************************************************************************************/
25
26		IndexIVFAdditiveQuantizer::IndexIVFAdditiveQuantizer(
27		AdditiveQuantizer* aq,
28		Index* quantizer,
29		size_t d,
30		size_t nlist,
31		MetricType metric)
32	0	: IndexIVF(quantizer, d, nlist, 0, metric), aq(aq) {
33	0	by_residual = true;
34	0	}
35
36		IndexIVFAdditiveQuantizer::IndexIVFAdditiveQuantizer(AdditiveQuantizer* aq)
37	0	: IndexIVF(), aq(aq) {}
38
39		void IndexIVFAdditiveQuantizer::train_encoder(
40		idx_t n,
41		const float* x,
42	0	const idx_t* assign) {
43	0	aq->train(n, x);
44	0	}
45
46	0	idx_t IndexIVFAdditiveQuantizer::train_encoder_num_vectors() const {
47	0	size_t max_train_points = 1024 * ((size_t)1 << aq->nbits[0]);
48		// we need more data to train LSQ
49	0	if (dynamic_cast<LocalSearchQuantizer*>(aq)) {
50	0	max_train_points = 1024 * aq->M * ((size_t)1 << aq->nbits[0]);
51	0	}
52	0	return max_train_points;
53	0	}
54
55		void IndexIVFAdditiveQuantizer::encode_vectors(
56		idx_t n,
57		const float* x,
58		const idx_t* list_nos,
59		uint8_t* codes,
60	0	bool include_listnos) const {
61	0	FAISS_THROW_IF_NOT(is_trained);
62
63		// first encode then possibly add listnos
64
65	0	if (by_residual) {
66		// subtract centroids
67	0	std::vector<float> residuals(n * d);
68
69	0	#pragma omp parallel for if (n > 10000)
70	0	for (idx_t i = 0; i < n; i++) {
71	0	quantizer->compute_residual(
72	0	x + i * d,
73	0	residuals.data() + i * d,
74	0	list_nos[i] >= 0 ? list_nos[i] : 0);
75	0	}
76	0	aq->compute_codes(residuals.data(), codes, n);
77	0	} else {
78	0	aq->compute_codes(x, codes, n);
79	0	}
80
81	0	if (include_listnos) {
82		// write back from the end, where there is enough space
83	0	size_t coarse_size = coarse_code_size();
84	0	for (idx_t i = n - 1; i >= 0; i--) {
85	0	uint8_t* code = codes + i * (code_size + coarse_size);
86	0	memmove(code + coarse_size, codes + i * code_size, code_size);
87	0	encode_listno(list_nos[i], code);
88	0	}
89	0	}
90	0	}
91
92		void IndexIVFAdditiveQuantizer::sa_decode(
93		idx_t n,
94		const uint8_t* codes,
95	0	float* x) const {
96	0	const size_t coarse_size = coarse_code_size();
97
98	0	#pragma omp parallel if (n > 1000)
99	0	{
100	0	std::vector<float> residual(d);
101
102	0	#pragma omp for
103	0	for (idx_t i = 0; i < n; i++) {
104	0	const uint8_t* code = codes + i * (code_size + coarse_size);
105	0	int64_t list_no = decode_listno(code);
106	0	float* xi = x + i * d;
107	0	aq->decode(code + coarse_size, xi, 1);
108	0	if (by_residual) {
109	0	quantizer->reconstruct(list_no, residual.data());
110	0	for (size_t j = 0; j < d; j++) {
111	0	xi[j] += residual[j];
112	0	}
113	0	}
114	0	}
115	0	}
116	0	}
117
118		void IndexIVFAdditiveQuantizer::reconstruct_from_offset(
119		int64_t list_no,
120		int64_t offset,
121	0	float* recons) const {
122	0	const uint8_t* code = invlists->get_single_code(list_no, offset);
123	0	aq->decode(code, recons, 1);
124	0	if (by_residual) {
125	0	std::vector<float> centroid(d);
126	0	quantizer->reconstruct(list_no, centroid.data());
127	0	for (int i = 0; i < d; ++i) {
128	0	recons[i] += centroid[i];
129	0	}
130	0	}
131	0	}
132
133	0	IndexIVFAdditiveQuantizer::~IndexIVFAdditiveQuantizer() = default;
134
135		/*********************************************
136		* AQInvertedListScanner
137		*********************************************/
138
139		namespace {
140
141		using Search_type_t = AdditiveQuantizer::Search_type_t;
142
143		struct AQInvertedListScanner : InvertedListScanner {
144		const IndexIVFAdditiveQuantizer& ia;
145		const AdditiveQuantizer& aq;
146		std::vector<float> tmp;
147
148		AQInvertedListScanner(const IndexIVFAdditiveQuantizer& ia, bool store_pairs)
149	0	: ia(ia), aq(*ia.aq) {
150	0	this->store_pairs = store_pairs;
151	0	this->code_size = ia.code_size;
152	0	keep_max = is_similarity_metric(ia.metric_type);
153	0	tmp.resize(ia.d);
154	0	}
155
156		const float* q0;
157
158		/// from now on we handle this query.
159	0	void set_query(const float* query_vector) override {
160	0	q0 = query_vector;
161	0	}
162
163		const float* q;
164		/// following codes come from this inverted list
165	0	void set_list(idx_t list_no, float coarse_dis) override {
166	0	this->list_no = list_no;
167	0	if (ia.metric_type == METRIC_L2 && ia.by_residual) {
168	0	ia.quantizer->compute_residual(q0, tmp.data(), list_no);
169	0	q = tmp.data();
170	0	} else {
171	0	q = q0;
172	0	}
173	0	}
174
175	0	~AQInvertedListScanner() = default;
176		};
177
178		template <bool is_IP>
179		struct AQInvertedListScannerDecompress : AQInvertedListScanner {
180		AQInvertedListScannerDecompress(
181		const IndexIVFAdditiveQuantizer& ia,
182		bool store_pairs)
183	0	: AQInvertedListScanner(ia, store_pairs) {} Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_131AQInvertedListScannerDecompressILb1EEC2ERKNS_25IndexIVFAdditiveQuantizerEb Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_131AQInvertedListScannerDecompressILb0EEC2ERKNS_25IndexIVFAdditiveQuantizerEb
184
185		float coarse_dis = 0;
186
187		/// following codes come from this inverted list
188	0	void set_list(idx_t list_no, float coarse_dis_2) override {
189	0	AQInvertedListScanner::set_list(list_no, coarse_dis_2);
190	0	if (ia.by_residual) {
191	0	this->coarse_dis = coarse_dis_2;
192	0	}
193	0	} Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_131AQInvertedListScannerDecompressILb1EE8set_listElf Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_131AQInvertedListScannerDecompressILb0EE8set_listElf
194
195		/// compute a single query-to-code distance
196	0	float distance_to_code(const uint8_t* code) const final {
197	0	std::vector<float> b(aq.d);
198	0	aq.decode(code, b.data(), 1);
199	0	FAISS_ASSERT(q);
200	0	FAISS_ASSERT(b.data());
201
202	0	return is_IP ? coarse_dis + fvec_inner_product(q, b.data(), aq.d)
203	0	: fvec_L2sqr(q, b.data(), aq.d);
204	0	} Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZNK5faiss12_GLOBAL__N_131AQInvertedListScannerDecompressILb1EE16distance_to_codeEPKh Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZNK5faiss12_GLOBAL__N_131AQInvertedListScannerDecompressILb0EE16distance_to_codeEPKh
205
206	0	~AQInvertedListScannerDecompress() override = default; Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_131AQInvertedListScannerDecompressILb1EED2Ev Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_131AQInvertedListScannerDecompressILb0EED2Ev
207		};
208
209		template <bool is_IP, Search_type_t search_type>
210		struct AQInvertedListScannerLUT : AQInvertedListScanner {
211		std::vector<float> LUT, tmp;
212		float distance_bias;
213
214		AQInvertedListScannerLUT(
215		const IndexIVFAdditiveQuantizer& ia,
216		bool store_pairs)
217	0	: AQInvertedListScanner(ia, store_pairs) {
218	0	LUT.resize(aq.total_codebook_size);
219	0	tmp.resize(ia.d);
220	0	distance_bias = 0;
221	0	} Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb1ELNS_17AdditiveQuantizer13Search_type_tE1EEC2ERKNS_25IndexIVFAdditiveQuantizerEb Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE1EEC2ERKNS_25IndexIVFAdditiveQuantizerEb Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE2EEC2ERKNS_25IndexIVFAdditiveQuantizerEb Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE3EEC2ERKNS_25IndexIVFAdditiveQuantizerEb Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE4EEC2ERKNS_25IndexIVFAdditiveQuantizerEb Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE5EEC2ERKNS_25IndexIVFAdditiveQuantizerEb Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE7EEC2ERKNS_25IndexIVFAdditiveQuantizerEb Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE6EEC2ERKNS_25IndexIVFAdditiveQuantizerEb
222
223		/// from now on we handle this query.
224	0	void set_query(const float* query_vector) override {
225	0	AQInvertedListScanner::set_query(query_vector);
226	0	if (!is_IP && !ia.by_residual) {
227	0	distance_bias = fvec_norm_L2sqr(query_vector, ia.d);
228	0	}
229	0	} Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb1ELNS_17AdditiveQuantizer13Search_type_tE1EE9set_queryEPKf Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE1EE9set_queryEPKf Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE2EE9set_queryEPKf Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE3EE9set_queryEPKf Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE4EE9set_queryEPKf Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE5EE9set_queryEPKf Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE7EE9set_queryEPKf Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE6EE9set_queryEPKf
230
231		/// following codes come from this inverted list
232	0	void set_list(idx_t list_no, float coarse_dis) override {
233	0	AQInvertedListScanner::set_list(list_no, coarse_dis);
234		// TODO find a way to provide the nprobes together to do a matmul
235		// + precompute tables
236	0	aq.compute_LUT(1, q, LUT.data());
237
238	0	if (ia.by_residual) {
239	0	distance_bias = coarse_dis;
240	0	}
241	0	} Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb1ELNS_17AdditiveQuantizer13Search_type_tE1EE8set_listElf Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE1EE8set_listElf Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE2EE8set_listElf Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE3EE8set_listElf Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE4EE8set_listElf Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE5EE8set_listElf Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE7EE8set_listElf Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE6EE8set_listElf
242
243		/// compute a single query-to-code distance
244	0	float distance_to_code(const uint8_t* code) const final {
245	0	return distance_bias +
246	0	aq.compute_1_distance_LUT<is_IP, search_type>(code, LUT.data());
247	0	} Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZNK5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb1ELNS_17AdditiveQuantizer13Search_type_tE1EE16distance_to_codeEPKh Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZNK5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE1EE16distance_to_codeEPKh Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZNK5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE2EE16distance_to_codeEPKh Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZNK5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE3EE16distance_to_codeEPKh Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZNK5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE4EE16distance_to_codeEPKh Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZNK5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE5EE16distance_to_codeEPKh Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZNK5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE7EE16distance_to_codeEPKh Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZNK5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE6EE16distance_to_codeEPKh
248
249	0	~AQInvertedListScannerLUT() override = default; Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb1ELNS_17AdditiveQuantizer13Search_type_tE1EED2Ev Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE1EED2Ev Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE2EED2Ev Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE3EED2Ev Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE4EED2Ev Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE5EED2Ev Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE7EED2Ev Unexecuted instantiation: IndexIVFAdditiveQuantizer.cpp:_ZN5faiss12_GLOBAL__N_124AQInvertedListScannerLUTILb0ELNS_17AdditiveQuantizer13Search_type_tE6EED2Ev
250		};
251
252		} // anonymous namespace
253
254		InvertedListScanner* IndexIVFAdditiveQuantizer::get_InvertedListScanner(
255		bool store_pairs,
256		const IDSelector* sel,
257	0	const IVFSearchParameters*) const {
258	0	FAISS_THROW_IF_NOT(!sel);
259	0	if (metric_type == METRIC_INNER_PRODUCT) {
260	0	if (aq->search_type == AdditiveQuantizer::ST_decompress) {
261	0	return new AQInvertedListScannerDecompress<true>(
262	0	*this, store_pairs);
263	0	} else {
264	0	return new AQInvertedListScannerLUT<
265	0	true,
266	0	AdditiveQuantizer::ST_LUT_nonorm>(*this, store_pairs);
267	0	}
268	0	} else {
269	0	switch (aq->search_type) {
270	0	case AdditiveQuantizer::ST_decompress:
271	0	return new AQInvertedListScannerDecompress<false>(
272	0	*this, store_pairs);
273	0	#define A(st) \
274	0	case AdditiveQuantizer::st: \
275	0	return new AQInvertedListScannerLUT<false, AdditiveQuantizer::st>( \
276	0	*this, store_pairs);
277	0	A(ST_LUT_nonorm)
278	0	A(ST_norm_from_LUT)
279	0	A(ST_norm_float)
280	0	A(ST_norm_qint8)
281	0	A(ST_norm_qint4)
282	0	A(ST_norm_cqint4)
283	0	case AdditiveQuantizer::ST_norm_lsq2x4:
284	0	case AdditiveQuantizer::ST_norm_rq2x4:
285	0	A(ST_norm_cqint8)
286	0	#undef A
287	0	default:
288	0	FAISS_THROW_FMT(
289	0	"search type %d not supported", aq->search_type);
290	0	}
291	0	}
292	0	}
293
294		/**************************************************************************************
295		* IndexIVFResidualQuantizer
296		**************************************************************************************/
297
298		IndexIVFResidualQuantizer::IndexIVFResidualQuantizer(
299		Index* quantizer,
300		size_t d,
301		size_t nlist,
302		const std::vector<size_t>& nbits,
303		MetricType metric,
304		Search_type_t search_type)
305	0	: IndexIVFAdditiveQuantizer(&rq, quantizer, d, nlist, metric),
306	0	rq(d, nbits, search_type) {
307	0	code_size = invlists->code_size = rq.code_size;
308	0	}
309
310		IndexIVFResidualQuantizer::IndexIVFResidualQuantizer()
311	0	: IndexIVFAdditiveQuantizer(&rq) {}
312
313		IndexIVFResidualQuantizer::IndexIVFResidualQuantizer(
314		Index* quantizer,
315		size_t d,
316		size_t nlist,
317		size_t M, /* number of subquantizers */
318		size_t nbits, /* number of bit per subvector index */
319		MetricType metric,
320		Search_type_t search_type)
321	0	: IndexIVFResidualQuantizer(
322	0	quantizer,
323	0	d,
324	0	nlist,
325	0	std::vector<size_t>(M, nbits),
326	0	metric,
327	0	search_type) {}
328
329	0	IndexIVFResidualQuantizer::~IndexIVFResidualQuantizer() = default;
330
331		/**************************************************************************************
332		* IndexIVFLocalSearchQuantizer
333		**************************************************************************************/
334
335		IndexIVFLocalSearchQuantizer::IndexIVFLocalSearchQuantizer(
336		Index* quantizer,
337		size_t d,
338		size_t nlist,
339		size_t M, /* number of subquantizers */
340		size_t nbits, /* number of bit per subvector index */
341		MetricType metric,
342		Search_type_t search_type)
343	0	: IndexIVFAdditiveQuantizer(&lsq, quantizer, d, nlist, metric),
344	0	lsq(d, M, nbits, search_type) {
345	0	code_size = invlists->code_size = lsq.code_size;
346	0	}
347
348		IndexIVFLocalSearchQuantizer::IndexIVFLocalSearchQuantizer()
349	0	: IndexIVFAdditiveQuantizer(&lsq) {}
350
351	0	IndexIVFLocalSearchQuantizer::~IndexIVFLocalSearchQuantizer() = default;
352
353		/**************************************************************************************
354		* IndexIVFProductResidualQuantizer
355		**************************************************************************************/
356
357		IndexIVFProductResidualQuantizer::IndexIVFProductResidualQuantizer(
358		Index* quantizer,
359		size_t d,
360		size_t nlist,
361		size_t nsplits,
362		size_t Msub,
363		size_t nbits,
364		MetricType metric,
365		Search_type_t search_type)
366	0	: IndexIVFAdditiveQuantizer(&prq, quantizer, d, nlist, metric),
367	0	prq(d, nsplits, Msub, nbits, search_type) {
368	0	code_size = invlists->code_size = prq.code_size;
369	0	}
370
371		IndexIVFProductResidualQuantizer::IndexIVFProductResidualQuantizer()
372	0	: IndexIVFAdditiveQuantizer(&prq) {}
373
374	0	IndexIVFProductResidualQuantizer::~IndexIVFProductResidualQuantizer() = default;
375
376		/**************************************************************************************
377		* IndexIVFProductLocalSearchQuantizer
378		**************************************************************************************/
379
380		IndexIVFProductLocalSearchQuantizer::IndexIVFProductLocalSearchQuantizer(
381		Index* quantizer,
382		size_t d,
383		size_t nlist,
384		size_t nsplits,
385		size_t Msub,
386		size_t nbits,
387		MetricType metric,
388		Search_type_t search_type)
389	0	: IndexIVFAdditiveQuantizer(&plsq, quantizer, d, nlist, metric),
390	0	plsq(d, nsplits, Msub, nbits, search_type) {
391	0	code_size = invlists->code_size = plsq.code_size;
392	0	}
393
394		IndexIVFProductLocalSearchQuantizer::IndexIVFProductLocalSearchQuantizer()
395	0	: IndexIVFAdditiveQuantizer(&plsq) {}
396
397	0	IndexIVFProductLocalSearchQuantizer::~IndexIVFProductLocalSearchQuantizer() =
398		default;
399
400		} // namespace faiss