Journal
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
Volume 33, Issue 2, Pages 768-781Publisher
IEEE COMPUTER SOC
DOI: 10.1109/TKDE.2019.2931969
Keywords
Earth mover's distance; parametric bounds; approximation framework
Categories
Funding
- Hong Kong RGC [GRF152201/14E]
- UMAC RC [MYRG-2016-00182-FST]
Ask authors/readers for more resources
EMD is a robust measure of similarity between two histograms, widely used in various fields. Despite the computationally intensive nature, efficient upper and lower bound functions have been developed without error guarantee. This study focuses on computing an approximate EMD value with bounded error, proposing solutions that demonstrate efficiency and effectiveness through experimental results.
The Earth Mover's Distance (EMD) is a robust similarity measure between two histograms (e.g., probability distributions). It has been extensively used in a wide range of applications, e.g., multimedia, data mining, computer vision, etc. As EMD is a computationally intensive operation, many efficient lower and upper bound functions of EMD have been developed. However, they provide no guarantee on the error. In this work, we study how to compute approximate EMD value with bounded error. First, we develop a parametric dual bound function for EMD, in order to offer sufficient trade-off points for optimization. After that, we propose an approximation framework that leverages on lower and upper bound functions to compute approximate EMD with error guarantee. Then, we present three solutions to solve our problem. Experimental results on real data demonstrate the efficiency and the effectiveness of our proposed solutions.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available