Locality-sensitive Hashing In Function Spaces

Shand Will, Becker Stephen. Arxiv 2020

[Paper]    
ARXIV Independent LSH

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 ${\mathbb{R}}^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.

Similar Work

• Multi-probe LSH Efficient Indexing For High-dimensional Similarity Search
• Generic LSH Families For The Angular Distance Based On Johnson-lindenstrauss Projections And Feature Hashing LSH
• Practical And Optimal LSH For Angular Distance
• Practical And Optimal LSH For Angular Distance