Sparse composite quantization
Authors:
- 1 June 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 4548-4556
Abstract
The quantization techniques have shown competitive performance in approximate nearest neighbor search. The state-of-the-art algorithm, composite quantization, takes advantage of the compositionabity, i.e., the vector approximation accuracy, as opposed to product quantization and Cartesian k-means. However, we have observed that the runtime cost of computing the distance table in composite quantization, which is used as a lookup table for fast distance computation, becomes nonnegligible in real applications, e.g., reordering the candidates retrieved from the inverted index when handling very large scale databases. To address this problem, we develop a novel approach, called sparse composite quantization, which constructs sparse dictionaries. The benefit is that the distance evaluation between the query and the dictionary element (a sparse vector) is accelerated using the efficient sparse vector operation, and thus the cost of distance table computation is reduced a lot. Experiment results on large scale ANN retrieval tasks (1M SIFTs and 1B SIFTs) and applications to object retrieval show that the proposed approach yields competitive performance: superior search accuracy to product quantization and Cartesian k-means with almost the same computing cost, and much faster ANN search than composite quantization with the same level of accuracy.Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Optimized Distances for Binary Code Ranking2014
- Distance Encoded Product Quantization2014
- Locally Optimized Product Quantization for Approximate Nearest Neighbor Search2014
- Optimized Cartesian K-MeansIEEE Transactions on Knowledge and Data Engineering, 2014
- Fast Neighborhood Graph Search Using Cartesian Concatenation2013
- Trinary-Projection Trees for Approximate Nearest Neighbor SearchIEEE Transactions on Pattern Analysis and Machine Intelligence, 2013
- Searching in one billion vectors: Re-rank with source coding2011
- Aggregating local descriptors into a compact image representation2010
- Product Quantization for Nearest Neighbor SearchIEEE Transactions on Pattern Analysis and Machine Intelligence, 2010
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975