Locality Sensitive Hashing for set-queries, applied to group recommendations

Locality Sensitive Hashing 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 such that it can find the nearest neighbors of a set of points, given as a query.

Given a point-to-point similarity s, we can define a similarity between a set Q and a point x by aggregating the similarities s(p,x) of all points $p\inQ$. We define several set-query-to-point similarities by using different functions s and different ways of aggregating these similarities. For example, we can take s(p,x) to be the angular similarity between p and x (i.e., $1-\frac{\angle (x,p)}{\pi}$), and aggregate by arithmetic or geometric averaging.

We develop techniques to get locality sensitive hash families and data structures for these similarity functions, and analyze their collision probabilities. We also establish an analogous framework and hash families for distance functions.

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.