# Data-Dependent LSH for the Earth Mover's Distance

arXiv: https://arxiv.org/abs/2403.05041 · HTML: https://mlsanity.com/paper/2403.05041/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Mar 2024.

## Built on by (most cited first, 1 of 1)

- [Learning Partition Trees for Nearest Neighbor Search](https://mlsanity.com/paper/2607.09909/) (2026)

## Abstract (arXiv)

We give new data-dependent locality sensitive hashing schemes (LSH) for the Earth Mover's Distance (mathsfEMD), and as a result, improve the best approximation for nearest neighbor search under mathsfEMD by a quadratic factor. Here, the metric mathsfEMDs(ℝd,ℓp) consists of sets of s vectors in ℝd, and for any two sets x,y of s vectors the distance mathsfEMD(x,y) is the minimum cost of a perfect matching between x,y, where the cost of matching two vectors is their ℓp distance. Previously, Andoni, Indyk, and Krauthgamer gave a (data-independent) locality-sensitive hashing scheme for mathsfEMDs(ℝd,ℓp) when p ∈ [1,2] with approximation O(log2 s). By being data-dependent, we improve the approximation to tildeO(log s). Our main technical contribution is to show that for any distribution μ supported on the metric mathsfEMDs(ℝd, ℓp), there exists a data-dependent LSH for dense regions of μ which achieves approximation tildeO(log s), and that the data-independent LSH actually achieves a tildeO(log s)-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 poly(log log s) factors) among those that collide close points with constant probability.