Sublinear time algorithms for earth mover's distance

DOI10.1007/S00224-010-9265-8MaRDI QIDQ633770zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Optimal algorithms for testing closeness of discrete distributions
• Space-Efficient Approximation Scheme for Circular Earth Mover Distance
• Testing closeness of discrete distributions
• Which Distribution Distances are Sublinearly Testable?
• Sketching earth-mover distance on graph metrics

Cites work

• scientific article; zbMATH DE number 6381629 (Why is no real title available?)
• scientific article; zbMATH DE number 5485550 (Why is no real title available?)
• scientific article; zbMATH DE number 5764809 (Why is no real title available?)
• A tight bound on approximating arbitrary metrics by tree metrics
• On testing expansion in bounded-degree graphs
• Similarity estimation techniques from rounding algorithms
• Testing of Clustering
• The earth mover's distance as a metric for image retrieval

Cited in

(17)

• Optimal Estimation of Wasserstein Distance on a Tree With an Application to Microbiome Studies
• scientific article; zbMATH DE number 7758314 (Why is no real title available?)
• Testing properties of collections of distributions
• Testing distributional assumptions of learning algorithms
• Projection-based techniques for high-dimensional optimal transport problems
• The ultrametric Gromov-Wasserstein distance
• Privacy-Preserving Computation of the Earth Mover’s Distance
• Sketching earth-mover distance on graph metrics
• Sublinear Distance Labeling
• Space-Efficient Approximation Scheme for Circular Earth Mover Distance
• Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance
• FPTAS for Minimizing Earth Mover’s Distance under Rigid Transformations
• A generalization for the expected value of the earth mover's distance
• On computing discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions
• Estimation of Wasserstein distances in the spiked transport model
• Algorithms and Computation
• Computing and Combinatorics

Describes a project that uses

Uses Software

• EMD

This page was built for publication: Sublinear time algorithms for earth mover's distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q633770)