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

Marc Wichterich, Ira Assent, Kranen Philipp, Thomas Seidl

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


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 date2008
ISBN (Print)978-1-60558-102-6
ISBN (Electronic)978-1-60558-102-6
Publication statusPublished - 2008
Externally publishedYes


Dive into the research topics of 'Efficient EMD-based Similarity Search in Multimedia Databases via Flexible Dimensionality Reduction'. Together they form a unique fingerprint.

Cite this