Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/105472
Title: | The power of bounds : answering approximate Earth Mover's Distance with parametric bounds | Authors: | Chan, TN Yiu, ML Leong, Hou, U |
Issue Date: | Feb-2021 | Source: | IEEE transactions on knowledge and data engineering, Feb. 2021, v. 33, no. 2, p. 768-781 | Abstract: | 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. | Keywords: | Approximation framework Earth mover's distance Parametric bounds |
Publisher: | Institute of Electrical and Electronics Engineers | Journal: | IEEE transactions on knowledge and data engineering | ISSN: | 1041-4347 | EISSN: | 1558-2191 | DOI: | 10.1109/TKDE.2019.2931969 | Rights: | © 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The following publication T. N. Chan, M. L. Yiu and L. H. U, "The Power of Bounds: Answering Approximate Earth Mover's Distance with Parametric Bounds," in IEEE Transactions on Knowledge and Data Engineering, vol. 33, no. 2, pp. 768-781, 1 Feb. 2021 is available at https://doi.org/10.1109/TKDE.2019.2931969. |
Appears in Collections: | Journal/Magazine Article |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Chan_Power_Bounds_Answering.pdf | Pre-Published version | 2.03 MB | Adobe PDF | View/Open |
Page views
15
Citations as of Jul 7, 2024
Downloads
5
Citations as of Jul 7, 2024
SCOPUSTM
Citations
4
Citations as of Jul 4, 2024
WEB OF SCIENCETM
Citations
2
Citations as of Jul 4, 2024
![](/image/google_scholar.jpg)
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.