Searching in one billion vectors: re-rank with source coding

Abstract

Recent indexing techniques inspired by source coding have been shown successful to index billions of high-dimensional vectors in memory. In this paper, we propose an approach that re-ranks the neighbor hypotheses obtained by these compressed-domain indexing methods. In contrast to the usual post-verification scheme, which performs exact distance calculation on the short-list of hypotheses, the estimated distances are refined based on short quantization codes, to avoid reading the full vectors from disk. We have released a new public dataset of one billion 128-dimensional vectors and proposed an experimental setup to evaluate high dimensional indexing algorithms on a realistic scale. Experiments show that our method accurately and efficiently re-ranks the neighbor hypotheses using little memory compared to the full vectors representation.

International Conference on Acoustics, Speech and Signal Processing, Prague : Czech Republic (2011)

Cited by in corpus (13)

• Fast k-NN search
• Pigeonring: A Principle for Faster Thresholded Similarity Search
• Inner Product Similarity Search using Compositional Codes
• Link and code: Fast indexing with graphs and compact regression codes
• Scalable Locality-Sensitive Hashing for Similarity Search in High-Dimensional, Large-Scale Multimedia Datasets
• ParMAC: distributed optimisation of nested functions, with application to learning binary autoencoders
• LOH and behold: Web-scale visual search, recommendation and clustering using Locally Optimized Hashing
• Fast Neighborhood Graph Search using Cartesian Concatenation
• Fast Exact Search in Hamming Space with Multi-Index Hashing
• Transformed Residual Quantization for Approximate Nearest Neighbor Search
• HCLAE: High Capacity Locally Aggregating Encodings for Approximate Nearest Neighbor Search
• Reconfigurable Inverted Index
• Accelerated Distance Computation with Encoding Tree for High Dimensional Data