Effiziente Algorithmen und Datenstrukturen zur inhaltsbasierten Suche in Audio- und 3D-Moleküldaten

Abstract

Gegenstand der vorgelegten Arbeit ist die inhaltsbasierte Suche in Audio- und Moleküldaten. Ausgangspunkt sind große Kollektionen von solchen multimedialen Dokumenten. Eine Grundaufgabe des inhaltsbasierten Retrievals besteht darin, ein möglicherweise verrauschtes oder deformiertes Fragment eines Dokuments in einer Kollektion zu lokalisieren und damit das Fragment zu identifizieren.<br /> Zur effizienten Lösung dieser und ähnlicher Retrievalaufgaben, wird ein Ansatz basierend auf sog. G-invertierten Listen zusammen mit dem Prinzip der Operation einer Gruppe auf einer Menge verwendet. Um diese Basistechnologie zur inhaltsbasierten Suche auf unterschiedlichste Arten von Dokumenten anwenden zu können, kommt der nicht trivialen Entwicklung sog. Merkmalsextraktoren eine Entscheidende Rolle zu. Um je nach Wahl der Gruppe G redundanzfreie G-invertierte Listen im Suchindex zu erhalten, sollten alle Stabilisatoren trivial sein. Die Trefferberechnung ergibt sich dann theoretisch als Berechnung des Durchschnitts von G-invertierten Listen.<br /> Im ersten Teil der Arbeit werden neue effiziente Suchalgorithmen vorgestellt, die es erlauben Retrievalsysteme zu entwickeln, die mit praxisrelevanten Datenmengen umgehen können. Besonders hervorzuheben ist dabei die Möglichkeit, Suchindexe mit unterschiedlichen Auflösungsstufen zu verwenden, um so die benötigte Zeit für die Bearbeitung einer Suchanfrage zu reduzieren. Es wird eine Übersicht über unterschiedliche Audio-Retrievalsysteme gegeben, die derzeit zum Teil kommerziell eingesetzt werden. Weiterhin werden unterschiedliche Merkmalsextraktoren für CD-Audiodaten vorgestellt, die es z.B. erlauben, einen Suchindex für viele tausend Musikstücke aufzubauen und dabei auch verlustbehaftet kodierte Audiodaten (z.B. MP3) als Anfragen zuzulassen.<br /> Im zweiten Teil der Arbeit spielen Dokumente eine Rolle, die dreidimensionale Ortskoordinaten von Atomen von biologischen Makromolekülen (Proteine, DNA-Sequenzen aus der Protein Data Bank, PDB) beinhalten. Ausgehend von den zuvor vorgestellten Algorithmen wird ein Retrievalsystem zur inhaltsbasierten Suche in dreidimensionalen Moleküldaten entwickelt. Zunächst geht es um die aus Anwendungssicht geeignete Modellierung der Elemente der euklidschen Bewegungsgruppe SE(3). Aufgrund des geringeren Speicheraufwands werden hierbei Quaternionen verwendet. Diese Gruppe stellt an die extrahierten Merkmale besonderen Anforderungen. Um bis auf pathologische Fälle stets triviale Stabilisatoren zu garantieren, werden jeweils drei benachbarte Atome zu einem Merkmal zusammengefasst. Bei der Indexerstellung werden alle möglichen Kombinationen bzgl. eines maximalen euklidschen Abstands zwischen zwei Atomen d betrachtet. Bei einer Anfrage hingegen, ist die minimale Anzahl von Merkmalen zu bestimmen, so dass dennoch alle Atome der Anfrage in mindestens einem Merkmal enthalten sind. Für allgemeine Graphen führt dies auf ein NP-vollständiges Überdeckungsproblem. Im Rahmen dieser Arbeit konnte jedoch gezeigt werden, dass für die speziellen Graphen basierend auf Moleküldaten ein Algorithmus existiert, der in Polynomialzeit eine fast-optimale Überdeckung berechnet. Dieses Ergebnis kann allgemein für die inhaltsbasierte Suche in attributierten 3D-Punktdaten genutzt werden.<br /> Anstelle der Suche auf atomarer Ebene bietet sich im Fall von Proteinen an, die Moleküle der jeweiligen Aminosäuren als Merkmale zu benutzen. Wie sich zeigt, führt dies zu einer deutlichen Reduktion des Indexierungsaufwands. Der höhere Semantikgehalt dieser Merkmale spiegelt sich auch in der Aussagekraft der Treffer wider. Außerdem kann die Sequenz einer angefragten Konstellation von Aminosäuren dazu benutzt werden, der inhaltsbasierten Suche bereits bestehende Sequenzalignmentalgorithmen vorzuschalten. Die Suchalgorithmen sind derart erweitert worden, dass die in den invertierten Listen abgespeicherten Elemente nur dann zur Suche herangezogen werden, wenn die jeweilige Dokumentennummer durch den vorgeschalteten Alignmentalgorithmus berechnet worden ist. Dieses Prinzip lässt sich auch auf die Verwendung anderer Metadaten übertragen.