Polysemous Codes

By Matthijs Douze, Herv'e J'egou, Florent Perronnin. 2016

60 citations recorded by the source corpus.

This paper considers the problem of approximate nearest neighbor search in the compressed domain. We introduce polysemous codes, which offer both the distance estimation quality of product quantization and the efficient comparison of binary codes with Hamming distance. Their design is inspired by algorithms introduced in the 90's to construct channel-optimized vector quantizers. At search time, this dual interpretation accelerates the search. Most of the indexed vectors are filtered out with Hamming distance, letting only a fraction of the vectors to be ranked with an asymmetric distance estimator. The method is complementary with a coarse partitioning of the feature space such as the inverted multi-index. This is shown by our experiments performed on several public benchmarks such as the BIGANN dataset comprising one billion vectors, for which we report state-of-the-art results for query times below 0.3\,millisecond per core. Last but not least, our approach allows the approximate computation of the k-NN graph associated with the Yahoo Flickr Creative Commons 100M, described by CNN image descriptors, in less than 8 hours on a single machine.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, ML Systems & Hardware

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In ML Systems & Hardware

Citations in the corpus

Billion-Scale Similarity Search with GPUs (2017, background): “Many other meth-ods, like LOPQ and the Polysemous codes [27, 16] are too complex to be implemented eﬃciently on GPUs.”
Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (2016, methodology): “To compare the performance of Hierarchical NSW against PQ algorithms we used the facebook Faiss library(8) as the baseline (a new library with state-of-the-art PQ algorithms [12], [15] implementations, released after the current manuscript was submitted) compiled with the”
Multiscale Quantization for Fast Similarity Search (2017, methodology): “[10] propose using Hamming distance for fast pruning.”
Mining on Manifolds: Metric Learning Without Labels (2018, methodology): “This method has been previously used for image graph visualization [12].”
The Faiss Library (2024, unknown): “Instead, they use two ways of interpreting the same compressed vectors: a fast and inaccurate decoding and a slower but more accurate decoding [54], [57], [58], [59], [60] are based on this principle.”