UM  > 科技學院  > 電腦及資訊科學系
Earth mover's distance based similarity search at scale
Tangy, Yu1; Uz, Leong Hou2; Caiy, Yilun1; Mamoulisy, Nikos1; Chengy, Reynold1
Source PublicationProceedings of the VLDB Endowment
AbstractEarth Mover's Distance (EMD), as a similarity measure, has received a lot of attention in the fields of multimedia and probabilistic databases, computer vision, image retrieval, machine learning, etc. EMD on multidimensional histograms provides better distinguishability between the objects approximated by the histograms (e.g., images), compared to classic measures like Euclidean distance. Despite its usefulness, EMD has a high computational cost; therefore, a number of effective filtering methods have been proposed, to reduce the pairs of histograms for which the exact EMD has to be computed, during similarity search. Still, EMD calculations in the refinement step remain the bottleneck of the whole similarity search process. In this paper, we focus on optimizing the refinement phase of EMD-based similarity search by (i) adapting an efficient min-cost flow algorithm (SIA) for EMD computation, (ii) proposing a dynamic distance bound, which can be used to terminate an EMD refinement early, and (iii) proposing a dynamic refinement order for the candidates which, paired with a concurrent EMD refinement strategy, reduces the amount of needless computations. Our proposed techniques are orthogonal to and can be easily integrated with the state-of-the-art filtering techniques, reducing the cost of EMD-based similarity queries by orders of magnitude. © 2013 VLDB Endowment 21508097/13/12.
The Source to ArticleEngineering Village
Fulltext Access
Document TypeJournal article
Affiliation1.The University of Hong Kong, Hong Kong;
2.University of Macau, China
Recommended Citation
GB/T 7714
Tangy, Yu,Uz, Leong Hou,Caiy, Yilun,et al. Earth mover's distance based similarity search at scale[J]. Proceedings of the VLDB Endowment,2013,7(4):313-324.
APA Tangy, Yu,Uz, Leong Hou,Caiy, Yilun,Mamoulisy, Nikos,&Chengy, Reynold.(2013).Earth mover's distance based similarity search at scale.Proceedings of the VLDB Endowment,7(4),313-324.
MLA Tangy, Yu,et al."Earth mover's distance based similarity search at scale".Proceedings of the VLDB Endowment 7.4(2013):313-324.
Related Services
Recommend this item
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Tangy, Yu]'s Articles
[Uz, Leong Hou]'s Articles
[Caiy, Yilun]'s Articles
Baidu academic
Similar articles in Baidu academic
[Tangy, Yu]'s Articles
[Uz, Leong Hou]'s Articles
[Caiy, Yilun]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Tangy, Yu]'s Articles
[Uz, Leong Hou]'s Articles
[Caiy, Yilun]'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.