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

TY - GEN

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

AU - Wichterich, Marc

AU - Assent, Ira

AU - Philipp, Kranen

AU - Seidl, Thomas

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

U2 - 10.1145/1376616.1376639

DO - 10.1145/1376616.1376639

M3 - Article in proceedings

SN - 978-1-60558-102-6

SP - 199

EP - 212

BT - Proceedings of the 2008 ACM SIGMOD international conference on Management of data

ER -