Data-Dependent LSH for the Earth Mover's Distance

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