Sublinear time algorithms for earth mover's distance

DOI10.1007/s00224-010-9265-8zbMath1209.62001OpenAlexW2162375667MaRDI QIDQ633770

Juan-Miguel Gracia

Publication date: 30 March 2011

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-010-9265-8

zbMATH Keywords

property testingearth mover's distancesublinear-time algorithms

Mathematics Subject Classification ID

Applications of graph theory (05C90) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Optimal Estimation of Wasserstein Distance on a Tree With an Application to Microbiome Studies, Estimation of Wasserstein distances in the spiked transport model, On computing discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions, The ultrametric Gromov-Wasserstein distance, Unnamed Item, Unnamed Item, Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance

Uses Software

• EMD

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The earth mover's distance as a metric for image retrieval
• On Testing Expansion in Bounded-Degree Graphs
• Similarity estimation techniques from rounding algorithms
• Testing of Clustering
• A tight bound on approximating arbitrary metrics by tree metrics