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

Haim Kaplan, Jay Tenenbaum

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 \in Q$. For example, we can take $s(p,x)$ to be the angular similarity between $p$ and $x$ (i.e., $1-{\angle (x,p)}/{\pi}$), 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.

Introduction

Standard Locality Sensitive Hashing (LSH) is a cornerstone technique for solving the approximate nearest neighbor problem in high-dimensional spaces. By hashing similar items into the same buckets, it avoids the computational burden of exhaustive linear searches. However, traditional LSH is restricted to point-to-point comparisons. In real-world scenarios like group recommendation systems—where a system might suggest a movie for a group of friends—the query is naturally a set of points representing individual preferences. Finding an item that appeals to the entire group requires aggregating these preferences using metrics like average similarity or the "least misery" baseline (maximizing the minimum similarity). This paper introduces Set-query LSH (SLSH), providing the first rigorous mathematical framework to handle these set-queries directly.

Methodology

The authors define set-to-point (s2p) similarities by aggregating point-to-point (p2p) metrics. They propose several novel techniques to construct these hash families:

1. Repeat-SLSH & Exhaustive-SLSH

For p2p similarities with known LSH families (e.g., angular or Jaccard), SLSH families can be built for $\ell_p$ (average) and geometric aggregations. This is achieved by sampling points from the set-query and applying standard LSH functions iteratively.

2. Shrink-Lift Transformation

To handle the average Euclidean distance for a group, the authors employ a mathematical reduction. They "shrink" data points and "lift" them onto a higher-dimensional unit hypersphere. This transformation converts Euclidean distances into approximate angular distances, enabling the use of angular SLSH structures.

The Shrink-Lift transformation maps Euclidean points onto a higher-dimensional hypersphere to approximate distances as angular similarities.

3. Euclidean Ellipsoid ALSH

The "least misery" metric (minimizing the maximum distance to any point in the set) presents a significant challenge. For a group of two users, the points satisfying this metric form an ellipsoid. The authors reduce this to an "angular ellipsoid" problem, solved using a weighted geometric angular similarity SLSH.

Geometric representation of angular similarity and its relation to ellipsoid-based query regions for group recommendations.

Key Insights

  • Achievability as a Foundation: If a standard LSH exists for a basic metric, it can be mathematically manipulated via repeated hashing to serve complex set-queries.
  • Geometry of Group Dynamics: The paper connects the social concept of "least misery" to the geometric properties of ellipsoids. Finding a mutually acceptable item for two users is equivalent to finding a data point within a specific ellipsoid defined by their feature vectors.
  • Reduction Chains: The authors tackle complex asymmetric hashing by chaining reductions—turning Euclidean problems into angular ones, and ellipsoid problems into weighted geometric similarity problems.

Conclusion and Future Work

This theoretical work establishes the existence and correctness of novel hash families for set-queries. Key results include valid SLSH families for $\ell_p$ and geometric similarities, as well as a working structure for center Euclidean distance for groups of size two. While the paper provides a strong mathematical foundation, future work is needed to empirically validate these methods on real-world recommendation datasets and to extend the "least misery" solution to groups larger than two.

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\in Q $. For example, we can take $ s(p,x) $ to be the angular similarity between $ p $ and $ x $ (i.e., $1-{\angle (x,p)}/{\pi}$), 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},
}
Figure