Tutorial: Distance-based Multimedia Indexing



Concomitant with the explosive growth of the digital universe, an immensely increasing amount of multimedia data is generated, processed, and finally stored in very large multimedia databases. The rapid expansion of the internet and the extensive spread of mobile devices allow users to generate and share multimedia data everywhere and at any time. As a result, multimedia databases tend to grow continuously without any restriction and are thus no longer manually manageable by humans. Automatic approaches that allow for effective and efficient information access to massive multimedia databases become immensely important.


Multimedia retrieval approaches are one class of information access approaches that allow to manage and access multimedia databases with respect to the users' information needs. These approaches deal with the representation, storage, organization of, and access to information items. In fact, they can be thought of approaches allowing users to search, browse, explore, and analyze multimedia databases by means of similarity relations among multimedia objects.

One promising and widespread approach to define similarity between multimedia objects consists in automatically extracting inherent properties of multimedia objects and comparing them with each other. For this purpose, the content-based properties of multimedia objects are modeled by feature representations which are comparable by means of distance-based similarity measures. This class of similarity measures follows a rigorous mathematical interpretation and allows domain experts and database experts to address the issues of effectiveness and efficiency simultaneously and independently. In fact, it has become mandatory for current distance-based similarity measures to be indexable in order to facilitate large-scale applicability.


Tutorial Outline


In this tutorial, we aim at providing a unified and comprehensive overview of the state-of-the-art approaches to distance-based multimedia indexing. We intend to cover a broad target audience starting from beginners to experts in the domain of distance-based similarity search in multimedia databases and adjacent research fields which utilize distance-based approaches. No prerequisite knowledge is needed.

We begin with outlining different approaches to object representations including the feature extraction process and suitable feature representation models as well as clustering-based computations in order to answer the question of how to model multimedia data objects in a compact and generic way. In the second part of this tutorial, we present state-of-the-art similarity and dissimilarity measures including kernels and distance functions in order to complete our understanding of a similarity model. The third part is devoted to approaches for efficient query processing. After introducing similarity queries, we show how to process such queries efficiently by means of multi-step filter-and-refinement algorithms and lower bounding. The last part finally covers indexing approaches for distance-based similarity models where we discuss the fundamentals of spatial indexing, high-dimensional indexing, as well as metric and ptolemaic indexing.


Tutorial Structure


  • Object Representation
    • Feature Extraction
    • Feature Representations
    • Clustering-based Computation
  • Fundamental Similarity Models
    • Similarity Measures
    • Dissimilarity Measures
  • Efficient Query Processing
    • Similarity Queries
    • Multi-step Algorithms
    • Lower Bounding
  • Indexing
    • Spatial Indexing
    • High-dimensional Indexing
    • Metric and Ptolemaic Indexing


About the Presenters

Dr. Christian Beecks

Christian Beecks is a postdoctoral researcher in the data management and data exploration group at RWTH Aachen University, Germany. His research interests include efficient content-based multimedia retrieval and exploration, adaptive distance-based similarity measures such as the Earth Mover's Distance, Signature Quadratic Form Distance, and Signature Matching Distance, as well as metric and Ptolemaic indexing.

Merih Seran Uysal

Merih Seran Uysal is a researcher pursuing a PhD in the data management and data exploration group at RWTH Aachen University, Germany. Her research interests include similarity search in multimedia databases and efficient query processing based on adaptive distance-based similarity measures, in particular the Earth Mover's Distance and the Signature Quadratic Form Distance.

Prof. Dr. Thomas Seidl

Thomas Seidl is a professor for computer science and head of the data management and data exploration group at RWTH Aachen University, Germany. His research interests include data mining and database technology for multimedia and spatio-temporal databases in engineering, communication and life science applications. Prof. Seidl received his Diplom (MSc) in 1992 from TU Muenchen and his PhD (1997) and venia legendi (2001) from LMU Muenchen. He is active member of several program committees including ACM SIGKDD, IEEE ICDE, SDM, recent MultiClust-Workshops and others. He is member of the editorial board of The VLDB Journal as associate editor.