Inner Product Similarity Search using Compositional Codes

By Chao Du, Jingdong Wang. 2014

19 citations recorded by the source corpus.

This paper addresses the nearest neighbor search problem under inner product similarity and introduces a compact code-based approach. The idea is to approximate a vector using the composition of several elements selected from a source dictionary and to represent this vector by a short code composed of the indices of the selected elements. The inner product between a query vector and a database vector is efficiently estimated from the query vector and the short code of the database vector. We show the superior performance of the proposed group $M$-selection algorithm that selects $M$ elements from $M$ source dictionaries for vector approximation in terms of search accuracy and efficiency for compact codes of the same length via theoretical and empirical analysis. Experimental results on large-scale datasets ($1M$ and $1B$ SIFT features, $1M$ linear models and Netflix) demonstrate the superiority of the proposed approach.

Subfields: Computer Vision and Pattern Recognition, Information Systems, Information Retrieval & Search

How researchers see this paper

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

In Computer Vision and Pattern Recognition

1. Jingkuan Song
2. Heng Tao Shen
3. Jingdong Wang
4. Nicu Sebe
5. Ting Zhang
6. Dacheng Tao
7. Yi Yang
8. Shiv Ram Dubey

In Information Systems

1. Heng Tao Shen
2. Jingkuan Song
3. Ting Zhang
4. Jingdong Wang
5. Nicu Sebe

In Information Retrieval & Search

1. Jingkuan Song
2. Ting Zhang
3. Heng Tao Shen
4. Nicu Sebe
5. Jingdong Wang
6. Jianmin Wang
7. Mingsheng Long

Citations in the corpus

• Quantization based Fast Inner Product Search (2015, neutral): “In this paper, we take a quantization based view of the MIPS problem and show that it leads to even better accuracy under both fixed space or fixed time budget on a variety of real world tasks.”
• A Survey on Learning to Hash (2016, methodology): “an approximation of a data item has already been studied in the signal processing research area, known as multi-stage vector quantization, residual quantization, ormore generally structured vector quantization [38], and recently re-developed for similarity search under the Euclidean distance (additi”
• Hashing for Similarity Search: A Survey (2014, unknown): “The idea of using the summation of several dictionary items as an approximation of a data item has already been studied in the signal processing area, known as multi-stage vector quantization, residual quantization, or more generally structured vector quantization [34], and recently re-developed for”