Inner Product Similarity Search using Compositional Codes

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.

• Publication year

  2014

• Venue

  arXiv.org

• Publication date

  2014-06-19

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1406.4966
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Scaling up all pairs similarity search pdf

  2015cited by this paper
• Cartesian K-Means

  2013influential reference
• Optimized Product Quantization for Approximate Nearest Neighbor Search

  2013cited by this paper
• Fast, Accurate Detection of 100,000 Object Classes on a Single Machine

  2013cited by this paper
• Towards good practice in large-scale learning for image classification

  2012influential reference
• Compact Hyperplane Hashing with Bilinear Functions

  2012cited by this paper
• A new approach to interdomain routing based on secure multi-party computation

  2012cited by this paper
• Maximum inner-product search using cone trees

  2012cited by this paper
• Accelerated Large Scale Optimization by Concomitant Hashing

  2012cited by this paper
• Product Quantization for Nearest Neighbor Search

  2011influential reference
• Iterative quantization: A procrustean approach to learning binary codes

  2011cited by this paper
• Fast and Balanced: Efficient Label Tree Learning for Large Scale Object Recognition

  2011cited by this paper
• High-dimensional signature compression for large-scale image classification

  2011influential reference
• Searching in one billion vectors: Re-rank with source coding

  2011cited by this paper
• Approximate Nearest Subspace Search

  2011cited by this paper
• Hashing Hyperplane Queries to Near Points with Applications to Large-Scale Active Learning

  2010cited by this paper
• Online dictionary learning for sparse coding

  2009cited by this paper
• Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration

  2009cited by this paper
• Nearest neighbor search : the old, the new, and the impossible

  2009cited by this paper
• Matrix Factorization Techniques for Recommender Systems

  2009cited by this paper
• Hamming Embedding and Weak Geometric Consistency for Large Scale Image Search

  2008cited by this paper
• Latent semantic analysis

  2008cited by this paper
• A Discriminative Kernel-Based Approach to Rank Images from Text Queries

  2008cited by this paper
• Nearest-Neighbor Methods in Learning and Vision

  2008cited by this paper
• Effective Proximity Retrieval by Ordering Permutations

  2008cited by this paper
• The Netflix Prize

  2007cited by this paper
• Model selection and estimation in regression with grouped variables

  2006cited by this paper
• Foundations of multidimensional and metric data structures

  2006cited by this paper
• Scalable Recognition with a Vocabulary Tree

  2006cited by this paper
• Nearest-Neighbor Methods in Learning and Vision: Theory and Practice (Neural Information Processing)

  2006cited by this paper
• Fast contour matching using approximate earth mover's distance

  2004cited by this paper
• Locality-sensitive hashing scheme based on p-stable distributions

  2004cited by this paper
• Multidimensional binary search trees used for associative searching

  1975cited by this paper

• Reinforcement Routing on Proximity Graph for Efficient Recommendation

  2022influential citation
• Semisupervised Network Embedding With Differentiable Deep Quantization

  2021cites this paper
• Efficient Retrieval of Matrix Factorization-Based Top-k Recommendations: A Survey of Recent Approaches

  2021cites this paper
• Influence maximization based on maximum inner product search

  2021cites this paper
• Asymmetric Mapping Quantization for Nearest Neighbor Search

  2020cites this paper
• SNEQ: Semi-Supervised Attributed Network Embedding with Attention-Based Quantisation

  2020cites this paper
• EFFECTS OF ONLINE ADVOCACY BANNERS ON CUSTOMERS AFTER ABANDONING PRODUCTS IN ONLINE SHOPPING CARTS

  2019cites this paper
• Deep Triplet Quantization

  2018cites this paper
• Composite Quantization

  2017cites this paper
• Collective Deep Quantization for Efficient Cross-Modal Retrieval

  2017cites this paper
• Deep Visual-Semantic Quantization for Efficient Image Retrieval

  2017cites this paper
• Accelerated distance computation with encoding tree/forest for high dimensional data

  2016cites this paper
• A Survey on Learning to Hash

  2016cites this paper
• Quantization based Fast Inner Product Search

  2015cites this paper
• Group $K$-Means

  2015cites this paper
• Sparse composite quantization

  2015cites this paper
• Accelerated Distance Computation with Encoding Tree for High Dimensional Data

  2015influential citation
• Optimized Distances for Binary Code Ranking

  2014cites this paper
• Hashing for Similarity Search: A Survey

  2014cites this paper