Maximum inner-product search using cone trees

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.

• Publication year

  2012

• Venue

  Knowledge Discovery and Data Mining

• Publication date

  2012-02-28

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/2339530.2339677arXiv 1202.6101
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Beyond Sentiment: The Manifold of Human Emotions

  2012cited by this paper
• The Yahoo! Music Dataset and KDD-Cup '11

  2012cited by this paper
• Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality

  2012cited by this paper
• Learning to Search Efficiently in High Dimensions

  2011cited by this paper
• Five Balltree Construction Algorithms

  2009cited by this paper
• The BellKor Solution to the Netflix Grand Prize

  2009cited by this paper
• Kernelized locality-sensitive hashing for scalable image search

  2009cited by this paper
• Rank-Approximate Nearest Neighbor Search: Retaining Meaning and Speed in High Dimensions

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

  2009cited by this paper
• Linear-time Algorithms for Pairwise Statistical Problems

  2009cited by this paper
• Latent semantic analysis

  2008cited by this paper
• Random projection trees and low dimensional manifolds

  2008cited by this paper
• A learning framework for nearest neighbor search

  2007cited by this paper
• Lessons from the Netflix prize challenge

  2007cited by this paper
• KDD Cup and workshop 2007

  2007cited by this paper
• The Netflix Prize

  2007cited by this paper
• Random Features for Large-Scale Kernel Machines

  2007cited by this paper
• Cover trees for nearest neighbor

  2006cited by this paper
• Fast maximum a-posteriori inference on Monte Carlo state spaces

  2005cited by this paper
• Nearest-Neighbor Searching and Metric Space Dimensions

  2005cited by this paper
• An Investigation of Practical Approximate Nearest Neighbor Algorithms

  2004cited by this paper
• Nonparametric Density Estimation: Toward Computational Tractability

  2003cited by this paper
• Similarity estimation techniques from rounding algorithms

  2002cited by this paper
• SDSS Imaging Pipelines

  2001influential reference
• 'N-Body' Problems in Statistical Learning

  2000cited by this paper
• PAC nearest neighbor queries: Approximate and controlled search in high-dimensional and metric spaces

  2000cited by this paper
• Similarity Search in High Dimensions via Hashing

  1999cited by this paper
• An Algorithm for Finding Best Matches in Logarithmic Expected Time

  1977cited by this paper
• Scaling Up All Pairs Similarity Search

  year unknowninfluential reference

• Beyond the Geometric Curse: High-Dimensional N-Gram Hashing for Dense Retrieval

  2026cites this paper
• Can Recommender Systems Teach Themselves? A Recursive Self-Improving Framework with Fidelity Control

  2026cites this paper
• Approximate Reverse $k$-Ranks Queries in High Dimensions

  2025cites this paper
• A Survey on Knowledge-Oriented Retrieval-Augmented Generation

  2025cites this paper
• Maximum Inner Product is Query-Scaled Nearest Neighbor

  2025cites this paper
• RetroInfer: A Vector-Storage Approach for Scalable Long-Context LLM Inference

  2025cites this paper
• Approximate Reverse k-Ranks Queries in High Dimensions

  2025cites this paper
• Reveal Hidden Pitfalls and Navigate Next Generation of Vector Similarity Search from Task-Centric Views

  2025cites this paper
• MA-DPR: Manifold-aware Distance Metrics for Dense Passage Retrieval

  2025cites this paper
• How to Mine Potentially Popular Items? A Reverse MIPS-based Approach

  2025cites this paper
• Reconsidering Tree based Methods for k-Maximum Inner-Product Search: The LRUS-CoverTree

  2024cites this paper
• Retrieval with Learned Similarities

  2024cites this paper
• QPaug: Question and Passage Augmentation for Open-Domain Question Answering of LLMs

  2024cites this paper
• Semantic-Enhanced Relational Metric Learning for Recommender Systems

  2024cites this paper
• A Survey on RAG Meeting LLMs: Towards Retrieval-Augmented Large Language Models

  2024cites this paper
• Survey of Computerized Adaptive Testing: A Machine Learning Perspective

  2024cites this paper
• Diversity-Aware k-Maximum Inner Product Search Revisited

  2024influential citation
• Topic-aware Most Influential Community Search in Social Networks

  2024cites this paper
• Improving top-<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si2.svg" display="inline" id="d1e1427"><mml:mi>N</mml:mi></mml:math> recommendations using batch approximation for weighted pair-wise loss

  2024cites this paper
• Deep Tree-based Retrieval for Efficient Recommendation: Theory and Method

  2024cites this paper
• Augmenting Query and Passage for Retrieval-Augmented Generation using LLMs for Open-Domain Question Answering

  2024cites this paper
• A Survey on RAG Meets LLMs: Towards Retrieval-Augmented Large Language Models

  2024cites this paper
• Instance-Level Dynamic LoRAs Composition for Cross-Task Generalization

  2024cites this paper
• CPEQA: A Large Language Model Based Knowledge Base Retrieval System for Chinese Confidentiality Knowledge Question Answering

  2024cites this paper
• Learning Deep Tree-Based Retriever for Efficient Recommendation: Theory and Method.

  2024cites this paper
• QSRP: Efficient Reverse $k-\text{Ranks}$ Query Processing on High-Dimensional Embeddings

  2024cites this paper
• Efficient Approximate Maximum Inner Product Search Over Sparse Vectors

  2024cites this paper
• Search-Efficient Computerized Adaptive Testing

  2023cites this paper
• GUITAR: Gradient Pruning toward Fast Neural Ranking

  2023cites this paper
• Query-Aware Quantization for Maximum Inner Product Search

  2023cites this paper
• Revisiting Neural Retrieval on Accelerators

  2023cites this paper
• Large-scale correlation network construction for unraveling the coordination of complex biological systems

  2023cites this paper
• Rethinking the Role of Token Retrieval in Multi-Vector Retrieval

  2023cites this paper
• Modular Retrieval for Generalization and Interpretation

  2023cites this paper
• Reverse Maximum Inner Product Search: Formulation, Algorithms, and Analysis

  2023influential citation
• FARGO: Fast Maximum Inner Product Search via Global Multi-Probing

  2023cites this paper
• Open-domain Visual Entity Recognition: Towards Recognizing Millions of Wikipedia Entities

  2023cites this paper
• Lightweight-Yet-Efficient: Revitalizing Ball-Tree for Point-to-Hyperplane Nearest Neighbor Search

  2023cites this paper
• OPORP: One Permutation + One Random Projection

  2023influential citation
• Categorical Diversity-Aware Inner Product Search

  2023cites this paper
• Automating Nearest Neighbor Search Configuration with Constrained Optimization

  2023cites this paper
• Multi-Faceted Knowledge-Driven Pre-Training for Product Representation Learning

  2023cites this paper
• Cardinality Estimation in Inner Product Space

  2022cites this paper
• Asymmetric Hashing for Fast Ranking via Neural Network Measures

  2022influential citation
• Constrained Approximate Similarity Search on Proximity Graph

  2022cites this paper
• Solving Diversity-Aware Maximum Inner Product Search Efficiently and Effectively

  2022cites this paper
• Isotropic Representation Can Improve Dense Retrieval

  2022cites this paper
• MQH: Locality Sensitive Hashing on Multi-level Quantization Errors for Point-to-Hyperplane Distances

  2022cites this paper
• Recommender Forest for Efficient Retrieval

  2022cites this paper
• Counterexamples expose gaps in the proof of time complexity for cover trees introduced in 2006

  2022cites this paper
• Forest-based Deep Recommender

  2022cites this paper
• Dialog Inpainting: Turning Documents into Dialogs

  2022cites this paper
• An Efficient and Accurate Encrypted Image Retrieval Scheme via Ball Tree

  2022cites this paper
• Effective and efficient negative sampling in metric learning based recommendation

  2022cites this paper
• WSLRec: Weakly Supervised Learning for Neural Sequential Recommendation Models

  2022cites this paper
• Approximate Nearest Neighbor Search under Neural Similarity Metric for Large-Scale Recommendation

  2022cites this paper
• Reinforcement Routing on Proximity Graph for Efficient Recommendation

  2022cites this paper
• SAH: Shifting-aware Asymmetric Hashing for Reverse k-Maximum Inner Product Search

  2022influential citation
• Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere

  2021cites this paper
• Retrieving and Reading: A Comprehensive Survey on Open-domain Question Answering

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

  2021cites this paper
• Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing

  2021cites this paper
• ProMIPS: Efficient High-Dimensional c-Approximate Maximum Inner Product Search with a Lightweight Index

  2021cites this paper
• A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree

  2021cites this paper
• MONGOOSE: A Learnable LSH Framework for Efficient Neural Network Training

  2021cites this paper
• Enhancing rating prediction for recommendation by metric learning with gray relational analysis

  2021cites this paper
• Federated Nearest Neighbor Classification with a Colony of Fruit-Flies: With Supplement

  2021cites this paper
• ALX: Large Scale Matrix Factorization on TPUs

  2021cites this paper
• A new compressed cover tree guarantees a near linear parameterized complexity for all $k$-nearest neighbors search in metric spaces

  2021cites this paper
• AdaLSH: Adaptive LSH for Solving c-Approximate Maximum Inner Product Search Problem

  2021cites this paper
• A Social Recommendation Based on Metric Learning and Users' Co-Occurrence Pattern

  2021cites this paper
• Item-side ranking regularized distillation for recommender system

  2021cites this paper
• Recommender Systems Based on Graph Embedding Techniques: A Review

  2021cites this paper
• Reverse Maximum Inner Product Search: How to efficiently find users who would like to buy my item?

  2021cites this paper
• Fast Variational AutoEncoder with Inverted Multi-Index for Collaborative Filtering

  2021cites this paper
• Norm Adjusted Proximity Graph for Fast Inner Product Retrieval

  2021cites this paper
• Online Additive Quantization

  2021cites this paper
• LightRec: A Memory and Search-Efficient Recommender System

  2020cites this paper
• A Meta-Algorithm for Improving Top-N Prediction Efficiency of Matrix Factorization Models in Collaborative Filtering

  2020cites this paper
• Unraveling Metric Vector Spaces With Factorization for Recommendation

  2020cites this paper
• ATM: An Attentive Translation Model for Next-Item Recommendation

  2020cites this paper
• Fast Item Ranking under Neural Network based Measures

  2020cites this paper
• Minimizing FLOPs to Learn Efficient Sparse Representations

  2020cites this paper
• REALM: Retrieval-Augmented Language Model Pre-Training

  2020cites this paper
• A^3: Accelerating Attention Mechanisms in Neural Networks with Approximation

  2020cites this paper
• Symmetric Metric Learning with Adaptive Margin for Recommendation

  2020cites this paper
• PRINCETON SERIES IN MODERN OBSERVATIONAL ASTRONOMY

  2020cites this paper
• Dense Passage Retrieval for Open-Domain Question Answering

  2020cites this paper
• Entities as Experts: Sparse Memory Access with Entity Supervision

  2020cites this paper
• Neural Metric Matrix Factorization

  2020cites this paper
• Metric Factorization with Item Cooccurrence for Recommendation

  2020cites this paper
• SONG: Approximate Nearest Neighbor Search on GPU

  2020cites this paper
• A Fully Dynamic Algorithm for k-Regret Minimizing Sets

  2020cites this paper
• MAP Inference for Customized Determinantal Point Processes via Maximum Inner Product Search

  2020cites this paper
• RepBERT: Contextualized Text Embeddings for First-Stage Retrieval

  2020cites this paper
• Neural Neighborhood Encoding for Classification

  2020cites this paper
• Enhancing Deep Multimedia Recommendations Using Graph Embeddings

  2020cites this paper
• AWMF: All-Weighted Metric Factorization for Collaborative Ranking

  2020cites this paper
• Learning To Retrieve: How to Train a Dense Retrieval Model Effectively and Efficiently

  2020cites this paper
• Multiattribute approximate nearest neighbor search based on navigable small world graph

  2020cites this paper