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