TY - JOUR
T1 - The Power of Bounds
T2 - Answering Approximate Earth Mover's Distance with Parametric Bounds
AU - Chan, Tsz Nam
AU - Yiu, Man Lung
AU - Leong Hou, U.
N1 - Funding Information:
This work was supported by grant GRF152201/14E from the Hong Kong RGC. Leong Hou U was supported by MYRG-2016-00182- FST from UMAC RC.
PY - 2021/2/1
Y1 - 2021/2/1
N2 - 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.
AB - 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.
KW - approximation framework
KW - Earth mover's distance
KW - parametric bounds
UR - http://www.scopus.com/inward/record.url?scp=85099435844&partnerID=8YFLogxK
U2 - 10.1109/TKDE.2019.2931969
DO - 10.1109/TKDE.2019.2931969
M3 - Journal article
AN - SCOPUS:85099435844
SN - 1041-4347
VL - 33
SP - 768
EP - 781
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 2
ER -