Adaptable transformation-based similarity search in multimedia databases [Elektronische Ressource] / vorgelegt von Marc Wichterich
287 pages

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Adaptable transformation-based similarity search in multimedia databases [Elektronische Ressource] / vorgelegt von Marc Wichterich

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
287 pages
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Adaptable Transformation-BasedSimilarity Search in MultimediaDatabasesVon der Fakultät für Mathematik, Informatik und Naturwissenschaften der RWTHAachen University zur Erlangung des akademischen Grades eines Doktors derNaturwissenschaften genehmigte Dissertationvorgelegt vonDiplom-InformatikerMarc Wichterichaus HaanBerichter: Universitätsprofessor Dr. rer. nat. Thomas Seidl Dr. rer. nat. Andreas HenrichTag der mündlichen Prüfung: 12.10.2010Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online verfügbar.To those who supported me during the past five years.ContentsAbstract / Zusammenfassung 1I Introduction to Distance-Based Similarity Search 51 Distance-Based Similarity Model 91.1 Object Feature Representations . . . . . . . . . . . . . . . . . . . . . 91.2 Distance Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 Distance-Based Similarity Queries 192.1 Range Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.2 Nearest Neighbor Queries . . . . . . . . . . . . . . . . . . . . . . . . 212.3 Ranking Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 Efficient Similarity Query Processing 253.1 Lower Bounds and Multi-Step . . . . . . . . . . . . . . 253.2 Indexing Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 An Example for Similarity Search Using Simple Distance Mea-sures 314.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . .

Sujets

Informations

Publié par
Publié le 01 janvier 2010
Nombre de lectures 22
Poids de l'ouvrage 24 Mo

Extrait

Adaptable Transformation-Based
Similarity Search in Multimedia
Databases
Von der Fakultät für Mathematik, Informatik und Naturwissenschaften der RWTH
Aachen University zur Erlangung des akademischen Grades eines Doktors der
Naturwissenschaften genehmigte Dissertation
vorgelegt von
Diplom-Informatiker
Marc Wichterich
aus Haan
Berichter: Universitätsprofessor Dr. rer. nat. Thomas Seidl Dr. rer. nat. Andreas Henrich
Tag der mündlichen Prüfung: 12.10.2010
Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online verfügbar.To those who supported me during the past five years.Contents
Abstract / Zusammenfassung 1
I Introduction to Distance-Based Similarity Search 5
1 Distance-Based Similarity Model 9
1.1 Object Feature Representations . . . . . . . . . . . . . . . . . . . . . 9
1.2 Distance Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 Distance-Based Similarity Queries 19
2.1 Range Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Nearest Neighbor Queries . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3 Ranking Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 Efficient Similarity Query Processing 25
3.1 Lower Bounds and Multi-Step . . . . . . . . . . . . . . 25
3.2 Indexing Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4 An Example for Similarity Search Using Simple Distance Mea-
sures 31
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.3 Dimensionality Reduction for the Voronoi Approach to NN Search 38
4.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
iii CONTENTS
II Transformation-Based Distance Measures 57
5 The Edit Distance 61
5.1 Formal Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.2 Illustration of Core Concepts of Transformation-Based Distances 63
5.3 Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6 The Dynamic Time Warping Distance 67
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.2 Formal Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.3 Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
7 The Earth Mover’s Distance 75
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
7.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
7.3 Formal Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
7.4 Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
7.5 Approximations of the EMD . . . . . . . . . . . . . . . . . . . . . . . 86
III Fast Searching with the Earth Mover’s Distance 91
8 Efficient Search Via Flexible Dimensionality Reduction 95
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
8.2 Dimensionality Reduction for the EMD . . . . . . . . . . . . . . . . 97
8.3 Query Processing Algorithm . . . . . . . . . . . . . . . . . . . . . . . 113
8.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
8.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
9 Direct Indexing and Vector Approximation 127
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
9.2 Direct Indexing of the EMD . . . . . . . . . . . . . . . . . . . . . . . 129
9.3 Vector Approximation for the EMD . . . . . . . . . . . . . . . . . . 133
9.4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
9.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148CONTENTS iii
IV Effective Searching with the Earth Mover’s Distance 149
10 Metric Adaptation of the Earth Mover’s Distance 153
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
10.2 Mathematical Framework for Adapting a Metric EMD . . . . . . . 154
10.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
11 Exploring Multimedia Databases via Relevance Feedback 169
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
11.2 Relevance Feedback with the Earth Mover’s Distance . . . . . . . 172
11.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
11.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
V The Earth Mover’s Distance in Context of Structured
Objects 197
12 Feature-Based Graph Similarity with the Earth Mover’s Dis-
tance 201
12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
12.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
12.3 Graph Similarity Model . . . . . . . . . . . . . . . . . . . . . . . . . 204
12.4 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 209
12.5 Summary and Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . 213
13 Reducing the Number of DTW Ground Distance Computations 215
13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
13.2 Anticipatory DTW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
13.3 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
13.4 Summary and Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . 239iv CONTENTS
VI Summary and Outlook 241
VII Appendices I
Naming Conventions III
List of Symbols V
List of Algorithms VII
Bibliography IX
Collaboration / Acknowledgments XXIX
List of Publications XXXIII
Curriculum Vitae XXXVAbstract
Efficient and effective methods of making data accessible to its consumers – be
they humans or algorithms – are crucial for turning ever-growing data dumps
into data mines.
Of particular importance to the user are access methods that allow for query-
based searching of databases. However, for vast collections of complex data
objects such as digital image libraries and music databases, querying methods
that necessitate an accurate, algebraic description of what the user is looking
for cannot cover all search needs. For instance, a prototypical object might be
known to the user and yet he or she may be unable to describe which qualities
make the object prototypical. Similarity search systems based on the query-by-
example paradigm can help the user in such situations by retrieving objects from
the database that exhibit a high degree of similarity to the prototypical query
object. For this purpose, the system must decide algorithmically which objects
are to be deemed similar to each other.
After giving an introduction and reviewing preliminaries in parts I and II,
the following three parts of this thesis address novel techniques regarding the
efficiency, effectiveness, and applicability of a particularly intuitive and flexible
class of distance measures where the distance (i.e., dissimilarity) between two
objects is modeled as the minimum amount of work that is required for trans-
forming the feature representation of one object into the feature representation
of the other. As the cost of transforming a feature into another can be chosen
depending on the features at hand, these transformation-based distance mea-
sures are highly adaptable and do not assume that the underlying features are
perceptually independent.
1Zusammenfassung
Mit dem stetigen Größenzuwachs heutiger Multimedia-Datenbanken laufen die-
se Gefahr, zu reinen Datenhalden zu verkommen. Um dies zu verhindern, sind
Methoden, welche einen effizienten und effektiven Zugriff auf die Daten er-
möglichen, für den Benutzer (ob Mensch oder Algorithmus) von hohem Stel-
lenwert. Aus Benutzersicht kommt hierbei anfragebasierten Suchmethoden eine
besondere Bedeutung zu. Allerdings können für Multimedia-Datensammlungen
nicht alle Suchbedarfe mittels exakten, algebraischen Anfragebeschreibungen
abgedeckt werden. So mag dem Benutzer ein prototypisches Bild oder Musik-
stück bekannt sein, ohne dass es ihm/ihr möglich ist, formal zu beschreiben,
welche Eigenschaften den prototypischen Charakter ausmachen. Systeme zur
Ähnlichkeitssuche, welche auf dem query-by-example Paradigma beruhen, kön-
nen dem Benutzer helfen, die Datenbank nach Objekten mit einem hohen Grad
an Ähnlichkeit zum Prototyp zu durchsuchen. Hierfür muss das System auf
algorithmische Weise entscheiden, welche Objekte zueinander ähnlich sind.
Nach einer Einleitung und einem Überblick über die Grundlagen der Ar-
beit in den Teilen I und II, zeigen die darauf folgenden drei Teile Techniken
auf, welche die Effizienz, die Effektivität und die Anwendbarkeit einer beson-
ders flexiblen und intuitiven Klasse von Distanzmaßen betreffen. Die Distanz
zweier Objekte wird hier als Maß für die Unähnlichkeit dieser interpretiert und
als minimales Pensum an Arbeit modelliert, welches für die Umwandlung der
Merkmalsrepräsentation des einen Objekts in die des anderen aufzuwenden ist.
Da die Kosten der f&#

  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents