Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)

Anshumali Shrivastava; Ping Li

Source-linked AI summary

Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)

Anshumali Shrivastava, Ping Li

arXiv:1405.5869v1May 22, 2014stat.MLcs.DScs.IRcs.LG

TL;DR

MIPS lacks a direct hashing solution because standard LSH cannot handle un-normalized inner products with varying data-vector norms. The paper extends LSH with asymmetric transformations that reduce MIPS to approximate near-neighbor search, yielding a provably efficient scheme evaluated on recommendation datasets.

Problem
Standard LSH is insufficient for MIPS, whose data-vector norms can vary and therefore prevent direct reduction to near-neighbor search.
Method
ALSH applies asymmetric transformations to query and data vectors, converting inner products into L2 distances or approximate near-neighbor search.
Results
The proposed construction provides the first provably sublinear query-time algorithm for approximate similarity search with un-normalized inner products.
Takeaways & Limitations
ALSH extends the LSH framework to MIPS while retaining theoretical guarantees and supports efficient inner-product retrieval in recommendation experiments.
Takeaways & Limitations
The L2-based hash function is unsuitable for MIPS when data norms are not constant, motivating the asymmetric transformations.

Abstract

from arXiv · show

We present the first provably sublinear time algorithm for approximate \emph{Maximum Inner Product Search} (MIPS). Our proposal is also the first hashing algorithm for searching with (un-normalized) inner product as the underlying similarity measure. Finding hashing schemes for MIPS was considered hard. We formally show that the existing Locality Sensitive Hashing (LSH) framework is insufficient for solving MIPS, and then we extend the existing LSH framework to allow asymmetric hashing schemes. Our proposal is based on an interesting mathematical phenomenon in which inner products, after independent asymmetric transformations, can be converted into the problem of approximate near neighbor search. This key observation makes efficient sublinear hashing scheme for MIPS possible. In the extended asymmetric LSH (ALSH) framework, we provide an explicit construction of provably fast hashing scheme for MIPS. The proposed construction and the extended LSH framework could be of independent theoretical interest. Our proposed algorithm is simple and easy to implement. We evaluate the method, for retrieving inner products, in the collaborative filtering task of item recommendations on Netflix and Movielens datasets.

1 Introduction and Motivation

MIPS seeks high-inner-product items in massive, un-normalized vector collections, where varying data-vector norms prevent direct use of standard near-neighbor methods. The paper develops ALSH to obtain provably efficient MIPS retrieval and evaluates it in recommendation.

The MIPS problem: MIPS searches a collection S for a data vector p maximizing or approximately maximizing q^T p for a query q.The collection has size N and vectors lie in R^D.
Why MIPS is difficult: Varying norms make MIPS non-equivalent to near-neighbor search, so existing fast approximate NNS algorithms cannot be directly applied.The equivalence holds when every data vector has constant norm.
Applications: MIPS appears in recommender systems, DPM object detection, structural SVM, and multi-class label prediction.These applications use inner products to rank items, filters, constraints, or class labels.
Applications: Recommendation with learned item vectors is an MIPS instance, but item-vector norms often vary widely and brute-force scanning all N items is prohibitively expensive.The setting requires computing N inner products for online recommendation.
Applications: DPM detection scores image patches against potentially millions of filters, making top-inner-product retrieval a costly step.Efficient MIPS can benefit large-scale DPM object detection.
Applications: Structural SVM separation-oracle calls involve possibly exponentially many labels, while large-label classification also requires expensive high-dimensional vector multiplications.Both computations include an MIPS subproblem.
Contributions: The paper formally rules out LSH for MIPS under the current framework and introduces ALSH, which permits asymmetric query and data transformations.The extended framework is designed to retain LSH-style theoretical guarantees.
Contributions: After asymmetric transformations, the construction reduces MIPS to approximate near-neighbor search and yields the first provably sublinear-time algorithm for approximate un-normalized inner-product search.The method is evaluated for top-ranked item recommendation on Netflix and Movielens datasets.

2 Background

Approximate near-neighbor search reformulates similarity retrieval through threshold guarantees, while LSH uses collision probabilities and multiple hash tables to obtain sublinear query time. However, standard L2 hashing is not generally suitable for un-normalized inner-product search because distance and inner-product orderings can differ.

Approximate Near Neighbor: Approximate near-neighbor search reports a cS0-near neighbor when an S0-near neighbor exists, with probability 1 − δ.The similarity-based formulation uses Sim(q,p) ≥ S0 instead of distance thresholds.
Locality Sensitive Hashing: LSH favors similar points by assigning them a higher collision probability than less similar points.An LSH family maps points into a range space where collisions support efficient retrieval.
Locality Sensitive Hashing: LSH concatenates K independent hash functions into meta-hash functions and uses L independent tables for indexing and querying.Preprocessing assigns data points to table buckets, while querying unions the buckets matching the query across tables.
Locality Sensitive Hashing: Colliding candidates have a higher probability of similarity than random points, with K and L tuning the speed–quality trade-off.The resulting c-NN structure has O(n^ρ log n) query time and O(n^(1+ρ)) space when ρ = log p1 / log p2 < 1.
Locality Sensitive Hashing: LSH provides provably sublinear query time while trading additional preprocessing cost and space, with worst-case query time dependent on ρ and n.This property makes LSH widely used in industrial practice and avoids dependence on dimension in the stated worst-case bound.
Limitations for MIPS: The p-stable L2 hash is monotonic in Euclidean distance, but its distance-based ordering is not generally monotonic in inner product unless data have constant norm.Consequently, standard L2 hashing is unsuitable for un-normalized MIPS, and normalization-based improvements cannot be used when data cannot be normalized.

3 Hashing for MIPS

The paper proves that standard LSH cannot solve un-normalized MIPS, then introduces asymmetric transformations and ALSH to reduce MIPS to approximate near neighbor search with sublinear guarantees.

3.1 A Negative Result: Standard LSH cannot provide a hashing family for un-normalized MIPS.The proof uses the fact that self-collision probability is always 1, while another point can have a larger inner product than a point’s self-similarity.
3.2 Our Proposal: Asymmetric LSH (ALSH): ALSH permits different query and preprocessing hash functions while preserving LSH-style runtime guarantees.The asymmetric collision probability must increase with similarity and satisfy the usual p1, p2 conditions.
3.3 From MIPS to Near Neighbor Search (NNS): The construction appends norm-dependent scalars to P(x), while Q(x) appends m values of 1/2.These asymmetric transformations map the original vectors into RD+m.
3.3 From MIPS to Near Neighbor Search (NNS): The transformations P and Q shrink norms and make transformed L2 distance rank-correlate with un-normalized inner products.This establishes the paper’s connection between un-normalized MIPS and approximate near neighbor search.
3.4 Fast Algorithms for MIPS: The approximation error U^(2m+1) rapidly becomes negligible, allowing c-approximate MIPS to use standard near neighbor data structures.For any c < 1, suitable U < 1 and m yield ρ < 1.
3.4 Fast Algorithms for MIPS: The resulting structure achieves O(n^ρ* log n) query time and O(n^(1+ρ*)) space, with ρ* < 1 determined by the optimization constraints.The parameter trade-off between U and m is governed by the decreasing collision-probability function Fr(d).

4 Evaluations

The evaluation constructs latent-factor recommendation benchmarks from Movielens and Netflix, then compares ALSH with L2LSH using top-T precision-recall. Across both datasets, ALSH retrieves high-inner-product items more effectively, with performance improving as hash codes increase and remaining reasonably stable near r = 2.5.

Datasets and setup: The evaluation uses Movielens and Netflix collaborative-filtering datasets, generating user and item latent vectors with PureSVD.The latent dimensions are f = 150 for Movielens and f = 300 for Netflix.
Baseline comparison: The proposed hash function is compared with L2LSH because it is the first provable hashing scheme for retrieving inner products and has no existing baseline.The comparison tests whether asymmetric transformations improve retrieval over an L2LSH indexing scheme.
Interpretation: The experiments indicate that item-vector norms significantly affect recommendation rankings and establish the need for asymmetric transformations P and Q.This follows from the suboptimal performance of L2LSH for un-normalized inner products.
Retrieval results: ALSH significantly outperforms L2LSH on Movielens and Netflix precision-recall curves for retrieving top-T items with T = 1,5,10.The proposed method uses m = 3, U = 0.83, and r = 2.5, while L2LSH is evaluated across r values from 1 to 5.
Parameter sensitivity: For the proposed method, r = 2.5 is a good choice, and performance is not too sensitive to r unless it is far from 2.5.Figure 7 varies r from 1 to 5 while fixing m = 3 and U = 0.83.

5 Conclusion and Future Work

The paper concludes that conventional LSH cannot solve MIPS, while asymmetric transformations extend hashing to this setting. It identifies faster hashing, higher-order similarities, additional applications, and other similarity functions as future directions.

Conclusion: MIPS seeks repository vectors with maximum un-normalized inner product, but conventional LSH is insufficient and no provably sublinear-time algorithm previously existed.The problem arises in applications including collaborative filtering.
Conclusion: ALSH generalizes LSH by applying different transformations to query and data vectors, converting inner products into L2 distances in transformed space.The paper provides an explicit construction with provably efficient MIPS retrieval.
Future work: The paper proposes extending ALSH to three-way or higher-order MIPS and exploring asymmetric hashing for other similarity functions, including binary data.These are identified as future research directions.
Future work: Replacing random-projection hashing with faster hashing techniques could further improve the runtime guarantees.The proposed hash function currently uses random projection as its main hashing scheme.
Future work: Applying efficient MIPS routines to object detection and structural SVMs is proposed as future work beyond collaborative filtering.Both applications involve expensive inner-product maximization over large candidate sets.