Efficient Similarity Search Using the Earth Mover's Distance for Large Multimedia Databases

Multimedia similarity search in large databases requires efficient query processing. The Earth Mover's Distance, introduced in computer vision, is successfully used as a similarity model in a number of small-scale applications. Its computational complexity hindered its adoption in large multimedia databases.

We enable directly indexing the Earth Mover's Distance in structures such as the R-tree and the VA-file by providing the accurate 'MinDist' function to any bounding rectangle in the index. We exploit the computational structure of the new MinDist to derive a new lower bound for the EMD MinDist which is assembled from quantized partial solutions yielding very fast query processing times. We prove completeness of our approach in a multistep scheme. Extensive experiments on real world data demonstrate the high efficiency.

Authors: Assent I., Wichterich M., Meisen T., Seidl T.
Published in: Proc. IEEE 24th International Conference on Data Engineering (ICDE 2008), Cancun, Mexico.
Publisher: IEEE Computer Society - Washington, USA
Language: EN
Year: 2008
Additional:

(full paper acceptance rate 19.3%)

Pages: 307-316
ISBN: 9781424418374
Conference: ICDE
DOI:10.1109/ICDE.2008.4497439
Url:ICDE 2008
DOI: 10.1109/ICDE.2008.4497439
Type: Conference papers (peer reviewed)
Research topic: Exploration of Multimedia Databases