UM
The Power of Bounds: Answering Approximate Earth Mover's Distance with Parametric Bounds
Chan,Tsz Nam1; Yiu,Man Lung1; Leong Hou,U.2
2021-02-01
Source PublicationIEEE Transactions on Knowledge and Data Engineering
ISSN1041-4347
Volume33Issue:2Pages:768-781
AbstractThe 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.
Keywordapproximation framework Earth mover's distance parametric bounds
DOI10.1109/TKDE.2019.2931969
URLView the original
Language英语
Fulltext Access
Citation statistics
Cited Times [WOS]:0   [WOS Record]     [Related Records in WOS]
Document TypeJournal article
CollectionUniversity of Macau
Corresponding AuthorChan,Tsz Nam
Affiliation1.Department of Computing,Hong Kong Polytechnic University,Hong Kong,Hong Kong
2.Department of Computer and Information Science,State Key Laboratory of Internet of Things for Smart City,University of Macau,Taipa,Macao
Recommended Citation
GB/T 7714
Chan,Tsz Nam,Yiu,Man Lung,Leong Hou,U.. The Power of Bounds: Answering Approximate Earth Mover's Distance with Parametric Bounds[J]. IEEE Transactions on Knowledge and Data Engineering,2021,33(2):768-781.
APA Chan,Tsz Nam,Yiu,Man Lung,&Leong Hou,U..(2021).The Power of Bounds: Answering Approximate Earth Mover's Distance with Parametric Bounds.IEEE Transactions on Knowledge and Data Engineering,33(2),768-781.
MLA Chan,Tsz Nam,et al."The Power of Bounds: Answering Approximate Earth Mover's Distance with Parametric Bounds".IEEE Transactions on Knowledge and Data Engineering 33.2(2021):768-781.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Chan,Tsz Nam]'s Articles
[Yiu,Man Lung]'s Articles
[Leong Hou,U.]'s Articles
Baidu academic
Similar articles in Baidu academic
[Chan,Tsz Nam]'s Articles
[Yiu,Man Lung]'s Articles
[Leong Hou,U.]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Chan,Tsz Nam]'s Articles
[Yiu,Man Lung]'s Articles
[Leong Hou,U.]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.