Locality-sensitive hashing in function spaces

2020/02/10 by Will Shand, Stephen Becker, Shand, Will +1
Computer Science · #Advanced Data Compression Techniques #Advanced Image and Video Retrieval Techniques #FOS: Computer and information sciences #FOS: Mathematics #Generative Adversarial Networks and Image Synthesis #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2002.03909

openalex publication_date 2020/02/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We discuss the problem of performing similarity search over function spaces. To perform search over such spaces in a reasonable amount of time, we use \it locality-sensitive hashing (LSH). We present two methods that allow LSH functions on ℝ^N to be extended to L^p spaces: one using function approximation in an orthonormal basis, and another using (quasi-)Monte Carlo-style techniques. We use the presented hashing schemes to construct an LSH family for Wasserstein distance over one-dimensional, continuous probability distributions.

Related

• Optimal Las Vegas Locality Sensitive Data Structures
• CoveringLSH: Locality-sensitive Hashing without False Negatives
• A Survey on Locality Sensitive Hashing Algorithms and their Applications
• Distance-Sensitive hashing
• Improving Similarity Search with High-dimensional Locality-sensitive Hashing