On constant factor approximation for earth mover distance over doubling metrics

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 $\mathrm{\mid }X\mathrm{\mid }=n$, we can use $\tilde{O}(n^2)$ preprocessing time to create a data structure of size $\tilde{O}(n^{1+\text{e}})$, such that subsequently queried EMDs can be $O({\alpha }_X\mathrm{/}\text{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\mathrm{.}Given$F(\mu)$and$F(\nu)$,theEMDbetween$\mu$and$\nu$canbe$O(\alpha_X/\e)$-approximatedin$\tilde O(n^\e)$ time.