Ähnlichkeitssuche beschäftigt sich mit dem Auffinden ähnlicher Objekte zu einem vorgegebenen Anfrageobjekt. Die logische Kombination verschiedener Features des Anfrageobjekts erhöht dabei die Ausdruckskraft von Anfragen und führt zu besseren Anfrageergebnissen. Um eine effiziente Suche zu ermöglichen ist eine Indexierung der Datenbankobjekte nötig. Neben einer möglichst hohen Sucheffizienz spielt die Flexibilität des Indexierungsverfahrens eine entscheidende Rolle. Das in dieser Arbeit vorgestellte Indexierungsverfahren ermöglicht eine effiziente Verarbeitung von Multi-Feature-Anfragen mit beliebigen logischen Kombinationen und Gewichtungen anhand eines einzigen Index. Die Verwendung metrischer Indexierungsmethoden garantiert die Anwendbarkeit des Konzepts für ein großes Spektrum von Features und Distanzfunktionen. similarity search, retrieval, nearest neighbor search, metric indexing, complex query
Indexing — Indexing methods
EINLEITUNG
Ähnlichkeitssuche [
Die Verwendung mehrerer Features und einer geeigneten
Kombination dieser, erhöht die Ausdruckskraft von Anfragen und führt
somit zu besseren Anfrageergebnissen [
Logikbasierte Anfragemodelle, wie die Commuting Quantum
Query Language (CQQL [
Der naive Ansatz zur Umsetzung einer Ähnlichkeitssuche ist der lineare Scan der Datenbank, bei dem alle Distanzen zwischen Anfrageobjekt und Datenbankobjekten ermittelt werden. Für MultiFeature-Anfragen bedeutet dies, dass für jedes einzelne Feature die Distanz zwischen Anfrage- und jedem Datenbankobjekt ermittelt wird. Anschließend werden diese Teildistanzen für jedes Objekt zu einer Gesamtdistanz aggregiert. Da die Evaluierung von Distanzfunktionen mitunter hohe CPU- und das Lesen der zugehörigen Features hohe I/O-Kosten verursachen, ist der lineare Scan für große Datenbanken mit einer Vielzahl von Objekten und Features nicht praktikabel. Stattdessen sollten Indexierungsverfahren genutzt werden, um eine effizientere Suche zu realisieren. Sie ermöglichen einen frühzeitigen Ausschluss von Objekten, die nicht zur Ergebnismenge gehören können, und verringern somit die Anzahl der nötigen Distanzberechnungen und I/O-Operationen.
Eine besondere Anforderung an die logikbasierte Indexierung stellt die Flexibilität dar. Die logische Kombination der Anfrage und auch die Anfragegewichte können sich im Rahmen von Relevance Feedback dynamisch verändern, dennoch sollte nur ein einziger Index zur Verarbeitung beliebiger Anfragen benötigt werden. Weiterhin sollte das Indexierungsverfahren unabhängig von Art und Struktur der verwendeten Features und Distanzfunktionen sein.
Hauptbeitrag dieser Arbeit ist die Entwicklung eines effizienten Indexierungsverfahrens zur Verarbeitung logikbasierter MultiFeature-Anfragen am Beispiel von CQQL. Dazu werden spezifische Anforderungen an die logikbasierte Indexierung definiert und anhand dieser ein Indexierungsverfahren entworfen, das eine effizi
Ausdruck arithmetische Formel :a a ^ b a _ b (c ^ a) _ (:c ^ b) 1 a a b a + b a b a + b ente und gleichzeitig flexible Verarbeitung beliebiger logikbasierter Multi-Feature-Anfragen und eine dynamische Gewichtung dieser ermöglicht.
Die Arbeit ist wie folgt aufgebaut. Abschnitt 2 definiert die grundlegenden Begriffe und die Notationen dieser Arbeit. In Abschnitt 3 wird ein theoretisches Anwendungsbeispiel aus dem Bereich der Bildähnlichkeitssuche mithilfe logikbasierter MultiFeature-Anfragen präsentiert. Auf die speziellen Anforderungen an Indexierungsverfahren für derartige Anfragen wird in Abschnitt 4 detailliert eingegangen. Abschnitt 5 beschäftigt sich mit dem Stand der Technik zur Indexierung. Abschnitt 6 zeigt das Konzept eines Indexierungsverfahrens und Kriterien zur Indexauswahl. Abschließend wird in Abschnitt 7 eine Zusammenfassung der Arbeit gegeben. 2.
Der folgende Abschnitt definiert die grundlegenden Begriffe und die Notationen, die in dieser Arbeit verwendet werden. 2.1
Ähnlichkeitsanfragen anhand von Distanzmaßen werden auch als k-Nächste-Nachbarn-Suche (kNN) bezeichnet und geben die k Objekte aus einer Datenbank zurück, deren Distanz zum Anfrageobjekt am geringsten ist.
Eine Ähnlichkeitsanfrage kNN(q) besteht aus einem Anfrageobjekt q aus dem Universum U und bezieht sich auf eine Datenbank D = fo1; o2; : : : ; ong U von Objekten oi. Die Distanz (Unähnlichkeit) von Objekten wird mithilfe einer Distanzfunktion : U U 7! R 0 anhand der aus den Objekten extrahierten Features q0 und o0i bestimmt. Das Ergebnis der Anfrage kNN(q) ist dann eine (nichtdeterministische) Menge K D, für die gilt: jKj = k und 8oi 2 K; oj 2 D n K : (q; oi) (q; oj ).
Bei einer kNN-Anfrage bestehend aus m Features werden die Features eines Objekts mit q0 = (q1; q2; : : : ; qm) beziehungsweise o0i = (oi1; oi2; : : : ; oim) bezeichnet. Jedem Feature wird eine eigene Distanzfunktion j zugeordnet. Die Teildistanzen dij aller Features werden durch eine Aggregationsfunktion agg : Rm0 7! R 0 zu einer Gesamtdistanz dagg vereinigt. Die k nächsten Nachbarn werden i dann anhand dieser Gesamtdistanz bestimmt. 2.2
Für die Evaluation einer auf CQQL basierenden Anfrage werden
boolesche Ausdrücke nach ihrer DNF-Normalisierung anhand von
festgelegten Transformationsregeln in arithmetische Formeln
umgewandelt [
Im Folgenden werden die in Abschnitt 2.2 beschriebenen arithmetischen Formeln als Aggregationsfunktionen betrachtet, deren Definitions- und Wertebereich auf Ähnlichkeitswerte im Intervall
[
Um eine Nächste-Nachbarn-Suche anhand logikbasierter Anfragen zu realisieren, müssen alle Teildistanzen dij vor ihrer Aggregation in Ähnlichkeitswerte sij umgewandelt werden. Die nächsten Nachbarn sind nach der Aggregation dieser Ähnlichkeitswerte dann genau die Objekte, deren aggregierte Ähnlichkeitswerte siagg bezüglich dem Anfrageobjekt am größten sind. Abbildung 1 verdeutlicht den Suchablauf.
Beispiele für geeignete Funktionen zur Umwandlung von
Distanzen in Ähnlichkeitswerte sind t(x) = e x oder t(x) = 1
x , wobei max der maximale Distanzwert der genutzen
Distanzmax
funktion darstellt [
Das folgende Anwendungsbeispiel illustriert eine logikbasierte Ähnlichkeitsanfrage anhand mehrerer Features.
Gegeben sei eine Datenbank mit Bildern verschiedener Pilze und
Informationen über deren Art und Giftigkeit. Ziel sei es nun anhand
eines Anfragebildes eines gesammelten Pilzes, die Art des Pilzes
zu ermitteln und so zu bestimmen, ob der Pilz essbar ist. Die aus
den Bildern extrahierten Features umfassen dabei aus den
Pixeldaten erzeugte Farb- (color ) und Formfeatures (shape) sowie aus den
Metadaten stammende Informationen, wie das Datum der
Bildaufnahme (date) oder die GPS-Koordinaten des Aufnahmeortes (gps).
Zur Ermittlung der (Un-)Ähnlichkeit von Objekten werden jeweils
für das Feature geeignete Distanzfunktionen genutzt,
beispielsweise die Earth Mover’s Distanzfunktion [
Eine Anfrage, bestehend aus nur einem Feature, genügt nicht, um eine korrekte Zuordnung der Pilzarten vorzunehmen. So kann zum Beispiel allein anhand der Farbfeatures eines Pilzes nicht immer ein Rückschluss auf dessen Art gezogen werden, wenn sich etwa die Form stark von der des Anfragebildes unterscheidet. In diesem Fall ist eine UND-Verknüpfung der Features nötig: shape ^ color . Für den Fall, dass der Pilz des Anfragebildes eine für seine Art sehr untypische Form aufweist (:shape ) und daher anhand dieser nicht zugeordnet werden kann, soll stattdessen allein anhand der GPS-Koordinaten des Bildes (gps ) auf dessen Art geschlossen werden. Als zusätzliche relationale (scharfe) Bedingung sollen nur Pilze betrachtet werden, die im selben Monat gesammelt wurden, wie der Pilz des Anfragebildes (date=). Eine logische Verknüpfung der Features eines Anfragebildes sieht dann wie folgt aus, wobei 1; 2 für Parameter stehen, die eine unterschiedliche Gewichtung der Teilbedingungen ermöglichen. date= ^ ((shape ^ color ) _ 1; 2 (:shape ^ gps )) (2)
Nach einer DNF-Normalisierung und Transformation anhand der in Abschnitt 2.2 beschriebenen Transformationsregeln, ergibt sich aus dem booleschen Ausdruck (2) folgende arithmetische Formel: ( 1 ( 2 date= date= shape
color ) + (1 shape ) gps ) (3)
In [
Flexibilität: Multi-Feature-Anfragen setzen sich aus unterschiedlichen Features und Distanzfunktionen zusammen, das Indexierungsverfahren muss daher unabhängig von Art und Struktur der Features sein und ein breites Spektrum an Distanzfunktionen unterstützen. Die Anzahl der unterschiedlichen zur Verfügung stehenden Features ist potentiell hoch. Das Indexierungsverfahren muss daher mit einer großen Menge von Features umgehen können, auch wenn nur eine Teilmenge dieser für eine Anfrage genutzt wird. Je nach Anfrage können sich die genutzten Features unterscheiden. Ebenso sind unterschiedliche logische Kombinationen und unterschiedliche Gewichtungen der selben Features möglich. Das Indexierungsverfahren darf daher nicht nur auf eine logische Kombination zugeschnitten werden, sondern muss mit beliebigen logischen Kombinationen und Gewichtungen umgehen können.
Sucheffizienz: Die Anzahl der nötigen Berechnungen der
Distanzfunktion und die Anzahl von I/O-Operationen (Seitenzugriffe)
dienen als Effizienzmaß für Indexierungsverfahren. Die Grundlage
für die Bewertung der Sucheffizienz bildet der Vergleich mit dem
Suchaufwand des linearen Scans der Datenbank. Ein effizientes
Indexierungsverfahren sollte diesen linearen Aufwand stets
unterbieten. Es existieren zwar Verfahren, welche eine sehr hohe
Sucheffizienz bieten, dabei aber einen nicht realisierbar hohen
Speicherverbrauch verursachen (vgl. [
Skalierbarkeit: Ein inhärentes Problem der Ähnlichkeitssuche
ist der Fluch der hohen Dimensionen (FdhD [
Der folgende Abschnitt geht auf den Stand der Technik auf dem Gebiet der effizienten Verarbeitung von Multi-Feature-Anfragen ein. Die existierenden Verfahren werden kurz vorgestellt und ausschnittsweise hinsichtlich der in Abschnitt 4 definierten Anforderungen bewertet. Wir beschränken uns dabei auf Verfahren für die exakte Suche der nächsten Nachbarn und gehen nicht auf Spezialfälle wie die approximative Suche oder zusätzliche Anfragearten wie getNext (Ranking-Anfrage) ein. 5.1
Combiner-Algorithmen [
Combiner-Algorithmen sind keine Indexierungsverfahren, sondern arbeiten auf einer darüber liegenden Ebene. Sie legen nicht fest, wie die sortierten Listen bereitgestellt werden. Um eine effiziente Suche zu ermöglichen, sollte der Zugriff über Indexierungsverfahren mit Unterstützung von getNext-Anfragen umgesetzt werden.
Combiner-Algorithmen erlauben eine dynamische Auswahl der
verwendeten Features sowie unterschiedliche
Aggregationsfunktionen und Gewichtungen. Aufgrund der Forderung nach globaler
Monotonie kommen sie jedoch nicht für alle logikbasierten
MultiFeature-Anfragen in Frage. Formel 3 ist beispielsweise nicht
global monoton steigend, da eine Erhöhung des Ähnlichkeitswerts
shape nicht in jedem Fall zu einer Erhöhung des aggregierten
Ähnlichkeitswerts führt. Ein weiterer Nachteil ist die geforderte
Bereitstellung der sortierten Listen, da Indexstrukturen mit
effizienten getNext-Anfragen nicht immer zur Verfügung stehen und sich
durch die getrennte Verwaltung jedes einzelnen Index ein
Mehraufwand ergibt.
3Die Dimensionalität eines Features ergibt sich aus der Anzahl
seiner Featurewerte. Die intrisische Dimensionalität lässt sich
beispielsweise anhand der paarweisen Distanzen zwischen den
Featurewerten der Datenbankobjekte abschätzen und ist dann definiert
als = 2=2 2 [
Räumliche Indexierungsverfahren gehen davon aus, dass die Features in Form von Vektoren vorliegen und die euklidsche Distanzfunktion (L2-Distanzfunktion) zur Berechnung der Unähnlichkeit zwischen den Featurevektoren verwendet wird. Da diese Beschränkung im Widerspruch zur Flexibilität steht, scheidet die Verwendung räumlicher Indexierungsverfahren aus. Dennoch soll im Folgenden auf sie eingegangen werden, da ihre Konzepte teilweise übertragbar sind.
Hierarchische Verfahren, wie zum Beispiel der R-Baum [9],
beschreiben Mengen von Objekten durch geometrische Regionen
(Cluster). Aufgrund des Fluchs der hohen Dimensionen sinkt die
Sucheffizienz dieser Verfahren jedoch bereits ab einer
Dimensionsanzahl der Featurevektoren von 10-20 unter die des linearen
Scans [
VA-Datei
hierarchisches Verfahren und akzeptiert den FdhD in dem Sinne, dass sie statt Cluster zu bilden, direkt einen linearen Scan der Datenbank durchführt. Sie setzt dazu einen Filter-Refinement-Ansatz auf Basis kompakter Bitsignaturen ein. Ziel dieses Ansatzes ist es in der Filterphase, anhand der durch Bitsignaturen approximierten Objekte, Distanzgrenzen zu ermitteln und mithilfe dieser möglichst viele Objekte von der weiteren Suche auszuschließen. Die exakte Distanz muss in der Verfeinerungsphase dann lediglich für die Objekte berechnet werden, die in der Filterphase nicht ausgeschlossen werden konnten.
Die Sucheffizienz des Verfahrens ergibt sich daraus, dass die Bitsignaturen in der Filterphase sequentiell aus Signaturdateien gelesen werden und durch den Ausschluss von Objekten die Anzahl teurer, wahlfreier Zugriffe in der Verfeinerungsphase verringert wird. Für Multi-Feature-Anfragen ist eine Anpassung der VADatei nötig. 5.2.2
GeVAS
GeVAS [
Liegen die einzelnen VA-Dateien auf der gleichen Festplatte
(HDD) ergeben sich für GeVAS Effizienzprobleme beim Lesen der
Daten vom Sekundärspeicher, da statt jede VA-Datei einzeln
sequentiell zu lesen, der Lesekopf der Festplatte zwischen den
verschiedenen VA-Dateien hin und her springen muss [
die Art der Featuredaten. Im Gegensatz zu räumlichen Indexierungsverfahren erlauben sie daher auch die Indexierung von Features bei denen es sich nicht um Vektoren handelt (zum Beispiel textuelle Daten) oder die nicht die euklidsche Distanzfunktion verwenden. Sie erfordern lediglich das Vorliegen einer Metrik.
Eine Metrik ist eine Distanzfunktion, für die folgenden Eigenschaften für alle oi; oj ; ok 2 U gelten: (oi; oj ) > 0 für oi 6= oj (Positivität), (oi; oi) = 0 (Selbstidentität), (oi; oj ) = (oj ; oi) (Symmetrie) und (oi; ok) (oi; oj ) + (oj ; ok) (Dreiecksungleichung).
Der Ausschluss von Objekten wird mithilfe der Dreiecksungleichung erreicht, die es ermöglicht, untere und obere Grenzen bezüglich der Distanz von Anfrageobjekt und Datenbankobjekten zu bestimmen. Die Grenzen können effizient anhand von vorberechneten Distanzen zu einem oder mehreren Referenzobjekten5 ermittelt werden. Die untere und die obere Grenze für die Distanz (q; oi) und ein Referenzobjekt p sind wie folgt definiert: j (q; p) |
{z lb (q;oi) (p; oi)j } (q; oi) | (q; p) + (p; oi)
{z } ub (q;oi) (4)
Analog zu räumlichen Indexierungsverfahren lässt sich zwischen
hierarchischen (M-Baum [
Der Großteil der existierenden metrischen
Indexierungsverfahren ist auf die Indexierung anhand einer einzigen
Distanzfunktion ausgelegt. Die Forderung nach der Unterstützung beliebiger
logischer Kombinationen kann daher nicht erfüllt werden.
MultiMetrische Indexierungsverfahren [
M2-Baum
Der M2-Baum [
Der M2-Baum verlangt die lokale Monotonie der
Aggregationsfunktion. Die arithmetische Formel 3 erfüllt jedoch auch
diese Eigenschaft nicht. Analog zu GeVAS lässt sich die
MonotonieEigenschaft aber auch hier so abschwächen, dass beliebige,
logikbasierte Multi-Feature-Anfragen möglich werden (siehe
Abschnitt 6.1). Der M2-Baum erlaubt somit beliebige, logische
Kombinationen und eine dynamische Auswahl der tatsächlich genutzten
Features. Da es sich beim M2-Baum um ein hierarchisches
Verfahren handelt, nimmt die Sucheffizienz jedoch aufgrund des Fluchs
der hohen Dimensionen mit steigender intrinsischer
Dimensionalität der Features stärker ab, als bei nicht-hierarchischen Verfahren
[
Dieser Abschnitt beschreibt das Konzept eines Indexierungsverfahrens zur effizienten Verarbeitung logikbasierter Multi-FeatureAnfragen. Dazu wird zuerst auf die Berechnung aggregierter Distanzgrenzen eingegangen. Die Übertragung des GeVAS-Ansatzes auf den metrischen Raum stellt den Kern des Konzepts dar. Wir wählen GeVAS aufgrund seiner Flexibilität im Bezug auf Featureanzahl und -auswahl sowie aufgrund seiner besseren Skalierbarkeit im Bezug auf die Dimensionalität als hierarchische Verfahren. Zusätzliche Anpassungen, wie die direkte Berechnung exakter Distanzen für eine Teilmenge der Features, dienen dazu, die Sucheffizienz des entworfenen Verfahrens bei steigender Featureanzahl zu verbessern. 6.1
Die korrekte Berechnung aggregierter Distanzgrenzen6 hängt von
der Monotonie der Aggregationsfunktion ab. Zur Berechnung der
oberen Distanzgrenze einer global monoton steigenden
Aggregationsfunktion müssen die oberen Grenzen aller Teildistanzen in die
Aggregationsfunktion eingesetzt werden [
Für die obere Distanzgrenze lokal monotoner
Aggregationsfunktionen kommt es auf die Monotonie der einzelnen Argumente an.
Bei monoton steigenden Argumenten muss die obere
Distanzgrenze und bei monoton fallenden Argumenten die untere
Distanzgrenze eingesetzt werden [
Die arithmetische Formel (3) ist nicht lokal monoton. Jedoch liegt eine Monotonie vor, für die wir den Begriff fixe Monotonie einführen. Hierbei hängt die Monotonie eines Arguments der Aggregationsfunktion von den Wertebelegungen der anderen Argumente ab. Eine fix monotone Funktion kann also in einem Argument für bestimmte Wertebelegungen monoton fallend und für alle andere Wertebelegungen monoton steigend sein. In Formel (3) ergibt sich die fixe Monotonie daraus, dass das Argument shape in einem Teil der Formel negiert und in einem anderen Teil nichtnegiert auftritt.
Die aggregierte obere Distanzgrenze für fix monotone Funktionen ergibt sich durch das Einsetzen aller möglichen Kombinationen von oberen und unteren Grenzen in die Aggregationsfunktion und einer Auswahl des maximalen Ergebnisses.
C = dl1b ; d1ub daugbg = max agg(c) c2C fdlmb ; dumb g (5) (6) Wie zuvor erwähnt, lässt sich die Berechnung der aggregierten Grenzen in GeVAS und M2-Baum entsprechend anpassen.
Es kann gezeigt werden, dass alle mithilfe von CQQL erzeugten arithmetischen Formeln eine der beschriebenen Monotonien erfüllen. Die Monotonie kann dabei allein anhand der Syntax der Anfrage bestimmt werden. Auf die Darstellung der Beweise dieser Eigenschaften wird an dieser Stelle aus Platzgründen verzichtet. 6.2
Im Gegensatz zu GeVAS werden die Signaturen beim metrischen Filter-Refinement nicht anhand der Featuredaten der Datenbankobjekte ermittelt, sondern ergeben sich aus den Distanzen der Datenbankobjekte zu Referenzobjekten. Jede Signaturdatei besteht daher aus den Bitsignaturen der Distanzen jedes Datenbankobjekts zu einer Menge von Referenzobjekten. Die Reihenfolge der Datenbankobjekte ist dabei in allen Signaturdateien gleich. Die kNN-Suche verläuft analog zu GeVAS, wobei der Ausschluss von Objekten jedoch anhand aggregierter Ähnlichkeitsgrenzen stattfindet. 6Die Beschreibungen lassen sich analog auf Ähnlichkeitsgrenzen anwenden.
Für die Auswahl geeigneter Referenzobjekte stehen
verschiedene Verfahren zur Verfügung, darunter die zufällige Auswahl oder
die inkrementelle Auswahl entfernter Objekte [
Bei der Indexerzeugung werden für einen repräsentativen
Ausschnitt der Datenbank die paarweisen Distanzen je Feature
bestimmt. Ein Equi-Height-Histogramm [
Dem in Abschnitt 5.2.2 erläuterten GeVAS-Problem der sinkenden Sucheffizienz bei der Ablage aller Signaturedateien auf einer Festplatte begegnen wir mit der Einführung eines Lesefensters. Statt für jedes Objekt parallel auf alle genutzten Signaturdateien zuzugreifen, wird jede Signaturdatei einzeln in Größe des Lesefensters ausgelesen. Der Vorteil dabei ist, dass längere sequentielle Lesephasen entstehen und weniger Sprünge zwischen den Signaturdateien stattfinden. Allerdings müssen die gelesenen Daten jeweils solange im Hauptspeicher gehalten werden, bis alle genutzten Signaturdateien in Größe des Lesefensters abgearbeitet wurden. 6.4
Ein Problem des Filter-Refinements ist, dass alle Objekte, die in der Filterphase nicht ausgeschlossen werden können, bis zur Verfeinerungsphase in einer nach unterer Distanzgrenze sortierten Kandidatenliste gehalten werden müssen. Für große Datenbanken kann es jedoch vorkommen, dass der vorhandene Hauptspeicher dazu nicht ausreicht. Ein weiteres Lesefenster ermöglicht daher die Einhaltung von festen Grenzen für die Hauptspeichernutzung.
Nach einem in [
Steigt die Anzahl der in der Anfrage genutzten Features, steigt der Approximationsfehler bei der Abschätzung der aggregierten Ähnlichkeitsgrenzen, da alle Teildistanzen in Form von Distanzgrenzen eingehen. Für Anfragen mit vielen Features bedeutet dies, dass sich die Anzahl der Objekte, die anhand dieser Grenzen ausgeschlossen werden können, verringert und die Sucheffizienz des Verfahrens sinkt.
Um diesem Problem zu begegnen, werden bei steigender Featureanzahl, statt Distanzgrenzen für jedes einzelne Feature zu nutzen, nur noch für eine Teilmenge der verwendeten Features Distanzgrenzen abgeschätzt. Für alle anderen Features werden direkt die exakten Distanzen berechnet. Aus der exakten Berechnung von Teildistanzen ergibt sich ein Mehraufwand gegenüber der Nutzung von Distanzgrenzen. Dieser Mehraufwand kann jedoch ausgeglichen werden, wenn durch diese exakte Berechnung genügend zusätzliche Objekte ausgeschlossen werden können.
Dieses Prinzip lässt sich in der Filterphase anwenden um mehr Objekte auszuschließen. Analog zum sequentiellen Lesen der Signaturdateien müssen die Features in diesem Fall ebenfalls sequentiell gelesen werden, um die Sucheffizienz in der Filterphase zu garantieren.
Das gleiche Prinzip kann in der Verfeinerungsphase genutzt werden, um die Suche früher und mit weniger exakten Distanzberechnungen abbrechen zu können. Statt für ein Objekt in der Verfeinerungsphase direkt alle Teildistanzen auf einmal exakt zu berechnen und zu aggregieren, wird schrittweise vorgegangen. Jedes Mal, wenn ein Objekt in der Verfeinerungsphase am Anfang der Kandidatenliste steht, für das noch nicht alle Teildistanzen berechnet wurden, wird eine Teildistanz berechnet und das Objekt anhand der neuen (genaueren) aggregierten Ähnlichkeitsgrenze wieder in die Kandidatenliste einsortiert. Ein Vorteil ergibt sich dann, wenn der Ausschluss eines Objekts von nur wenigen Teildistanzen abhängt. Bei einer geeigneten Reihenfolge der berechneten Teildistanzen müssen dann nur diese diskriminierenden Distanzen exakt berechnet werden, die Berechnung aller weiteren Teildistanzen kann gespart werden.
Die Auswahl der Features, für die exakte Distanzen berechnet werden, erfolgt statisch (zur Indexierungszeit) oder dynamisch (zur Anfragezeit) nach unterschiedlichen Kriterien, wie der (intrinsischen) Dimensionalität der Features oder der Berechnungsdauer der zugehörigen Distanzfunktion. 6.6
Die Sucheffizienz des beschriebenen Verfahrens hängt besonders von der Anzahl der verwendeten Features und der daraus resultierenden (intrinsischen) Dimensionalität ab. Hierarchische Verfahren können bei niedriger (intrinsischer) Dimensionalität, aufgrund der hohen Lokalität der Daten, größere Mengen von Objekten auf einmal ausschließen und dadurch effizienter als nicht-hierarchische Verfahren sein. Ein Vergleich des entworfenen Konzepts mit dem angepassten M2-Baum dient daher zur Bestimmung der Schnittpunkte bezüglich der Sucheffizienz beider Ansätze. Eine Selektion des effizienteren Index kann dann entweder bereits bei der Indexerzeugung oder erst zur Anfragezeit anhand der in der Anfrage genutzten Features und ihrer (intrinsischen) Dimensionalität stattfinden. Überschreitet die (intrinsische) Dimensionalität eine bestimmte Grenze, ist unter Umständen ein Rückfall auf den linearen Scan sinnvoll.
In dieser Arbeit wurde ein Konzept zur flexiblen Indexierung für Ähnlichkeitssuche mit logikbasierten Multi-Feature-Anfragen vorgestellt. Dazu wurden die spezifischen Anforderungen an geeignete Indexierungsverfahren definiert und der Stand der Technik im Bezug auf diese Anforderungen analysiert. Das entwickelte Konzept zur Indexierung basiert auf einer Übertragung und Anpassung des GeVAS-Ansatzes auf den metrischen Raum. Der Index ist dadurch unabhängig von der genutzten logischen Kombination, der Art und Struktur der verwendeten Features und unterstützt eine Vielzahl unterschiedlicher Features und Distanzfunktionen zur Berechnung der Unähnlichkeit.
Als zukünftige Arbeiten verbleiben Teile der Implementierung, die Bestimmung der optimalen Indexparameter und die Evaluation des Konzeptes anhand von synthetischen und realen Daten. Die Unterstützung von Multi-Objekt-Anfragen sowie von Distanzfunktionen die keine Metriken sind, stellen weitere Herausforderungen dar.
Literatur [9] Antonin Guttman. “R-trees: a dynamic index structure for spatial searching”. In: Proceedings of the 1984 ACM SIGMOD international conference on Management of data. SIGMOD ’84. 1984, S. 47– 57.