SLOSH: Set Locality Sensitive Hashing Via Sliced-wasserstein Embeddings

Abstract

Learning from set-structured data is an essential problem with many applications in machine learning and computer vision. This paper focuses on non-parametric and data-independent learning from set-structured data using approximate nearest neighbor (ANN) solutions, particularly locality-sensitive hashing. We consider the problem of set retrieval from an input set query. Such retrieval problem requires: 1) an efficient mechanism to calculate the distances/dissimilarities between sets, and 2) an appropriate data structure for fast nearest neighbor search. To that end, we propose Sliced-Wasserstein set embedding as a computationally efficient "set-2-vector" mechanism that enables downstream ANN, with theoretical guarantees. The set elements are treated as samples from an unknown underlying distribution, and the Sliced-Wasserstein distance is used to compare sets. We demonstrate the effectiveness of our algorithm, denoted as Set-LOcality Sensitive Hashing (SLOSH), on various set retrieval

Stats

• citations4
• S2 citations—
• github stars0
• HF likes0
• heat score5.24
• arxiv keylu2021slosh

Related papers

• Locality Sensitive Hashing For Set-queries, Motivated By Group Recommendations (2020)0.00
• Set-to-set Hashing With Applications In Visual Recognition (2017)0.00
• Hierarchical Locality Sensitive Hashing For Structured Data: A Survey (2022)0.00
• Unfolded Self-reconstruction LSH: Towards Machine Unlearning In Approximate Nearest Neighbour Search (2023)0.00
• Improving Locality Sensitive Hashing By Efficiently Finding Projected Nearest Neighbors (2020)6.77
• Experimental Analysis Of Locality Sensitive Hashing Techniques For High-dimensional Approximate Nearest Neighbor Searches (2020)6.34
• Optimal Las Vegas Locality Sensitive Data Structures (2017)6.77
• Multi-level Spherical Locality Sensitive Hashing For Approximate Near Neighbors (2017)0.00