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.

使用最近邻搜索来逼近地球移动距离（EMD），以实现高准确性、低时间复杂度和高内存效率；通过 GPU 的向量化进一步加快速度，比现有的近似 EMD 方法在图像分类和检索任务中达到 44 倍至 135 倍的速度优势，同时实现了更好的准确性、加速比和内存效率。