Inner Product Similarity Search Using Compositional Codes

Du Chao, Wang Jingdong. Arxiv 2014

[Paper]    
ARXIV

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.

Similar Work

• Quantization Based Fast Inner Product Search
• Composite Quantization
• Learning Better Encoding For Approximate Nearest Neighbor Search With Dictionary Annealing
• SAH Shifting-aware Asymmetric Hashing For Reverse k-maximum Inner Product Search