Maximum inner-product search using cone trees

By Parikshit Ram, Alexander G. Gray. 2012

194 citations recorded by the source corpus.

The problem of efficiently finding the best match for a query in a given set with respect to the Euclidean distance or the cosine similarity has been extensively studied. However, the closely related problem of efficiently finding the best match with respect to the inner-product has never been explored in the general setting to the best of our knowledge. In this paper we consider this problem and contrast it with the previous problems considered. First, we propose a general branch-and-bound algorithm based on a (single) tree data structure. Subsequently, we present a dual-tree algorithm for the case where there are multiple queries. Our proposed branch-and-bound algorithms are based on novel inner-product bounds. Finally we present a new data structure, the cone tree, for increasing the efficiency of the dual-tree algorithm. We evaluate our proposed algorithms on a variety of data sets from various applications, and exhibit up to five orders of magnitude improvement in query time over the naive search technique in some cases.

Subfields: Computer Networks and Communications, Information Systems, Information Retrieval & Search, Signal Processing

How researchers see this paper

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

In Computer Networks and Communications

In Information Systems

In Information Retrieval & Search

In Signal Processing

Citations in the corpus

REALM: Retrieval-Augmented Language Model Pre-Training (2020, methodology): “Thus, we can employ Maximum Inner Product Search (MIPS) algorithms to find the approximate top k documents, using running time and storage space that scale sub-linearly with the number of documents (Ram & Gray, 2012; Shrivastava & Li, 2014; Shen et al., 2015).”
Entities as Experts: Sparse Memory Access with Entity Supervision (2020, background): “, 2019) and, while our current implementation does not yet include an efficient implementation of top-k routing (Section 2), we note that it is possible with fast maximum inner product search (Ram and Gray, 2012; Shen et al., 2015; Shrivastava and Li, 2014; Johnson et al., 2017).”
Quantization based Fast Inner Product Search (2015, methodology): “We also compare against the PCA-tree version adapted to inner product search as proposed in [2], which has shown better results than IP-tree [13].”
Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) (2014, methodology): “[19, 13] proposed solutions based on tree data structure combined with branch and bound space partitioning technique similar to k-d trees [9].”
Speeding up the Xbox recommender system using a euclidean transformation for inner-product spaces (2014, background): “This work was later continued in [18] for the general problem of maximal inner-product search, but these extensions showed effective-”
Collaborative Metric Learning (2017, background): “In this section we review the background of metric learning and collaborative filtering with a particular focus on collaborative filtering for implicit feedback.”
Hierarchical Memory Networks (2016, background): “Tree-based approaches [6, 7] create search trees with cells in the leaves of the tree.”
Learning and Inference via Maximum Inner Product Search (2016, methodology): “Zθ is a normalization constant known as partition function: Zθ = ∑ x∈X eθ·φ(x) (2) The partition function ensures that Pθ(x) is a valid probability distribution that sums to one.”
RepBERT: Contextualized Text Embeddings for First-Stage Retrieval (2020, methodology): “Note that in our current retrieval implementation, we have not adopted optimized MIPS algorithms [6, 7, 8] and simply compute relevance scores between the given query and each document.”
Fast Exact Max-Kernel Search (2012, background): “Here p controls the accuracy of the algorithm – larger p implies better approximation; the suggest value for p is O( √ n) with no rigorous approximation guarantees.”
Dialog Inpainting: Turning Documents into Dialogs (2022, methodology): “…between the two is their vector cosine similarity: sγ(q, p) = embedγ(q) > embedγ(p) ‖ embedγ(q)‖ · ‖ embedγ(p)‖ This particular function enables one to retrieve the top-K highest-scoring passages for a given query using fast similarity search methods that run in sub-linear time (Ram & Gray, 2012).”
Inner Product Similarity Search using Compositional Codes (2014, background): “A cone tree based index structure [14] is designed for exact inner product similarity search.”
On Symmetric and Asymmetric LSHs for Inner Product Search (2014, unknown): “M L ] 2 4 O ct 2 01 4”
TensorCast: forecasting and mining with coupled tensors (2018, background): “Some attention has been given to this problem, since Ram and Gray [30] proposed the use of Cone Trees to speed-up this search.”
To Index or Not to Index: Optimizing Exact Maximum Inner Product Search (2017, methodology): “In this paper, we focus on the batch top-K MIPS problem [27], [31], [34], where we wish to minimize the end-to-end runtime of finding the top K items that maximize the inner product for all u ∈ U .”
Clustering is Efficient for Approximate Maximum Inner Product Search (2015, methodology): “Ram and Gray (2012) provided a tree-based solution for the problem.”
Retrieving and Reading: A Comprehensive Survey on Open-domain Question Answering (2021, methodology): “The Sublinear Maximum Inner Product Search (MIPS) algorithm [68], [69], [70] is used to improve the retrieval efficiency given a question, especially when the document repository is large-scale.”