On constant factor approximation for earth mover distance over doubling metrics

2010/02/22 by Shi Li, Li, Shi
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.1002.4034

Extended abstract. An older version submitted to ICALP

arxiv created 2010/02/22 · arxiv updated 2010/02/26

Abstract

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 α such that every ball in X can be covered by 2^α 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 O(n²) preprocessing time to create a data structure of size O(n^{1 + \e}), such that subsequently queried EMDs can be O(α_X/\e)-approximated in O(n) time. We also show a weaker form of sketching scheme, which we call "encoding scheme". Given (X, d_X), by using O(n²) preprocessing time, every subsequent distribution μ over X can be encoded into F(μ) in O(n^{1 + \e}) time. Given F(μ) and F(ν), the EMD between μ and ν can be O(α_X/\e)-approximated in O(n^\e) time.

Related

• Fine-Grained Complexity of Earth Mover’s Distance Under Translation
• Improved Approximation Algorithms for Earth-Mover Distance in Data Streams
• Sublinear Time Algorithms for Earth Mover's Distance
• Approximating the Earth Mover's Distance between sets of geometric objects
• Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair