Locality Sensitive Hashing for Set-Queries, Motivated by Group Recommendations

Haim Kaplan, Jay Tenenbaum

TL;DR

This paper introduces Set-query Locality Sensitive Hashing (SLSH), generalizing classical LSH from single-point queries to sets of query points. By aggregating individual similarities using arithmetic, geometric, or center (min/max) metrics, SLSH enables sublinear-time approximate nearest neighbor search for groups—such as recommending an item that best satisfies a group of users.

What Problem Does This Paper Address?

Standard Locality Sensitive Hashing (LSH) solves the approximate nearest neighbor (ANN) problem in high dimensions: given a single query point, retrieve database points that are close under a distance or similarity metric without scanning the entire database.

However, real-world systems often deal with group queries. For example, in group recommendation systems (e.g., picking a movie for family movie night or selecting a travel destination for friends), the query is not a single user profile, but a set of user vectors. The goal is to find an item that maximizes an aggregate score, such as:

  • Average similarity / distance: Maximizing the average satisfaction.
  • Geometric similarity: Balancing mutual agreement across members.
  • Center / "Least-Misery" similarity: Minimizing the dissatisfaction of the most unhappy group member.

Prior solutions to group recommendation relied mostly on heuristic or linear-scan approaches on small datasets. This paper provides the first rigorous sublinear algorithmic framework for set-queries using LSH.

Methods

The authors formulate SLSH for set-query-to-point (s2p) similarities and distances, developing several novel schemes and reductions:

  • Repeat-SLSH for $\ell_p$ / Average Similarities: For "achievable" point-to-point similarities (where collision probability equals exact similarity, e.g., angular, Hamming, or Jaccard similarity), uniformly sampling a random element from query set $Q$ and hashing it $p$ times independently yields a collision probability exactly equal to the $\ell_p$ aggregated similarity.
  • Exhaustive-SLSH (Unweighted and Weighted Geometric Similarity): By hashing each point in the set with an independent hash function, the combined collision probability equals the geometric product of similarities $\prod_{i} s(q_i, x)^{w_i}$.
  • Shrink-Lift Transformation for Euclidean Distances: By shrinking vectors into a small ball and "lifting" them onto a unit sphere in $\mathbb{R}^{d+1}$ ($x^\uparrow = ( \varepsilon x, \sqrt{1 - \|\varepsilon x\|^2} )$), Euclidean distances are mapped approximately to angular distances. This enables SLSH for average Euclidean distance.
  • Euclidean Ellipsoid ALSH: Extends ANN to distance metrics whose unit balls are ellipsoids with arbitrary query-specified orientations and center points. The authors solve this via reduction to an angular ellipsoid ALSH problem, which in turn reduces to weighted geometric angular similarity SLSH using hyperplane hashing (H-hash).
  • Center Euclidean Distance for Pairs ($k=2$): Solves the "least-misery" metric for sets of size 2. The region where $\max(\|v - q_1\|, \|v - q_2\|) \le r$ is sandwiched between two concentric ellipsoids, reducing the problem to Euclidean Ellipsoid ALSH combined with a quantization of the distance between the two query points.

Datasets

Not discussed in the paper (this is a purely theoretical paper; no experimental datasets or empirical benchmarks were evaluated).

Key Insights and Ideas

  • Composability of Achievable Similarities: If an LSH family matches the underlying similarity value exactly, basic probabilistic operations mirror aggregation algebra: random choice corresponds to arithmetic averaging, while independent conjunction corresponds to geometric multiplication.
  • Sandwiching the "Least-Misery" Lens: The intersection of two metric balls (the feasible region for queries of size 2 under center distance) is difficult to index directly. However, it can be tightly bounded from the inside and outside by concentric ellipsoids, translating a set-query problem into an ellipsoid-query problem.
  • Hyperplane Collisions as Angular Distances: Using hyperplane hashing (where collision probability depends on the angle to the hyperplane), the squared distance along an ellipsoid axis directly translates to collision probabilities, tying geometric ellipsoid queries back to angular SLSH.

Key Results

  • Provable SLSH Families: Established $(S, cS)$-SLSH schemes for arithmetic average, $\ell_p$, geometric, and weighted geometric similarities for any achievable base metric.
  • Average Euclidean Distance SLSH: Constructed an $(r, cr)$-SLSH structure for average Euclidean distance over query sets of arbitrary size $k$.
  • Ellipsoid Near-Neighbor Search: Designed the first LSH-based structure for query-oriented Euclidean ellipsoids.
  • Size-2 Center Euclidean Distance: Designed an $(r, cr)$-SLSH structure for $k=2$ center Euclidean distance for any approximation factor $c > c_{\min} = \frac{3}{2\sqrt{2}} \approx 1.06066$.

Limitations and Future Work

  • Performance Trade-offs: Chains of reductions (Euclidean $\to$ angular $\to$ weighted geometric) degrade collision probability gaps ($p_1, p_2$), leading to higher query times and larger data structures. The parameter $\rho = \frac{\log p_1}{\log p_2}$ was not analytically optimized.
  • Approximation Ratio Bounds: The shrink-lift reduction degrades as $c \to 1$ or as the shrinking parameter $\varepsilon \to 0$, making query time bounds grow sharply.
  • Group Size for Center Metric: The least-misery (center Euclidean) algorithm is restricted to groups of size $k = 2$. Extending center distance indexing to larger groups ($k \ge 3$) remains an open challenge.
  • Lack of Empirical Testing: Empirical validation on real-world recommendation data remains open for future research.

Summary updated

Abstract

Locality Sensitive Hashing (LSH) is an effective method to index a set of points such that we can efficiently find the nearest neighbors of a query point. We extend this method to our novel Set-query LSH (SLSH), such that it can find the nearest neighbors of a set of points, given as a query. Let s(x,y) be the similarity between two points x and y. We define a similarity between a set Q and a point x by aggregating the similarities s(p,x) for all p∈ Q. For example, we can take s(p,x) to be the angular similarity between p and x (i.e., 1-(∠(x,p)/π)), and aggregate by arithmetic or geometric averaging, or taking the lowest similarity. We develop locality sensitive hash families and data structures for a large set of such arithmetic and geometric averaging similarities, and analyze their collision probabilities. We also establish an analogous framework and hash families for distance functions. Specifically, we give a structure for the euclidean distance aggregated by either averaging or taking the maximum. We leverage SLSH to solve a geometric extension of the approximate near neighbors problem. In this version, we consider a metric for which the unit ball is an ellipsoid and its orientation is specified with the query. An important application that motivates our work is group recommendation systems. Such a system embeds movies and users in the same feature space, and the task of recommending a movie for a group to watch together, translates to a set-query Q using an appropriate similarity.
BibTeX
@inproceedings{kaplan2020locality,
  author = {Haim Kaplan and Jay Tenenbaum},
  title = {{Locality Sensitive Hashing for Set-Queries, Motivated by Group Recommendations}},
  booktitle = {SWAT},
  year = {2020},
  url = {https://openreview.net/forum?id=spTuCGuRcKT},
}

Loading related content...

Figure