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

Marc Wichterich, Ira Assent, Kranen Philipp, Thomas Seidl

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer 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.
TitelProceedings of the 2008 ACM SIGMOD international conference on Management of data
Antal sider14
ISBN (Trykt)978-1-60558-102-6
ISBN (Elektronisk)978-1-60558-102-6
StatusUdgivet - 2008
Udgivet eksterntJa


Dyk ned i forskningsemnerne om 'Efficient EMD-based Similarity Search in Multimedia Databases via Flexible Dimensionality Reduction'. Sammen danner de et unikt fingeraftryk.