Efficient EMD-based Similarity Search in Multimedia Databases via Flexible Dimensionality Reduction

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Marc Wichterich, RWTH Aachen University, Germany
  • Ira Assent
  • Kranen Philipp, RWTH Aachen University, Germany
  • Thomas Seidl, RWTH Aachen University, Germany
The Earth Mover's Distance (EMD) was developed in computer vision as a flexible similarity model that utilizes similarities in feature space to define a high quality similarity measure in feature representation space. It has been successfully adopted in a multitude of applications with low to medium dimensionality. However, multimedia applications commonly exhibit high-dimensional feature representations for which the computational complexity of the EMD hinders its adoption. An efficient query processing approach that mitigates and overcomes this effect is crucial. We propose novel dimensionality reduction techniques for the EMD in a filter-and-refine architecture for efficient lossless retrieval. Thorough experimental evaluation on real world data sets demonstrates a substantial reduction of the number of expensive high-dimensional EMD computations and thus remarkably faster response times. Our techniques are fully flexible in the number of reduced dimensions, which is a novel feature in approximation techniques for the EMD.
Original languageEnglish
Title of host publicationProceedings of the 2008 ACM SIGMOD international conference on Management of data
Number of pages14
Publication year2008
Pages199-212
ISBN (print)978-1-60558-102-6
ISBN (Electronic)978-1-60558-102-6
DOIs
Publication statusPublished - 2008
Externally publishedYes

See relations at Aarhus University Citationformats

ID: 47659907