mlsanityData to 14 Oct 2026

Scalable Nearest Neighbor Search for Optimal Transport

arXiv 1910.04126 ↗First posted 9 Oct 2019cs.DScited by 25

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 11; 2022: 3; 2023: 4; 2024: 6; 2025: 0; 2026: 1.

25 papers.

Sort:

  1. 2021Multi-Vector Models with Textual Guidance for Fine-Grained Scientific Document Similaritycited by 35
  2. 2021Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structurescited by 19
  3. 2021Diffusion Earth Mover's Distance and Distribution Embeddingscited by 18
  4. 2023Editable User Profiles for Controllable Text Recommendationcited by 16
  5. 2021Sentence Similarity Based on Contextscited by 12
  6. 2021Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and Morecited by 11
  7. 2024Graph Edit Distance with General Costs Using Neural Set Divergencecited by 11
  8. 2021Supervised Tree-Wasserstein Distancecited by 10
  9. 2021Re-evaluating Word Mover's Distancecited by 10
  10. 2021Fixed Support Tree-Sliced Wasserstein Barycentercited by 10
  11. 2022Approximating 1-Wasserstein Distance with Treescited by 9
  12. 2024A New Robust Partial p-Wasserstein-Based Metric for Comparing Distributionscited by 7
13 more
  1. 2023Fast Optimal Transport through Sliced Wasserstein Generalized Geodesicscited by 5
  2. 2024Tree-Wasserstein Distance for High Dimensional Data with a Latent Feature Hierarchycited by 5
  3. 2021Landmarks Augmentation with Manifold-Barycentric Oversamplingcited by 4
  4. 2021Embedding Signals on Knowledge Graphs with Unbalanced Diffusion Earth Mover's Distancecited by 4
  5. 2023Neural approximation of Wasserstein distance via a universal architecture for symmetric and factorwise group invariant functionscited by 4
  6. 2022Learning Ultrametric Trees for Optimal Transport Regressioncited by 3
  7. 2024Efficient approximation of Earth Mover's Distance Based on Nearest Neighbor Searchcited by 3
  8. 2024Learning Structured Representations by Embedding Class Hierarchy with Fast Optimal Transportcited by 3
  9. 2022Budget-Constrained Bounds for Mini-Batch Estimation of Optimal Transportcited by 1
  10. 2021MURAL: An Unsupervised Random Forest-Based Embedding for Electronic Health Record Datacited by 0
  11. 2023An Empirical Study of Self-supervised Learning with Wasserstein Distancecited by 0
  12. 2024A Class of Topological Pseudodistances for Fast Comparison of Persistence Diagramscited by 0
  13. 2026Sierpi'nski--Knopp Wasserstein Distance for Persistence Diagrams and Applications to 2-Wasserstein Approximationcited by 0