Research map / Learning theory and algorithms / Optimal transport
Linear-Complexity Data-Parallel Earth Mover’s Distance Approximations
Kubilay Atasu, Thomas Mittelholzer
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add ACT constrained-transfer iterations, increasing from 1 to 3 (ablation) | ACT · MNIST without background | precision @ top-128: 0.8997 -> 0.9014 | Improved |
| add ACT constrained-transfer iterations, increasing from 1 to 7 (ablation) | ACT · MNIST without background | precision @ top-128: 0.8997 -> 0.9016 | Improved |
| add ACT constrained-transfer iterations, increasing from 7 to 15 (ablation) | ACT · MNIST with background | precision @ top-128: 0.8872 -> 0.8999 | Improved |
| include background pixels in the histogram representation (ablation) | RWMD · MNIST | precision @ top-1: 0.9752 -> 0.1123 | Hurt |
| include background pixels in the histogram representation (ablation) | OMR · MNIST | precision @ top-128: The paper reports 0.8692 with background; no without-background OMR value is reported. | Mixed |
| use OMR's overlapping-mass reduction instead of RWMD (ablation) | EMD approximation · MNIST with background | precision @ top-1: 0.1123 -> 0.9707 | Improved |
| use ACT-15 instead of ACT-7 (ablation) | ACT · MNIST with background | precision @ top-16: 0.9470 -> 0.9520 | Improved |
| use ACT-1 instead of BoW cosine similarity | nearest-neighbor search · 20 Newsgroups | precision @ top-ℓ: 4.5% to 7.5% higher search accuracy | Improved |
| use ACT-1 instead of RWMD | nearest-neighbor search · 20 Newsgroups | precision @ top-ℓ: 2% to 3.5% higher search accuracy | Improved |
| use ACT-1 instead of WMD | nearest-neighbor search · 20 Newsgroups | runtime: approximately 20000-fold faster | Improved |
| use ACT-7 instead of WMD | nearest-neighbor search · 20 Newsgroups | search accuracy: approximately 10000-fold faster; slightly higher search accuracy | Improved |
| use ACT-1 instead of Sinkhorn | nearest-neighbor search · MNIST | search accuracy: four orders of magnitude faster; higher search accuracy | Improved |
Closest papers by meaning
- On Computing Diverse Solutions in the Earth Movers Distance (NeurIPS 2026 · similarity 0.90)
- Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration (NeurIPS 2017 · similarity 0.86)
- A Direct tilde{O}(1/epsilon) Iteration Parallel Algorithm for Optimal Transport (NeurIPS 2019 · similarity 0.86)
- Diffusion Earth Mover’s Distance and Distribution Embeddings (ICML 2021 · similarity 0.85)
- Near-Linear Time Generalized Sinkhorn Algorithms for Bounded Genus Graphs (NeurIPS 2026 · similarity 0.81)
- Learning Distances from Data with Normalizing Flows and Score Matching (ICML 2025 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
