Locality-sensitive hashing in function spaces
This addresses the problem of efficient similarity search in high-dimensional function spaces for applications like data analysis, but it is incremental as it builds on existing LSH techniques.
The paper tackles similarity search in function spaces by extending locality-sensitive hashing (LSH) to L^p spaces using two methods: function approximation in an orthonormal basis and (quasi-)Monte Carlo techniques, and applies this to construct an LSH family for Wasserstein distance over one-dimensional continuous probability distributions.
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.