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

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

  • Ira Assent
  • Marc Wichterich, RWTH Aachen University, Germany
  • Tobias Meisen, RWTH Aachen University, Germany
  • Thomas Seidl, RWTH Aachen University, Germany
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.
Original languageEnglish
Title of host publicationIEEE 24th International Conference on Data Engineering, 2008. ICDE 2008.
Number of pages10
Publication year2008
ISBN (print)978-1-4244-1836-7
ISBN (Electronic)978-1-4244-1836-7
Publication statusPublished - 2008
Externally publishedYes

See relations at Aarhus University Citationformats

ID: 47659884