# Scalable Nearest Neighbor Search for Optimal Transport

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Oct 2019.

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

- [Multi-Vector Models with Textual Guidance for Fine-Grained Scientific Document Similarity](https://mlsanity.com/paper/2111.08366/) (2021)
- [Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures](https://mlsanity.com/paper/2111.15139/) (2021)
- [Diffusion Earth Mover's Distance and Distribution Embeddings](https://mlsanity.com/paper/2102.12833/) (2021)
- [Editable User Profiles for Controllable Text Recommendation](https://mlsanity.com/paper/2304.04250/) (2023)
- [Sentence Similarity Based on Contexts](https://mlsanity.com/paper/2105.07623/) (2021)
- [Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More](https://mlsanity.com/paper/2107.06876/) (2021)
- [Graph Edit Distance with General Costs Using Neural Set Divergence](https://mlsanity.com/paper/2409.17687/) (2024)
- [Supervised Tree-Wasserstein Distance](https://mlsanity.com/paper/2101.11520/) (2021)
- [Re-evaluating Word Mover's Distance](https://mlsanity.com/paper/2105.14403/) (2021)
- [Fixed Support Tree-Sliced Wasserstein Barycenter](https://mlsanity.com/paper/2109.03431/) (2021)
- [Approximating 1-Wasserstein Distance with Trees](https://mlsanity.com/paper/2206.12116/) (2022)
- [A New Robust Partial p-Wasserstein-Based Metric for Comparing Distributions](https://mlsanity.com/paper/2405.03664/) (2024)
- [Fast Optimal Transport through Sliced Wasserstein Generalized Geodesics](https://mlsanity.com/paper/2307.01770/) (2023)
- [Tree-Wasserstein Distance for High Dimensional Data with a Latent Feature Hierarchy](https://mlsanity.com/paper/2410.21107/) (2024)
- [Landmarks Augmentation with Manifold-Barycentric Oversampling](https://mlsanity.com/paper/2104.00925/) (2021)
- [Embedding Signals on Knowledge Graphs with Unbalanced Diffusion Earth Mover's Distance](https://mlsanity.com/paper/2107.12334/) (2021)
- [Neural approximation of Wasserstein distance via a universal architecture for symmetric and factorwise group invariant functions](https://mlsanity.com/paper/2308.00273/) (2023)
- [Learning Ultrametric Trees for Optimal Transport Regression](https://mlsanity.com/paper/2210.12288/) (2022)
- [Efficient approximation of Earth Mover's Distance Based on Nearest Neighbor Search](https://mlsanity.com/paper/2401.07378/) (2024)
- [Learning Structured Representations by Embedding Class Hierarchy with Fast Optimal Transport](https://mlsanity.com/paper/2410.03052/) (2024)
- [Budget-Constrained Bounds for Mini-Batch Estimation of Optimal Transport](https://mlsanity.com/paper/2210.13630/) (2022)
- [MURAL: An Unsupervised Random Forest-Based Embedding for Electronic Health Record Data](https://mlsanity.com/paper/2111.10452/) (2021)
- [An Empirical Study of Self-supervised Learning with Wasserstein Distance](https://mlsanity.com/paper/2310.10143/) (2023)
- [A Class of Topological Pseudodistances for Fast Comparison of Persistence Diagrams](https://mlsanity.com/paper/2402.14489/) (2024)
- [Sierpi'nski--Knopp Wasserstein Distance for Persistence Diagrams and Applications to 2-Wasserstein Approximation](https://mlsanity.com/paper/2609.01528/) (2026)

## Abstract (arXiv)

The Optimal Transport (a.k.a. Wasserstein) distance is an increasingly popular similarity measure for rich data domains, such as images or text documents. This raises the necessity for fast nearest neighbor search algorithms according to this distance, which poses a substantial computational bottleneck on massive datasets. In this work we introduce Flowtree, a fast and accurate approximation algorithm for the Wasserstein-1 distance. We formally analyze its approximation factor and running time. We perform extensive experimental evaluation of nearest neighbor search algorithms in the W1 distance on real-world dataset. Our results show that compared to previous state of the art, Flowtree achieves up to 7.4 times faster running time.