Clustering is Efficient for Approximate Maximum Inner Product Search

Abstract

Efficient Maximum Inner Product Search (MIPS) is an important task that has a wide applicability in recommendation systems and classification with a large number of classes. Solutions based on locality-sensitive hashing (LSH) as well as tree-based solutions have been investigated in the recent literature, to perform approximate MIPS in sublinear time. In this paper, we compare these to another extremely simple approach for solving approximate MIPS, based on variants of the k-means clustering algorithm. Specifically, we propose to train a spherical k-means, after having reduced the MIPS problem to a Maximum Cosine Similarity Search (MCSS). Experiments on two standard recommendation system benchmarks as well as on large vocabulary word embeddings, show that this simple approach yields much higher speedups, for the same retrieval precision, than current state-of-the-art hashing-based and tree-based methods. This simple method also yields more robust retrievals when the query is corrupted by noise.

10 pages, Under review at ICLR 2016

References in corpus (4)

• Efficient Estimation of Word Representations in Vector Space
• Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)
• On Symmetric and Asymmetric LSHs for Inner Product Search
• Deep Networks With Large Output Spaces

Cited by in corpus (13)

• Efficient Natural Language Response Suggestion for Smart Reply
• Hierarchical Memory Networks
• Foundations of Vector Retrieval
• Question Answering from Unstructured Text by Retrieval and Comprehension
• A Greedy Approach for Budgeted Maximum Inner Product Search
• Unsupervised Machine Commenting with Neural Variational Topic Model
• Minimizing FLOPs to Learn Efficient Sparse Representations
• Fast Amortized Inference and Learning in Log-linear Models with Randomly Perturbed Nearest Neighbor Search
• Norm-Explicit Quantization: Improving Vector Quantization for Maximum Inner Product Search
• Reference Product Search
• Energy-Efficient Inference Accelerator for Memory-Augmented Neural Networks on an FPGA
• ProMIPS: Efficient High-Dimensional c-Approximate Maximum Inner Product Search with a Lightweight Index
• Pyramid: A General Framework for Distributed Similarity Search