Locality-sensitive Hashing In Function Spaces
Will Shand, Stephen Becker . Arxiv 2020 – 0 citations
[Paper]
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.