On constant factor approximation for earth mover distance over doubling metrics

Computer Science – Data Structures and Algorithms

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Extended abstract. An older version submitted to ICALP

Scientific paper

Given a metric space $(X,d_X)$, the earth mover distance between two distributions over $X$ is defined as the minimum cost of a bipartite matching between the two distributions. The doubling dimension of a metric $(X, d_X)$ is the smallest value $\alpha$ such that every ball in $X$ can be covered by $2^\alpha$ ball of half the radius. We study efficient algorithms for approximating earth mover distance over metrics with bounded doubling dimension. Given a metric $(X, d_X)$, with $|X| = n$, we can use $\tilde O(n^2)$ preprocessing time to create a data structure of size $\tilde O(n^{1 + \e})$, such that subsequently queried EMDs can be $O(\alpha_X/\e)$-approximated in $\tilde O(n)$ time. We also show a weaker form of sketching scheme, which we call "encoding scheme". Given $(X, d_X)$, by using $\tilde O(n^2)$ preprocessing time, every subsequent distribution $\mu$ over $X$ can be encoded into $F(\mu)$ in $\tilde O(n^{1 + \e})$ time. Given $F(\mu)$ and $F(\nu)$, the EMD between $\mu$ and $\nu$ can be $O(\alpha_X/\e)$-approximated in $\tilde O(n^\e)$ time.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

On constant factor approximation for earth mover distance over doubling metrics 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 On constant factor approximation for earth mover distance over doubling metrics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On constant factor approximation for earth mover distance over doubling metrics will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-373109

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.