Locality Sensitive Hashing For Set-queries, Motivated By Group Recommendations

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,

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keykaplan2020locality

Related papers

• Distance-sensitive Hashing (2017)8.82
• Fast Locality-sensitive Hashing Frameworks For Approximate Near Neighbor Search (2017)7.81
• Improving Locality Sensitive Hashing By Efficiently Finding Projected Nearest Neighbors (2020)6.77
• SLOSH: Set Locality Sensitive Hashing Via Sliced-wasserstein Embeddings (2021)5.24
• Qwlsh: Cache-conscious Indexing For Processing Similarity Search Query Workloads In High-dimensional Spaces (2019)4.52
• Sharing Hash Codes For Multiple Purposes (2016)0.00
• Experimental Analysis Of Locality Sensitive Hashing Techniques For High-dimensional Approximate Nearest Neighbor Searches (2020)6.34
• Hierarchical Locality Sensitive Hashing For Structured Data: A Survey (2022)0.00