2026-07-20T11:16:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:649 2024-03-06T11:06:52Z ddc:004 open_access

Efficient multi-step query processing for EMD-based similarity Assent, Ira Seidl, Thomas Content-based retrieval indexing multimedia databases efficiency similarity Similarity search in large multimedia databases requires ef- ficient query processing based on suitable similarity models. Similarity models consist of a feature extraction step as well as a distance defined for these features, and they demand an efficient algorithm for retrieving similar objects under this model. In this work, we focus on the Earth Movers Distance (EMD), a recently introduced similarity model which has been successfully employed in numerous applications and has been reported as well reflecting human perceptual similarity. As its computation is complex, the direct application of the EMD to large, high-dimensional databases is not feasible. To remedy this and allow users to benefit from the high quality of the model even in larger settings, we developed various lower bounds for the EMD to be used in index-supported multistep query processing algorithms. We prove that our algorithms are complete, thus producing no false drops. We also show that it is highly efficient as experiments on large image databases with high-dimensional features demonstrate. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ira Assent and Thomas Seidl 2006 Is Part Of Dagstuhl Seminar Proceedings, Volume 6171, Content-Based Retrieval (2006) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.06171.6 urn:nbn:de:0030-drops-6490 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06171.6 eng https://creativecommons.org/licenses/by/4.0/legalcode