Sublinear Time Algorithms for Earth Mover's Distance

Details Sublinear Time Algorithms for Earth Mover's Distance Sublinear Time Algorithms for Earth Mover's Distance

2009-04-02

arxiv.org/abs/0904.0292v1

Computer Science

Data Structures and Algorithms

12 pages

Scientific paper

We study the problem of estimating the Earth Mover's Distance (EMD) between probability distributions when given access only to samples. We give closeness testers and additive-error estimators over domains in $[0, \Delta]^d$, with sample complexities independent of domain size - permitting the testability even of continuous distributions over infinite domains. Instead, our algorithms depend on other parameters, such as the diameter of the domain space, which may be significantly smaller. We also prove lower bounds showing the dependencies on these parameters to be essentially optimal. Additionally, we consider whether natural classes of distributions exist for which there are algorithms with better dependence on the dimension, and show that for highly clusterable data, this is indeed the case. Lastly, we consider a variant of the EMD, defined over tree metrics instead of the usual L1 metric, and give optimal algorithms.

Affiliated with

Also associated with

No associations

Rating

Sublinear Time Algorithms for Earth Mover's Distance does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sublinear Time Algorithms for Earth Mover's Distance, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sublinear Time Algorithms for Earth Mover's Distance will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-63358