The Power of Bounds: Answering Approximate Earth Mover's Distance with Parametric Bounds

Tsz Nam CHAN*, Man Lung Yiu, U. Leong Hou

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish
Article number8781913
Pages (from-to)768-781
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Volume33
Issue number2
DOIs
Publication statusPublished - 1 Feb 2021

Scopus Subject Areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

User-Defined Keywords

  • approximation framework
  • Earth mover's distance
  • parametric bounds

Fingerprint

Dive into the research topics of 'The Power of Bounds: Answering Approximate Earth Mover's Distance with Parametric Bounds'. Together they form a unique fingerprint.

Cite this