# Efficient approximation of Earth Mover's Distance Based on Nearest Neighbor Search

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 81 references that are in the map.
- First posted on arXiv 14 Jan 2024.

## Builds on (most cited first, 30 of 33)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Benchmarking Neural Network Robustness to Common Corruptions and Perturbations](https://mlsanity.com/paper/1903.12261/) (2019)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Accelerating 3D Deep Learning with PyTorch3D](https://mlsanity.com/paper/2007.08501/) (2020)
- [Deep Photo Style Transfer](https://mlsanity.com/paper/1703.07511/) (2017)
- [Morphing and Sampling Network for Dense Point Cloud Completion](https://mlsanity.com/paper/1912.00280/) (2019)
- [Density-aware Chamfer Distance as a Comprehensive Metric for Point Cloud Completion](https://mlsanity.com/paper/2111.12702/) (2021)
- [Smooth and Sparse Optimal Transport](https://mlsanity.com/paper/1710.06276/) (2017)
- [Generative Modeling with Optimal Transport Maps](https://mlsanity.com/paper/2110.02999/) (2021)
- [Low-Rank Sinkhorn Factorization](https://mlsanity.com/paper/2103.04737/) (2021)
- [HistoGAN: Controlling Colors of GAN-Generated and Real Images via Color Histograms](https://mlsanity.com/paper/2011.11731/) (2020)
- [Regularized Discrete Optimal Transport](https://mlsanity.com/paper/1307.5551/) (2013)
- [Tree-Sliced Variants of Wasserstein Distances](https://mlsanity.com/paper/1902.00342/) (2019)
- [Point-set Distances for Learning Representations of 3D Point Clouds](https://mlsanity.com/paper/2102.04014/) (2021)
- [Emerging from Water: Underwater Image Color Correction Based on Weakly Supervised Color Transfer](https://mlsanity.com/paper/1710.07084/) (2017)
- [Statistical Optimal Transport via Factored Couplings](https://mlsanity.com/paper/1806.07348/) (2018)
- [Word Mover's Embedding: From Word2Vec to Document Embedding](https://mlsanity.com/paper/1811.01713/) (2018)
- [Scalable Nearest Neighbor Search for Optimal Transport](https://mlsanity.com/paper/1910.04126/) (2019)
- [Hierarchical Sliced Wasserstein Distance](https://mlsanity.com/paper/2209.13570/) (2022)
- [DPDist : Comparing Point Clouds Using Deep Point Cloud Distance](https://mlsanity.com/paper/2004.11784/) (2020)
- [Screening Sinkhorn Algorithm for Regularized Optimal Transport](https://mlsanity.com/paper/1906.08540/) (2019)
- [Diffusion Earth Mover's Distance and Distribution Embeddings](https://mlsanity.com/paper/2102.12833/) (2021)
- [Sobolev Transport: A Scalable Metric for Probability Measures with Graph Metrics](https://mlsanity.com/paper/2202.10723/) (2022)
- [DOTmark - A Benchmark for Discrete Optimal Transport](https://mlsanity.com/paper/1610.03368/) (2016)
- [Geodesic Sinkhorn for Fast and Accurate Optimal Transport on Manifolds](https://mlsanity.com/paper/2211.00805/) (2022)
- [An Overview of Color Transfer and Style Transfer for Images and Videos](https://mlsanity.com/paper/2204.13339/) (2022)
- [Approximation algorithms for 1-Wasserstein distance between persistence diagrams](https://mlsanity.com/paper/2104.07710/) (2021)
- [Iterative Manifold Embedding Layer Learned by Incomplete Data for Large-scale Image Retrieval](https://mlsanity.com/paper/1707.09862/) (2017)

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

- [MedSynapse-V: Bridging Visual Perception and Clinical Intuition via Latent Memory Evolution](https://mlsanity.com/paper/2604.26283/) (2026)
- [MS-COOT: Comparing Morse-Smale Complexes with Co-Optimal Transport](https://mlsanity.com/paper/2606.08258/) (2026)
- [TopoAgent: An Agentic Framework for Automated Topology Learning in Medical Imaging](https://mlsanity.com/paper/2606.29763/) (2026)

## Abstract (arXiv)

Earth Mover's Distance (EMD) is an important similarity measure between two distributions, used in computer vision and many other application domains. However, its exact calculation is computationally and memory intensive, which hinders its scalability and applicability for large-scale problems. Various approximate EMD algorithms have been proposed to reduce computational costs, but they suffer lower accuracy and may require additional memory usage or manual parameter tuning. In this paper, we present a novel approach, NNS-EMD, to approximate EMD using Nearest Neighbor Search (NNS), in order to achieve high accuracy, low time complexity, and high memory efficiency. The NNS operation reduces the number of data points compared in each NNS iteration and offers opportunities for parallel processing. We further accelerate NNS-EMD via vectorization on GPU, which is especially beneficial for large datasets. We compare NNS-EMD with both the exact EMD and state-of-the-art approximate EMD algorithms on image classification and retrieval tasks. We also apply NNS-EMD to calculate transport mapping and realize color transfer between images. NNS-EMD can be 44x to 135x faster than the exact EMD implementation, and achieves superior accuracy, speedup, and memory efficiency over existing approximate EMD methods.