License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06171.6
URN: urn:nbn:de:0030-drops-6490
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/649/
Go to the corresponding Portal

Assent, Ira ; Seidl, Thomas

Efficient multi-step query processing for EMD-based similarity

pdf-format:
06171.AssentIra.ExtAbstract.649.pdf (0.3 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{assent_et_al:DagSemProc.06171.6,
  author =	{Assent, Ira and Seidl, Thomas},
  title =	{{Efficient multi-step query processing for EMD-based similarity}},
  booktitle =	{Content-Based Retrieval},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6171},
  editor =	{Tim Crawford and Remco C. Veltkamp},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2006/649},
  URN =		{urn:nbn:de:0030-drops-6490},
  doi =		{10.4230/DagSemProc.06171.6},
  annote =	{Keywords: Content-based retrieval, indexing, multimedia databases, efficiency, similarity}
}

Keywords: Content-based retrieval, indexing, multimedia databases, efficiency, similarity
Collection: 06171 - Content-Based Retrieval
Issue Date: 2006
Date of publication: 19.09.2006

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI