Sublinear time algorithms for earth mover's distance

DOI10.1007/S00224-010-9265-8zbMATH Open1209.62001OpenAlexW2162375667MaRDI QIDQ633770FDOQ633770

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

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

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)

Cites Work

• The earth mover's distance as a metric for image retrieval
• Similarity estimation techniques from rounding algorithms
• A tight bound on approximating arbitrary metrics by tree metrics
• Title not available (Why is that?)
• On testing expansion in bounded-degree graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Testing of Clustering

Cited In (17)

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

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)