Erik Waingarten, University of Pennsylvania

Abstract

We give a new data-dependent LSH for the Earth Mover's Distance, and as a result improve on the approximation of nearest neighbor search for the Earth Mover's Distance by a quadratic factor. Our main technical contribution is to show that for any distribution supported on the EMD metric space, there exists a data-dependent LSH for dense regions of which achieves improved approximation, and that the data-independent LSH actually achieves a better outside of those dense regions. Finally, we “glue” together these two hashing schemes without any additional loss in the approximation.    

[Video]