Name
Abstract | ||
|---|---|---|
The Earth Mover Distance (EMD) between point sets A and B is the minimum cost of a bipartite matching between A and B. EMD is an important measure for estimating similarities between objects with quantifiable features and has important applications in several areas including computer vision. The streaming complexity of approximating EMD between point sets in a two-dimensional discretized grid is an important open problem proposed in [8,9]. We study the problem of approximating EMD in the streaming model, when points lie on a discretized circle. Computing the EMD in this setting has applications to computer vision [13] and can be seen as a special case of computing EMD on a discretized grid. We achieve a (1 ±ε) approximation for EMD in Õ (ε-3) space, for every 0ε |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-29344-3_9 | LATIN |
Keywords | Field | DocType |
b. emd,space-efficient approximation scheme,discretized grid,computer vision,approximating emd,important application,circular earth mover distance,point set,important open problem,discretized circle,two-dimensional discretized grid,important measure | Discretization,Combinatorics,Earth mover's distance,Open problem,Streaming algorithm,Computer science,Bipartite graph,Grid,Special case | Conference |
Volume | ISSN | Citations |
7256 | 0302-9743 | 3 |
PageRank | References | Authors |
0.39 | 17 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joshua Brody | 1 | 118 | 5.33 |
| Hongyu Liang | 2 | 84 | 16.39 |
| Xiaoming Sun | 3 | 280 | 41.19 |