Improving Bilayer Product Quantization for Billion-Scale Approximate Nearest Neighbors in High Dimensions

By Artem Babenko, Victor S. Lempitsky. 2014

25 citations recorded by the source corpus.

The top-performing systems for billion-scale high-dimensional approximate nearest neighbor (ANN) search are all based on two-layer architectures that include an indexing structure and a compressed datapoints layer. An indexing structure is crucial as it allows to avoid exhaustive search, while the lossy data compression is needed to fit the dataset into RAM. Several of the most successful systems use product quantization (PQ) for both the indexing and the dataset compression layers. These systems are however limited in the way they exploit the interaction of product quantization processes that happen at different stages of these systems. Here we introduce and evaluate two approximate nearest neighbor search systems that both exploit the synergy of product quantization processes in a more efficient way. The first system, called Fast Bilayer Product Quantization (FBPQ), speeds up the runtime of the baseline system (Multi-D-ADC) by several times, while achieving the same accuracy. The second system, Hierarchical Bilayer Product Quantization (HBPQ) provides a significantly better recall for the same runtime at a cost of small memory footprint increase. For the BIGANN dataset of billion SIFT descriptors, the 10% increase in Recall@1 and the 17% increase in Recall@10 is observed.

Subfields: Aerospace Engineering, Computer Vision and Pattern Recognition, Information Retrieval & Search, Efficiency & Compression

How researchers see this paper

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

In Aerospace Engineering

In Computer Vision and Pattern Recognition

In Information Retrieval & Search

In Efficiency & Compression

Citations in the corpus

Billion-Scale Similarity Search with GPUs (2017, neutral): “T b is further optimized [5].”
Polysemous Codes (2016, methodology): “Our polysemous method is set to ﬁlter out 80% of the codes. of the lookup tables involved in PQ when multiple lists are probed [6], and use an optimized rotation before encoding with PQ [19].”
Sparse composite quantization (2015, methodology): “On the reranking stage, there are two ways for distance computation: with reconstructing the database vector, and without reconstructing the database vector but through looking up distance tables like [3].”
The Inverted Multi-Index (2012, background): “Secondly, in Kalantidis and Avrithis [30] and in our report [31], the idea of local codebooks that describe the distribution of the points within each cell of a multi-index has been demonstrated to bring further boost to search accuracy.”