Data-dependent LSH For The Earth Movers Distance

Jayaram Rajesh, Waingarten Erik, Zhang Tian. Arxiv 2024

[Paper]    
ARXIV Independent LSH

We give new data-dependent locality sensitive hashing schemes (LSH) for the Earth Mover’s Distance ($\mathsf{EMD}$), and as a result, improve the best approximation for nearest neighbor search under $\mathsf{EMD}$ by a quadratic factor. Here, the metric ${\mathsf{EMD}}_s({\mathbb{R}}^d,{\ell }_p)$ consists of sets of $s$ vectors in ${\mathbb{R}}^d$, and for any two sets $x,y$ of $s$ vectors the distance $\mathsf{EMD}(x,y)$ is the minimum cost of a perfect matching between $x,y$, where the cost of matching two vectors is their ${\ell }_p$ distance. Previously, Andoni, Indyk, and Krauthgamer gave a (data-independent) locality-sensitive hashing scheme for ${\mathsf{EMD}}_s({\mathbb{R}}^d,{\ell }_p)$ when $p\in [1,2]$ with approximation $O(lo{g}^{2}s)$. By being data-dependent, we improve the approximation to $\tilde{O}(logs)$. Our main technical contribution is to show that for any distribution $\mu$ supported on the metric ${\mathsf{EMD}}_s({\mathbb{R}}^d,{\ell }_p)$, there exists a data-dependent LSH for dense regions of $\mu$ which achieves approximation $\tilde{O}(logs)$, and that the data-independent LSH actually achieves a $\tilde{O}(logs)$-approximation outside of those dense regions. Finally, we show how to “glue” together these two hashing schemes without any additional loss in the approximation. Beyond nearest neighbor search, our data-dependent LSH also gives optimal (distributional) sketches for the Earth Mover’s Distance. By known sketching lower bounds, this implies that our LSH is optimal (up to $\mathrm{poly}(loglogs)$ factors) among those that collide close points with constant probability.

Similar Work

• A Linear-time Approximation Of The Earth Movers Distance
• Set Similarity Search Beyond Minhash
• Approximate Nearest Neighbors In Limited Space
• Adaptive And Dynamic Multi-resolution Hashing For Pairwise Summations