PaperlayerView exact revision on arXiv

Source-linked AI summary

Maximum Inner-Product Search using Tree Data-structures

Parikshit Ram, Alexander G. Gray

arXiv:1202.6101v1cs.CGcs.DScs.IR

TL;DR

The paper addresses the largely unexplored general problem of efficiently finding maximum-inner-product matches, which differs from Euclidean and cosine retrieval. It develops tree-based branch-and-bound methods, including dual-tree search and a query-indexing structure, and reports up to five orders of magnitude faster query time than naive search across varied datasets.

  • Problem

    The paper studies efficient maximum inner-product search, a general best-match problem distinguished from extensively studied Euclidean and cosine-similarity retrieval.

  • Method

    The paper develops tree-based branch-and-bound algorithms, extends them to multiple queries with dual-tree search, and introduces a new data structure for query indexing.

  • Results

    Up to five orders of magnitude improvement in query time over naive linear search is reported across datasets from varied applications.

  • Takeaways & Limitations

    The proposed algorithms provide more efficient maximum inner-product search than naive linear scanning, with performance depending on dataset and query-set characteristics.

  • Takeaways & Limitations

    The paper provides no rigorous runtime bounds for the proposed algorithms.

Abstract

from arXiv · show

The problem of {\em 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 in literature. However, a 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 general problem and contrast it with the existing best-match algorithms. First, we propose a general branch-and-bound algorithm using a tree data structure. Subsequently, we present a dual-tree algorithm for the case where there are multiple queries. Finally we present a new data structure for increasing the efficiency of the dual-tree algorithm. These branch-and-bound algorithms involve novel bounds suited for the purpose of best-matching with inner products. 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.

1 Introduction

The paper formulates maximum inner-product search as efficiently finding the highest-inner-product point for a query, distinguishing it from established Euclidean and cosine best-match problems. It proposes tree-based branch-and-bound methods, including a dual-tree extension and a new query-indexing structure, motivated by applications such as scalable recommendation retrieval.

  • Problem: Maximum inner-product search finds, for a query q and point set S, the point p maximizing their inner product.The paper also gives an equivalent vector–matrix formulation.
  • Motivation: Unlike Euclidean nearest-neighbor and cosine-similarity retrieval, maximum inner-product search is treated as a distinct and potentially harder best-match problem.The paper notes that existing techniques cannot be assumed to solve it directly.
  • Applications: Matrix-factorization recommender systems use user–item inner products as preferences, making recommendation retrieval an instance of maximum inner-product search.The paper connects efficient search to scalable retrieval in real-world systems.
  • Applications: Inner-product matching also applies to document retrieval when documents are represented by non-normalized vectors whose inner products define similarity.Using cosine similarity in that setting can return inaccurate matches because the two similarities differ.
  • Connections: Maximum inner-product search can represent max-kernel operations when the kernel has an explicit inner-product feature mapping.The paper identifies applications in maximum-a-posteriori inference and image matching.
  • Contributions: The paper proposes tree-based branch-and-bound algorithms, a dual-tree method for many queries, and a new data structure for indexing those queries.The methods are evaluated on diverse datasets for computational efficiency.

2 Maximum Inner-product Search

Maximum inner-product search differs from Euclidean and cosine matching because unequal vector norms can change the best match, while inner products lack the metric properties required by LSH. The paper therefore uses tree-based exact search, with approximate or constrained variants enabled by the incremental branch-and-bound framework.

  • Differences from existing problems: Euclidean or cosine best matches coincide with inner-product matches when all reference-point norms are equal, but can differ without that restriction.The paper illustrates the difference geometrically and with Figure 1.
  • Assumptions: Under normalization to norms at most one and first-quadrant data, inner products lie in [0,1] and can serve as the similarity function considered for LSH analysis.This normalization does not require all vectors to have equal lengths.
  • Differences from existing problems: Inner products do not induce a triangle inequality, so LSH cannot be directly applied to inner-product similarity even when data are restricted to the first quadrant.The paper uses the distance d(r,p)=1−⟨r,p⟩ to explain this limitation.
  • Differences from existing problems: Inner-product self-similarity equals ∥x∥2, so another point y may have greater similarity to x than x has to itself.This differs from the usual high self-similarity behavior of Euclidean distance and cosine similarity.
  • Tree-based approach: The paper uses tree indexing and branch-and-bound to solve exact maximum inner-product search, extending hierarchical trees beyond nearest-neighbor search.The hierarchical structure also supports approximate solutions for greater efficiency.
  • Search control: Incremental tree-based branch-and-bound search can be adapted to strict error or time constraints, unlike the stated LSH workflow.The paper contrasts this with LSH's theoretical error bounds and non-incremental search behavior.

3 Tree-based Search

The paper indexes points with ball trees and searches them using exact branch-and-bound for maximum inner-product queries. Its key bound uses a node’s center and radius to prune branches that cannot beat the current match.

  • Tree Construction: Ball trees hierarchically partition points into child nodes, each indexed by a center and a ball enclosing its points.Nodes split their point sets into two disjoint child sets; child balls may overlap their parent balls.
  • Tree Construction: A heuristic selects approximately farthest-apart pivot points and assigns each point to its closer pivot before recursively constructing the tree.
  • Branch-and-bound Search: The search traverses the node with better potential inner-product first and prunes a branch when its upper bound cannot improve the current best match.Leaves are searched linearly, and the procedure returns the exact best match.
  • Branch-and-bound Search: For a node T, MIP(q, T) = ⟨q, T.µ⟩ + ∥q∥T.R bounds the maximum possible inner-product with any point in that node.The bound is computed in almost the same time as a single inner-product when query norms are pre-computed.
  • Bounding with a Ball: Because inner products lack the triangle inequality, the method derives an analytical upper bound for points contained in a ball using only its center and radius.The proof maximizes the possible inner-product over geometric angle and radius constraints.

4 Dual-tree based Search

The dual-tree search indexes both queries and reference points, traversing their trees jointly while pruning node pairs whose best possible inner product cannot improve current matches. Ball-trees provide one query organization, while cone-trees exploit the fact that maximum-inner-product matches depend on query direction rather than norm.

  • Dual-tree branch-and-bound: Dual-tree search indexes queries and reference points as trees, traversing both simultaneously to amortize traversal across similar queries.At each query-node/reference-node pair, recursion is pruned when the query node’s lowest current affinity exceeds its maximum possible inner product with the reference node.
  • Query-tree structures: The query tree may use either a ball-tree or the proposed cone-tree, with corresponding upper bounds MIP(Q, T) for query/reference node pairs.The paper derives separate MIP(Q, T) expressions for these query-tree structures.
  • Ball-tree bounds: For two ball nodes, the inner-product bound combines their center inner product, radii, and center norms, then relaxes angular cosine terms to obtain an upper bound.The derivation uses rp ≤ Rp and rq ≤ Rq; when the query ball collapses to a point, the bound reduces to the single-query case.
  • Cone-trees for queries: Cone-tree nodes bound query directions without bounding query norms, enabling bounds between a reference ball and a query cone.The cone aperture is twice the angle between the cone axis and its perimeter, and the paper derives a maximum-inner-product bound for the ball–cone case.
  • Cone-trees for queries: Because the maximizing point is independent of query norm, cone-trees hierarchically index queries by direction using possibly overlapping open cones.Each cone is represented by an axis and the maximum angle between that axis and any point in the cone; cone-tree splitting uses cosine similarity rather than Euclidean distance.

5 Experiments and Results

The experiments evaluate tree-based maximum inner-product search across diverse datasets, comparing branch-and-bound variants with linear search. Tree construction is inexpensive relative to search, while speedups depend on dataset structure and query-set size.

  • Experimental setup: The proposed algorithms are compared with linear search, using speedup defined as linear-search time divided by evaluated-algorithm time.The experiments use a fixed leaf size of N0 = 20 rather than cross-validation.
  • Datasets: The evaluation uses collaborative filtering, text, digit, and astronomy datasets, with item-vectors as references and user-vectors as queries for collaborative filtering.
  • Tree construction: Tree construction costs are small relative to linear search: the highest reported ratio is 0.15 for OptDigits, so speedup above 1.18 compensates for construction.The construction cost is paid once and the tree can then support multiple searches.
  • Search efficiency: Speedups range from 1.13 on OptDigits to over 10^5 on LCDM and PSF, with a Yahoo! Music speedup of 2 saving 19 hours after 120 seconds of construction.
  • Search efficiency: Dual-tree methods perform poorly when single-tree bounds are weak but improve substantially for very large query sets, especially with cone-trees.Cone-trees generally outperform ball-trees for indexing queries.
  • Search efficiency: The algorithms also evaluate retrieving the k highest-inner-product points for k = 1, 2, 5, and 10.

6 Max-kernel Operation with General Kernel Functions

The paper extends maximum inner-product search to kernel-defined spaces whose feature-space points cannot be explicitly represented. It modifies tree construction and upper bounds so branch-and-bound search can operate through kernel evaluations.

  • Kernel-space extension: The method applies the proposed algorithms in kernel inner-product spaces without explicitly representing points in the feature space.
  • Ball-tree construction: Ball-tree centers are chosen as data points closest to the feature-space mean, with quadratic preprocessing used to improve search efficiency.
  • Ball-tree construction: The resulting ball-tree can be constructed and searched in feature space using modified upper bounds, without explicit point representations.The upper bound requires one kernel evaluation, with K(q,q) precomputed.
  • Cone-tree construction: For query cone-trees, the central axis is selected from the feature-space direction closest in angle to the mean of the normalized queries.
  • Dual-tree search: The dual-tree algorithm extends to feature space by replacing the query-point and reference-point bounds with kernel-based upper bounds.

7 Conclusion

The paper concludes that tree-based branch-and-bound methods provide efficient approaches to general maximum inner-product search. It also identifies rigorous runtime analysis as an unresolved direction.

  • The paper presents three tree-based methods: branch-and-bound search, a dual-tree extension for many queries, and a data structure improving dual-tree efficiency.
  • Experiments across varied datasets demonstrate the computational efficiency of the proposed algorithms.
  • The authors do not provide rigorous runtime bounds and identify theoretical analysis as future work.

A Tighter Bounds with Optimization

The paper introduces a tighter upper bound for pairs of tree nodes by optimizing over their angular and radial parameters.

  • The maximum-inner-product bound between two balls is tightened by optimizing over θp, θq, rp, and rq.

A.1 Two-variable Optimization

The two-variable bound is optimized over θp and θq using optimality conditions. Although the resulting conditions identify a maximum, they do not provide an analytic solution, so an efficient optimization algorithm is required.

  • A.1 Two-variable Optimization: Equation 27 bounds ⟨q∗, p∗⟩ by maximizing an expression over θp and θq.The objective includes center inner products, radius products, and cosine terms involving φ, θp, and θq.
  • A.1 Two-variable Optimization: The second-order conditions are negative over the stated range of φ, θp, and θq.Thus, the optimality-condition values correspond to a maximum.
  • A.1 Two-variable Optimization: The optimality conditions lack an analytic solution for θp and θq, so an efficient optimizer can solve the constrained maximization.The optimization task is maxθp,θq f(θp, θq) over the specified range.

A.2 One-variable Optimization

The one-variable approach reduces the bound optimization by fixing θq and substituting the corresponding optimal θp. An efficient one-dimensional optimizer then obtains tight bounds for MIP(Q, T).

  • A.2 One-variable Optimization: The bound is formulated as a maximization over θp, θq, rp, and rq using center and radius terms.The objective combines ⟨p0, q0⟩ with cosine-weighted products involving rp and rq.
  • A.2 One-variable Optimization: For fixed θq, θp is set to φ − ωq using the single-tree bound, reducing the task to one-dimensional optimization.The substitution is made in equation 34 after noting that ωq is fixed when θq is fixed.
  • A.2 One-variable Optimization: The resulting bound maximizes over θq, rp, and rq and uses an inequality based on an assumption together with rp ≤ Rp and rq ≤ Rq.This produces equation 35 as an upper bound on ⟨p∗, q∗⟩.
  • A.2 One-variable Optimization: The second derivative is negative, implying that the optimal θp is the maximum even though equation A.2 has no analytic solution.An efficient optimization algorithm solves maxθp f(θp) to obtain tight bounds for MIP(Q, T).
Loading 1202.6101v1…