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

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.


© ACM, 2008. This is the author’s version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM SIGMOD 2008. http://doi.acm.org/10.1145/1376616.1376639

Authors: Wichterich M., Assent I., Kranen P., Seidl T.
Published in: Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD 2008), Vancouver, BC, Canada.
Publisher: ACM - New York, NY, USA
Sprache: EN
Jahr: 2008

(full paper acceptance rate 17.9%)

Seiten: 199-212
ISBN: 9781605581026
Konferenz: SIGMOD
DOI: 10.1145/1376616.1376639
Typ: Tagungsbeiträge
Forschungsgebiet: Exploration of Multimedia Databases