Index Structures for Similarity Search in Multimedia Databases

Zitieren

Dateien zu dieser Ressource

Prüfsumme: MD5:48392ab9434550ba3400696608d5d42b

BUSTOS CÁRDENAS, Benjamin Eugenio, 2006. Index Structures for Similarity Search in Multimedia Databases [Dissertation]. Konstanz: University of Konstanz

@phdthesis{BustosCardenas2006Index-6104, title={Index Structures for Similarity Search in Multimedia Databases}, year={2006}, author={Bustos Cárdenas, Benjamin Eugenio}, address={Konstanz}, school={Universität Konstanz} }

application/pdf eng Bustos Cárdenas, Benjamin Eugenio Index Structures for Similarity Search in Multimedia Databases Im Arbeitsbereich der Multimedia-Datenbanksysteme ist die Suche ähnlicher Objekte ein wichtiges Forschungsgebiet. Für die meisten Anwendungen in Multimedia-Datenbanken ist eine exakte Suche nicht sinnvoll. Deshalb wurde viel Mühe darauf verwendet, effiziente und effektive Methoden der Ähnlichkeitssuche zu entwickeln. Eine weit verbreitete Methode für die Implementierung der Ähnlichkeitssuche ist die auf Objekteigenschaften basierende Methode. Diese Methode transformiert alle multimediale Objekte, die in einer Datenbank gespeichert sind, in hochdimensionale Feature-Vektoren. Nach der Transformation werden diese Feature-Vektoren in einen Indexstruktur eingefügt, um so effiziente Ähnlichkeitssuchen durchzuführen.<br /><br />Diese Dissertation trägt dazu bei neuartige Lösungen vorzuschlagen, indem sie erforscht wie die Effizienz der Ähnlichkeitssuche verbessert werden kann. Die Dissertation beginnt mit einer Untersuchung, wie man die Effektivität (d.h. die Qualität der Ergebnisse) der Ähnlichkeitssuche verbessern kann. Es wird aufgezeigt, dass mit Kombinationen von Feature-Vektoren die Effektivität der Ähnlichkeitssuche bedeutsam erweitert werden kann. Es werden Methoden vorgestellt, um Suchobjektsabhängig Gewichte für lineare Kombinationen von Feture-Vektoren zu berechnen, was die Effektivität der Ähnlichkeitssuche weiter verbessern kann. Das Design und die Analyse von neuen Indexstrukturen sind notwendig, um Ähnlichkeitsanfragen mit Kombinationen von Feature-Vektoren effizient durchzuführen, denn bislang können fast alle Indexstrukturen für Ähnlichkeitssuche nur individuelle Feature-Vektoren indizieren. Dies begründete die besondere Motivation, der in der restlichen Dissertation erforschten Methoden.<br /><br />Im zweiten Teil der Dissertation werden verschiedene Algorithmen und Indexstrukturen vorgeschlagen, um die Effizienz der Ähnlichkeitssuche zu verbessern. Zuerst werden Techniken zur Auswahl von Pivots für Pivotbasierte Indexstrukturen untersucht. Es wird ein auf Abstandhistogramme basiertes Effizienzkriterium angeführt, um gute Pivotmenge auszuwählen und der empirische Beweis dargelegt, dass die dargebotene Methode effektiv ist. Desweiteren wird ein verbesserter k-Nächste-Nachbarn-Algorithmus dargestellt, welcher auf dem best-first Algorithmus von Hjaltason und Hamet basiert. Obwohl der ursprüngliche Algorithmus in der Abstandsberchnung optimal ist, sind seine Raumanforderungen bedeutend. Der verbesserte Algorithmus zielt auf die Absenkung der Raumanforderungen mit Hilfe von Distanzschätzfunktionen ab. Drittens wird eine metrische Indexstruktur für dynamische Kombinationen von Feature-Vektoren dargestellt. Die Indexstruktur ist Pivot-basiert und kann einen Vorteil aus den zuvor entwickelten Pivotwahlmethoden ziehen. Zum Abschluss wird eine Annäherung ausgeführt, welche auf die Minimierung der zu erwartenden Suchzeit einer Ähnlichkeitsuche zielt. Die prinzipielle Idee ist, die am häufigsten benutzteten Kombinationen von Feature-Vektoren zu indizieren. Das sich ergebende Optimierungsproblem kann zu einem Binary-Linear-Program ummodelliert werden, wenn es bei der Speicherung von Indexstrukturen Beschränkungen des Speicherplatzes gibt. Da Binary-Linear-Programs im Allgemeinen NP-hart sind, werden Algorithmen vorgeschlagen, die auf schnelle Weise gute Indexmengen finden.<br /><br />Der Schlußteil der Dissertation beschreibt die Erforschung der Verwendung von Grafikkartenprozessoren (GPU) für die Beschleunigung von Datenbankoperationen. Es werden GPU-Implementierungen für hoch-dimensionale Nächste-Nachbarn-Suche und ein Clusteringalgorithmus vorgestellt. Die experimentelle Evaluierung zeigt, dass die vorgestellte GPU-basierten Algorithmen eine Größenordnung schneller sind als die gleichen aus CPU-basierenden Algorithmen. 2011-03-24T16:09:34Z 2006 deposit-license Indexstrukturen für Ähnlichkeitssuche in Multimedia-Datenbanken Bustos Cárdenas, Benjamin Eugenio 2011-03-24T16:09:34Z

Dateiabrufe seit 01.10.2014 (Informationen über die Zugriffsstatistik)

Dissertation_Benjamin_Bustos.pdf 161

Das Dokument erscheint in:

deposit-license Solange nicht anders angezeigt, wird die Lizenz wie folgt beschrieben: deposit-license

KOPS Suche


Stöbern

Mein Benutzerkonto