Flexible Indexierung für Ähnlichkeitssuche mit logikbasierten Multi-Feature-Anfragen Marcel Zierenberg Brandenburgische Technische Universität Cottbus Institut für Informatik, Informations- und Medientechnik Lehrstuhl Datenbank- und Informationssysteme Postfach 10 13 44, 03013 Cottbus, Deutschland zieremar@tu-cottbus.de KURZFASSUNG sich dabei um eine Menge von Werten, die bestimmte Eigenschaf- Ähnlichkeitssuche beschäftigt sich mit dem Auffinden ähnlicher ten eines Objekts charakterisieren. Die Nutzung von Features, wel- Objekte zu einem vorgegebenen Anfrageobjekt. Die logische Kom- che die gewünschte Semantik geeignet beschreiben, ist dabei ent- bination verschiedener Features des Anfrageobjekts erhöht dabei scheidend für eine effektive Ähnlichkeitssuche. die Ausdruckskraft von Anfragen und führt zu besseren Anfra- Die Verwendung mehrerer Features und einer geeigneten Kom- geergebnissen. Um eine effiziente Suche zu ermöglichen ist eine bination dieser, erhöht die Ausdruckskraft von Anfragen und führt Indexierung der Datenbankobjekte nötig. Neben einer möglichst somit zu besseren Anfrageergebnissen [20]. Multi-Feature-Anfra- hohen Sucheffizienz spielt die Flexibilität des Indexierungsverfah- gen nutzen daher eine Vielzahl von Features für die Anfrageformu- rens eine entscheidende Rolle. Das in dieser Arbeit vorgestell- lierung. te Indexierungsverfahren ermöglicht eine effiziente Verarbeitung Logikbasierte Anfragemodelle, wie die Commuting Quantum von Multi-Feature-Anfragen mit beliebigen logischen Kombinatio- Query Language (CQQL [14]) oder die Fuzzy-Logik [18], erlau- nen und Gewichtungen anhand eines einzigen Index. Die Verwen- ben die Kombination mehrerer Features mithilfe boolescher Junk- dung metrischer Indexierungsmethoden garantiert die Anwendbar- toren. Neben der verbesserten Ausdruckskraft von Anfragen wird keit des Konzepts für ein großes Spektrum von Features und Di- hierdurch eine Verbindung von (unscharfen) Ähnlichkeitsbedin- stanzfunktionen. gungen und (scharfen) relationalen Datenbankbedingungen ermög- licht [13]. Eine Gewichtung der einzelnen Anfrageatome erlaubt weiterhin eine dynamische Anpassung der Anfragen. Das Lernen Kategorien und Themenbeschreibung dieser Gewichte anhand von Nutzerpräferenzen [19] ermöglicht ei- H.3.1 [Information Storage and Retrieval]: Content Analysis and ne schrittweise Verfeinerung von Anfragen in Form von Relevance Indexing — Indexing methods Feedback. Der naive Ansatz zur Umsetzung einer Ähnlichkeitssuche ist der lineare Scan der Datenbank, bei dem alle Distanzen zwischen An- Allgemeine Begriffe frageobjekt und Datenbankobjekten ermittelt werden. Für Multi- Algorithms, Performance Feature-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 Schlüsselwörter zu einer Gesamtdistanz aggregiert. Da die Evaluierung von Di- similarity search, retrieval, nearest neighbor search, metric inde- stanzfunktionen mitunter hohe CPU- und das Lesen der zugehö- xing, complex query rigen Features hohe I/O-Kosten verursachen, ist der lineare Scan für große Datenbanken mit einer Vielzahl von Objekten und Fea- tures nicht praktikabel. Stattdessen sollten Indexierungsverfahren 1. EINLEITUNG genutzt werden, um eine effizientere Suche zu realisieren. Sie er- Ähnlichkeitssuche [13] verfolgt das Ziel, in einer Menge von Ob- möglichen einen frühzeitigen Ausschluss von Objekten, die nicht jekten genau die Objekte zu finden, die einem Anfrageobjekt am zur Ergebnismenge gehören können, und verringern somit die An- ähnlichsten sind. Die (Un-)Ähnlichkeit der Objekte wird mithilfe zahl der nötigen Distanzberechnungen und I/O-Operationen. von Distanz- oder Ähnlichkeitsmaßen1 anhand der aus den Objek- Eine besondere Anforderung an die logikbasierte Indexierung ten extrahierten Features bestimmt. Bei einem Feature handelt es stellt die Flexibilität dar. Die logische Kombination der Anfrage 1 und auch die Anfragegewichte können sich im Rahmen von Re- Im Folgenden gehen wir von Distanzmaßen aus. levance Feedback dynamisch verändern, dennoch sollte nur ein einziger Index zur Verarbeitung beliebiger Anfragen benötigt wer- den. Weiterhin sollte das Indexierungsverfahren unabhängig von Art und Struktur der verwendeten Features und Distanzfunktionen sein. Hauptbeitrag dieser Arbeit ist die Entwicklung eines effizien- ten Indexierungsverfahrens zur Verarbeitung logikbasierter Multi- Feature-Anfragen am Beispiel von CQQL. Dazu werden spezifi- 24th GI-Workshop on Foundations of Databases (Grundlagen von Daten- sche Anforderungen an die logikbasierte Indexierung definiert und banken), 29.05.2012 - 01.06.2012, Lübbenau, Germany. anhand dieser ein Indexierungsverfahren entworfen, das eine effizi- Copyright is held by the author/owner(s). Tabelle 1: Umwandlung boolescher Ausdrücke in arithmetische Tabelle 2: Einbettung von Gewichten in die Logik Formeln in CQQL Ausdruck Einbettung Ausdruck arithmetische Formel a ∧θ1 ,θ2 b (a ∨ ¬θ1 ) ∧ (b ∨ ¬θ2 ) ¬a 1−a a ∨θ1 ,θ2 b (a ∧ θ1 ) ∨ (b ∧ θ2 ) a∧b a∗b a∨b a+b−a∗b aggregierter (c ∧ a) ∨ (¬c ∧ b) a+b Ähnlichkeitswert sagg i agg(s1i , s2i , . . . , sm i ) ente und gleichzeitig flexible Verarbeitung beliebiger logikbasierter Multi-Feature-Anfragen und eine dynamische Gewichtung dieser ... Ähnlichkeitswerte s1i s2i sm i ermöglicht. Die Arbeit ist wie folgt aufgebaut. Abschnitt 2 definiert die t(dji ) grundlegenden Begriffe und die Notationen dieser Arbeit. In Ab- schnitt 3 wird ein theoretisches Anwendungsbeispiel aus dem ... dm Distanzen d1i d2i i Bereich der Bildähnlichkeitssuche mithilfe logikbasierter Multi- Feature-Anfragen präsentiert. Auf die speziellen Anforderungen an δ j (q j , oji ) Indexierungsverfahren für derartige Anfragen wird in Abschnitt 4 detailliert eingegangen. Abschnitt 5 beschäftigt sich mit dem Stand ... qm om Features q1 o1i q2 o2i i 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 gege- Featureextraktion dynamisch ben. statisch Objekte q oi 2. GRUNDLAGEN Der folgende Abschnitt definiert die grundlegenden Begriffe und Abbildung 1: Ablauf einer logikbasierten Multi-Feature- die Notationen, die in dieser Arbeit verwendet werden. Anfrage 2.1 Nächste-Nachbarn-Suche Ähnlichkeitsanfragen anhand von Distanzmaßen werden auch als [0,1] beschränkt ist: agg : [0, 1]m 7→ [0, 1]. Hierbei steht ein Ähn- k-Nächste-Nachbarn-Suche (kNN) bezeichnet und geben die k Ob- lichkeitswert von 1 für die maximale Ähnlichkeit (Identität), wäh- jekte aus einer Datenbank zurück, deren Distanz zum Anfrageob- rend ein Wert von 0 die größtmögliche Unähnlichkeit darstellt. jekt am geringsten ist. Um eine Nächste-Nachbarn-Suche anhand logikbasierter Anfra- Eine Ähnlichkeitsanfrage kNN(q) besteht aus einem Anfrage- gen zu realisieren, müssen alle Teildistanzen dji vor ihrer Aggre- objekt q aus dem Universum U und bezieht sich auf eine Daten- gation in Ähnlichkeitswerte sji umgewandelt werden. Die nächs- bank D = {o1 , o2 , . . . , on } ⊆ U von Objekten oi . Die Distanz ten Nachbarn sind nach der Aggregation dieser Ähnlichkeitswerte (Unähnlichkeit) von Objekten wird mithilfe einer Distanzfunktion dann genau die Objekte, deren aggregierte Ähnlichkeitswerte sagg i δ : U × U 7→ R≥0 anhand der aus den Objekten extrahierten Featu- bezüglich dem Anfrageobjekt am größten sind. Abbildung 1 ver- res q 0 und o0i bestimmt. Das Ergebnis der Anfrage kNN(q) ist dann deutlicht den Suchablauf. eine (nichtdeterministische) Menge K ⊆ D, für die gilt: |K| = k Beispiele für geeignete Funktionen zur Umwandlung von Di- und ∀oi ∈ K, oj ∈ D \ K : δ(q, oi ) ≤ δ(q, oj ). stanzen in Ähnlichkeitswerte sind t(x) = e−x oder t(x) = 1 − x Bei einer kNN-Anfrage bestehend aus m Features werden die δmax , wobei δmax der maximale Distanzwert der genutzen Distanz- Features eines Objekts mit q 0 = (q 1 , q 2 , . . . , q m ) beziehungsweise funktion darstellt [13]. o0i = (o1i , o2i , . . . , om i ) bezeichnet. Jedem Feature wird eine eigene Distanzfunktion δ j zugeordnet. Die Teildistanzen dji aller Features 2.4 Monotonie werden durch eine Aggregationsfunktion agg : Rm ≥0 7→ R≥0 zu ei- Eine Aggregationsfunktion ist monoton steigend im i-ten Argu- ner Gesamtdistanz dagg i vereinigt. Die k nächsten Nachbarn werden ment2 , wenn gilt: dann anhand dieser Gesamtdistanz bestimmt. xi ≤ y i =⇒ (1) 2.2 CQQL 1 i m 1 agg(x , . . . , x , . . . , x ) ≤ agg(x , . . . , y , . . . , x ) i m Für die Evaluation einer auf CQQL basierenden Anfrage werden boolesche Ausdrücke nach ihrer DNF-Normalisierung anhand von Das bedeutet, dass wenn alle Parameter außer xi festgelegt sind festgelegten Transformationsregeln in arithmetische Formeln um- und xi vergrößert wird, kann das Ergebnis der Aggregationfunktion gewandelt [14]. Tabelle 1 zeigt die in CQQL verwendeten Trans- nicht kleiner werden. Eine Aggregationsfunktion ist global mono- formationsregeln. Ebenso ist eine Umsetzung der Gewichtung in ton steigend, wenn sie in allen m Argumenten monoton steigend CQQL direkt innerhalb der booleschen Logik möglich. Dazu wer- ist. Ein Beispiel ist agg(x1 , x2 ) = x1 + x2 . den Gewichte anhand der in Tabelle 2 gezeigten Transformations- Eine Aggregationsfunktion ist lokal monoton, wenn sie in einem regeln in die Logik eingebettet. Teil ihrer m Argumente monoton steigend und in allen anderen Argumenten monoton fallend ist. Ein Beispiel ist agg(x1 , x2 ) = 2.3 Logikbasierte kNN x1 − x2 . Im Folgenden werden die in Abschnitt 2.2 beschriebenen arith- metischen Formeln als Aggregationsfunktionen betrachtet, deren 2 Monoton fallend im i-ten Argument ist analog anhand des ≥- Definitions- und Wertebereich auf Ähnlichkeitswerte im Intervall Operators definiert. 3. ANWENDUNGSBEISPIEL für die Bewertung der Sucheffizienz bildet der Vergleich mit dem Das folgende Anwendungsbeispiel illustriert eine logikbasierte Suchaufwand des linearen Scans der Datenbank. Ein effizientes In- Ähnlichkeitsanfrage anhand mehrerer Features. dexierungsverfahren sollte diesen linearen Aufwand stets unterbie- Gegeben sei eine Datenbank mit Bildern verschiedener Pilze und ten. Es existieren zwar Verfahren, welche eine sehr hohe Suchef- Informationen über deren Art und Giftigkeit. Ziel sei es nun anhand fizienz bieten, dabei aber einen nicht realisierbar hohen Speicher- eines Anfragebildes eines gesammelten Pilzes, die Art des Pilzes verbrauch verursachen (vgl. [16]). Ein geeignetes Indexierungsver- zu ermitteln und so zu bestimmen, ob der Pilz essbar ist. Die aus fahren sollte daher einen möglichst geringen Speicherverbrauch bei den Bildern extrahierten Features umfassen dabei aus den Pixelda- gleichzeitig möglichst hoher Sucheffizienz aufweisen. ten erzeugte Farb- (color ) und Formfeatures (shape) sowie aus den Skalierbarkeit: Ein inhärentes Problem der Ähnlichkeitssuche Metadaten stammende Informationen, wie das Datum der Bildauf- ist der Fluch der hohen Dimensionen (FdhD [13, 5]). Dieser be- nahme (date) oder die GPS-Koordinaten des Aufnahmeortes (gps). wirkt, dass die Performanz von Indexierungsverfahren mit steigen- Zur Ermittlung der (Un-)Ähnlichkeit von Objekten werden jeweils der (intrinsischer) Dimensionalität3 eines Features abnimmt. In- für das Feature geeignete Distanzfunktionen genutzt, beispielswei- dexierungsverfahren können den Suchaufwand des linearen Scans se die Earth Mover’s Distanzfunktion [11] für Farbsignaturen oder dann nicht mehr signifikant unterbieten oder übersteigen ihn so- verschiedene Minkowski-Distanzfunktion (Lp -Distanzfunktion). gar. Analog zur Erhöhung der Dimensionsanzahl bei einem Feature Eine Anfrage, bestehend aus nur einem Feature, genügt nicht, lässt sich der FdhD auch bei Multi-Feature-Anfragen beobachten. um eine korrekte Zuordnung der Pilzarten vorzunehmen. So kann Die Kombination von Features bewirkt hier ebenfalls eine Erhö- zum Beispiel allein anhand der Farbfeatures eines Pilzes nicht hung der (intrinsischen) Dimensionalität. Ein geeignetes Indexie- immer ein Rückschluss auf dessen Art gezogen werden, wenn rungsverfahren für Multi-Feature-Anfragen muss daher Möglich- sich etwa die Form stark von der des Anfragebildes unterschei- keiten bieten, mit dem FdhD umzugehen und möglichst ohne Ef- det. In diesem Fall ist eine UND-Verknüpfung der Features nötig: fizienzeinbußen skalierbar bezüglich der (intrinsischen) Dimensio- shape ≈ ∧ color ≈ . Für den Fall, dass der Pilz des Anfragebildes nalität einzelner Features und der Kombination mehrerer Features eine für seine Art sehr untypische Form aufweist (¬shape ≈ ) und sein. daher anhand dieser nicht zugeordnet werden kann, soll stattdessen allein anhand der GPS-Koordinaten des Bildes (gps ≈ ) auf dessen 5. STAND DER TECHNIK Art geschlossen werden. Als zusätzliche relationale (scharfe) Be- Der folgende Abschnitt geht auf den Stand der Technik auf dem dingung sollen nur Pilze betrachtet werden, die im selben Monat Gebiet der effizienten Verarbeitung von Multi-Feature-Anfragen gesammelt wurden, wie der Pilz des Anfragebildes (date = ). Eine ein. Die existierenden Verfahren werden kurz vorgestellt und aus- logische Verknüpfung der Features eines Anfragebildes sieht dann schnittsweise hinsichtlich der in Abschnitt 4 definierten Anforde- wie folgt aus, wobei θ1 , θ2 für Parameter stehen, die eine unter- rungen bewertet. Wir beschränken uns dabei auf Verfahren für die schiedliche Gewichtung der Teilbedingungen ermöglichen. exakte Suche der nächsten Nachbarn und gehen nicht auf Spezi- date = ∧ ((shape ≈ ∧ color ≈ ) ∨θ1 ,θ2 (¬shape ≈ ∧ gps ≈ )) (2) alfälle wie die approximative Suche oder zusätzliche Anfragearten wie getNext (Ranking-Anfrage) ein. Nach einer DNF-Normalisierung und Transformation anhand der in Abschnitt 2.2 beschriebenen Transformationsregeln, ergibt 5.1 Combiner-Algorithmen sich aus dem booleschen Ausdruck (2) folgende arithmetische For- Combiner-Algorithmen [8] kombinieren die Ergebnisse mehrerer mel: Ähnlichkeitsanfragen zu einem aggregierten Ergebnis. Für Multi- Feature-Anfragen existiert dazu je Feature eine nach Distanz4 zum (θ1 ∗ date = ∗ shape ≈ ∗ color ≈ ) + (3) Anfrageobjekt sortierte Liste der Datenbankobjekte. (θ2 ∗ date = ∗ (1 − shape ≈ ) ∗ gps ≈ ) Combiner-Algorithmen sind keine Indexierungsverfahren, son- dern arbeiten auf einer darüber liegenden Ebene. Sie legen nicht 4. ANFORDERUNGEN fest, wie die sortierten Listen bereitgestellt werden. Um eine effi- In [13] werden allgemeine Anforderungen an Indexierungsverfah- ziente Suche zu ermöglichen, sollte der Zugriff über Indexierungs- ren im Bereich des Multimedia Retrievals definiert. Auf Grundlage verfahren mit Unterstützung von getNext-Anfragen umgesetzt wer- dieser werden im Folgenden die spezifischen Anforderungen für In- den. dexierungsverfahren zur effizienten Verarbeitung von logikbasier- Combiner-Algorithmen erlauben eine dynamische Auswahl der ten Multi-Feature-Anfragen vorgestellt. verwendeten Features sowie unterschiedliche Aggregationsfunk- Flexibilität: Multi-Feature-Anfragen setzen sich aus unter- tionen und Gewichtungen. Aufgrund der Forderung nach globaler schiedlichen Features und Distanzfunktionen zusammen, das Inde- Monotonie kommen sie jedoch nicht für alle logikbasierten Multi- xierungsverfahren muss daher unabhängig von Art und Struktur der Feature-Anfragen in Frage. Formel 3 ist beispielsweise nicht glo- Features sein und ein breites Spektrum an Distanzfunktionen unter- bal monoton steigend, da eine Erhöhung des Ähnlichkeitswerts stützen. Die Anzahl der unterschiedlichen zur Verfügung stehenden shape ≈ nicht in jedem Fall zu einer Erhöhung des aggregierten Features ist potentiell hoch. Das Indexierungsverfahren muss da- Ähnlichkeitswerts führt. Ein weiterer Nachteil ist die geforderte her mit einer großen Menge von Features umgehen können, auch Bereitstellung der sortierten Listen, da Indexstrukturen mit effizien- wenn nur eine Teilmenge dieser für eine Anfrage genutzt wird. Je ten getNext-Anfragen nicht immer zur Verfügung stehen und sich nach Anfrage können sich die genutzten Features unterscheiden. durch die getrennte Verwaltung jedes einzelnen Index ein Mehrauf- Ebenso sind unterschiedliche logische Kombinationen und unter- wand ergibt. schiedliche Gewichtungen der selben Features möglich. Das Inde- 3 Die Dimensionalität eines Features ergibt sich aus der Anzahl xierungsverfahren darf daher nicht nur auf eine logische Kombina- seiner Featurewerte. Die intrisische Dimensionalität lässt sich bei- tion zugeschnitten werden, sondern muss mit beliebigen logischen spielsweise anhand der paarweisen Distanzen zwischen den Fea- Kombinationen und Gewichtungen umgehen können. turewerten der Datenbankobjekte abschätzen und ist dann definiert Sucheffizienz: Die Anzahl der nötigen Berechnungen der Di- als ρ = µ2 /2 ∗ σ 2 [1]. 4 stanzfunktion und die Anzahl von I/O-Operationen (Seitenzugriffe) Combiner-Algorithmen sind ohne größere Anpassungen auch für dienen als Effizienzmaß für Indexierungsverfahren. Die Grundlage Ähnlichkeitswerte nutzbar. 5.2 Räumliche Indexierung textuelle Daten) oder die nicht die euklidsche Distanzfunktion ver- Räumliche Indexierungsverfahren gehen davon aus, dass die Fea- wenden. Sie erfordern lediglich das Vorliegen einer Metrik. tures in Form von Vektoren vorliegen und die euklidsche Distanz- Eine Metrik δ ist eine Distanzfunktion, für die folgenden Eigen- funktion (L2 -Distanzfunktion) zur Berechnung der Unähnlichkeit schaften für alle oi , oj , ok ∈ U gelten: δ(oi , oj ) > 0 für oi 6= oj zwischen den Featurevektoren verwendet wird. Da diese Beschrän- (Positivität), δ(oi , oi ) = 0 (Selbstidentität), δ(oi , oj ) = δ(oj , oi ) kung im Widerspruch zur Flexibilität steht, scheidet die Verwen- (Symmetrie) und δ(oi , ok ) ≤ δ(oi , oj ) + δ(oj , ok ) (Dreiecksun- dung räumlicher Indexierungsverfahren aus. Dennoch soll im Fol- gleichung). genden auf sie eingegangen werden, da ihre Konzepte teilweise Der Ausschluss von Objekten wird mithilfe der Dreiecksunglei- übertragbar sind. chung erreicht, die es ermöglicht, untere und obere Grenzen be- Hierarchische Verfahren, wie zum Beispiel der R-Baum [9], be- züglich der Distanz von Anfrageobjekt und Datenbankobjekten zu schreiben Mengen von Objekten durch geometrische Regionen bestimmen. Die Grenzen können effizient anhand von vorberechne- (Cluster). Aufgrund des Fluchs der hohen Dimensionen sinkt die ten Distanzen zu einem oder mehreren Referenzobjekten5 ermittelt Sucheffizienz dieser Verfahren jedoch bereits ab einer Dimensi- werden. Die untere und die obere Grenze für die Distanz δ(q, oi ) onsanzahl der Featurevektoren von 10-20 unter die des linearen und ein Referenzobjekt p sind wie folgt definiert: Scans [13]. Im Folgenden stellen wir daher lediglich den nicht- |δ(q, p) − δ(p, oi )| ≤ δ(q, oi ) ≤ δ(q, p) + δ(p, oi ) (4) hierarchischen Ansatz der VA-Datei vor. | {z } | {z } δlb (q,oi ) δub (q,oi ) 5.2.1 VA-Datei Analog zu räumlichen Indexierungsverfahren lässt sich zwischen Die Vektor-Approximations-Datei (VA-Datei) [17] ist ein nicht- hierarchischen (M-Baum [7]) und nicht-hierarchischen (AESA [16]) hierarchisches Verfahren und akzeptiert den FdhD in dem Sinne, metrischen Indexierungsverfahren unterscheiden. Eine umfassen- dass sie statt Cluster zu bilden, direkt einen linearen Scan der Da- de Übersicht metrischer Indexierungsverfahren bietet zum Beispiel tenbank durchführt. Sie setzt dazu einen Filter-Refinement-Ansatz das Lehrbuch von Samet [12]. auf Basis kompakter Bitsignaturen ein. Ziel dieses Ansatzes ist es Der Großteil der existierenden metrischen Indexierungsverfah- in der Filterphase, anhand der durch Bitsignaturen approximierten ren ist auf die Indexierung anhand einer einzigen Distanzfunk- Objekte, Distanzgrenzen zu ermitteln und mithilfe dieser möglichst tion ausgelegt. Die Forderung nach der Unterstützung beliebiger viele Objekte von der weiteren Suche auszuschließen. Die exakte logischer Kombinationen kann daher nicht erfüllt werden. Multi- Distanz muss in der Verfeinerungsphase dann lediglich für die Ob- Metrische Indexierungsverfahren [4] ermöglichen die Indexierung jekte berechnet werden, die in der Filterphase nicht ausgeschlossen auf Grundlage einer dynamischen Kombination mehrerer Distanz- werden konnten. funktionen zu einer Aggregationsfunktion. Sie unterstützen da- Die Sucheffizienz des Verfahrens ergibt sich daraus, dass die Bit- durch mit einem einzigen Index unterschiedliche Gewichtungen signaturen in der Filterphase sequentiell aus Signaturdateien ge- der gleichen Aggregationsfunktion. Da es sich bei der Aggregati- lesen werden und durch den Ausschluss von Objekten die An- onsfunktion jedoch um eine Metrik handeln muss, ist diese auf die zahl teurer, wahlfreier Zugriffe in der Verfeinerungsphase verrin- gewichtete Summe metrischer Distanzfunktion beschränkt. Für lo- gert wird. Für Multi-Feature-Anfragen ist eine Anpassung der VA- gikbasierte Multi-Feature-Anfragen sind diese Verfahren daher nur Datei nötig. eingeschränkt anwendbar. 5.2.2 GeVAS 5.3.1 M2 -Baum GeVAS [2] ist eine Erweiterung der VA-Datei für Multi-Feature- Der M2 -Baum [6] ist eine Erweiterung des M-Baums für Multi- Anfragen und erlaubt eine dynamische Auswahl der in der An- Feature-Anfragen. Statt die Distanzen bezüglich aller Features be- frage verwendeten Features aus einer großen Menge vorhandener reits bei der Indexierung zu aggregierten Distanzen zusammen- Features. Für jedes Feature wird dazu eine separate VA-Datei er- zufassen, werden die Distanzgrenzen bei der Anfrage dynamisch zeugt, wobei die Reihenfolge der Objekte in allen Signaturdateien für jedes einzelne Feature abgeschätzt. Diese Grenzen werden an- gleich ist. Bei einer Multi-Feature-Anfrage werden nun nur die Si- schließend in Ähnlichkeitswerte umgewandelt und zu aggregierten gnaturdateien der Features parallel abgearbeitet, die tatsächlich in Ähnlichkeitsgrenzen kombiniert (vergleiche aggregierte Distanz- der Anfrage eingesetzt werden. Für jedes einzelne Feature eines grenzen bei GeVAS). Der Vorteil bei diesem Vorgehen ist, dass die Objekts werden Distanzgrenzen ermittelt und dynamisch zu ag- metrischen Eigenschaften in diesem Fall nicht für die Aggregati- gregierten Distanzgrenzen zusammengefasst. Der Ausschluss von onsfunktion gelten müssen, sondern nur für jede zugrundeliegende Objekten geschieht in der Filterphase anhand dieser aggregierten Distanzfunktionen. Distanzgrenzen. Voraussetzung für die korrekte Aggregation von Der M2 -Baum verlangt die lokale Monotonie der Aggregati- Distanzgrenzen ist, dass die Aggregationsfunktion global mono- onsfunktion. Die arithmetische Formel 3 erfüllt jedoch auch die- ton steigend ist. Diese Forderung lässt sich jedoch so abschwä- se Eigenschaft nicht. Analog zu GeVAS lässt sich die Monotonie- chen, dass beliebige, logikbasierte Multi-Feature-Anfragen ermög- Eigenschaft aber auch hier so abschwächen, dass beliebige, lo- licht werden (siehe Abschnitt 6.1). gikbasierte Multi-Feature-Anfragen möglich werden (siehe Ab- Liegen die einzelnen VA-Dateien auf der gleichen Festplatte schnitt 6.1). Der M2 -Baum erlaubt somit beliebige, logische Kom- (HDD) ergeben sich für GeVAS Effizienzprobleme beim Lesen der binationen und eine dynamische Auswahl der tatsächlich genutzten Daten vom Sekundärspeicher, da statt jede VA-Datei einzeln se- Features. Da es sich beim M2 -Baum um ein hierarchisches Verfah- quentiell zu lesen, der Lesekopf der Festplatte zwischen den ver- ren handelt, nimmt die Sucheffizienz jedoch aufgrund des Fluchs schiedenen VA-Dateien hin und her springen muss [13]. der hohen Dimensionen mit steigender intrinsischer Dimensionali- tät der Features stärker ab, als bei nicht-hierarchischen Verfahren 5.3 Metrische Indexierung [13]. Metrische Indexierungsverfahren stellen keine Anforderungen an die Art der Featuredaten. Im Gegensatz zu räumlichen Indexie- 5 Für Referenzobjekte existieren unterschiedliche Benennungen in rungsverfahren erlauben sie daher auch die Indexierung von Fea- der Literatur, wie zum Beispiel Routing-, Focus-, Vantage- oder tures bei denen es sich nicht um Vektoren handelt (zum Beispiel Pivot-Objekt, die das gleiche Konzept widerspiegeln. 6. KONZEPT Für die Auswahl geeigneter Referenzobjekte stehen verschiede- Dieser Abschnitt beschreibt das Konzept eines Indexierungsver- ne Verfahren zur Verfügung, darunter die zufällige Auswahl oder fahrens zur effizienten Verarbeitung logikbasierter Multi-Feature- die inkrementelle Auswahl entfernter Objekte [3]. Um möglichst Anfragen. Dazu wird zuerst auf die Berechnung aggregierter Di- enge Grenzen zu garantieren, nutzt jedes Datenbankobjekt eine dy- stanzgrenzen eingegangen. Die Übertragung des GeVAS-Ansatzes namisch ausgewählte Teilmenge seiner nächsten Referenzobjekte. auf den metrischen Raum stellt den Kern des Konzepts dar. Wir Bei der Indexerzeugung werden für einen repräsentativen Aus- wählen GeVAS aufgrund seiner Flexibilität im Bezug auf Featu- schnitt der Datenbank die paarweisen Distanzen je Feature be- reanzahl und -auswahl sowie aufgrund seiner besseren Skalierbar- stimmt. Ein Equi-Height-Histogramm [10] dieser Distanzen wird keit im Bezug auf die Dimensionalität als hierarchische Verfahren. genutzt um Distanzintervalle für jedes Feature zu berechnen. Die- Zusätzliche Anpassungen, wie die direkte Berechnung exakter Di- se Distanzintervalle dienen dann der Quantisierung der Distanzen stanzen für eine Teilmenge der Features, dienen dazu, die Sucheffi- zwischen Referenzobjekten und Datenbankobjekten. Statt also zur zienz des entworfenen Verfahrens bei steigender Featureanzahl zu Indexierung exakte Distanzen zu speichern, werden die exakten verbessern. Distanzen durch nummerierte Distanzintervalle repräsentiert (vgl. [4]). Die kompakte Darstellung dieser Nummern durch Bitsigna- 6.1 Aggregierte Distanzgrenzen turen verringert den Speicherverbrauch und erhöht gleichzeitig die Sucheffizienz in der Filterphase, da weniger Daten von der Fest- Die korrekte Berechnung aggregierter Distanzgrenzen6 hängt von platte gelesen werden müssen. Der Approximationsfehler der Di- der Monotonie der Aggregationsfunktion ab. Zur Berechnung der stanzgrenzen steigt jedoch durch die Verwendung von Distanzinter- oberen Distanzgrenze einer global monoton steigenden Aggregati- vallen. Die Festlegung der Anzahl an Bits pro Signatur entspricht onsfunktion müssen die oberen Grenzen aller Teildistanzen in die daher der Steuerung der Genauigkeit der Distanzintervalle. Aggregationsfunktion eingesetzt werden [2]. Für die obere Distanzgrenze lokal monotoner Aggregationsfunk- tionen kommt es auf die Monotonie der einzelnen Argumente an. 6.3 Lesefenster Bei monoton steigenden Argumenten muss die obere Distanzgren- Dem in Abschnitt 5.2.2 erläuterten GeVAS-Problem der sinkenden ze und bei monoton fallenden Argumenten die untere Distanzgren- Sucheffizienz bei der Ablage aller Signaturedateien auf einer Fest- ze eingesetzt werden [6]. platte begegnen wir mit der Einführung eines Lesefensters. Statt für Die arithmetische Formel (3) ist nicht lokal monoton. Jedoch jedes Objekt parallel auf alle genutzten Signaturdateien zuzugrei- liegt eine Monotonie vor, für die wir den Begriff fixe Monotonie fen, wird jede Signaturdatei einzeln in Größe des Lesefensters aus- einführen. Hierbei hängt die Monotonie eines Arguments der Ag- gelesen. Der Vorteil dabei ist, dass längere sequentielle Lesephasen gregationsfunktion von den Wertebelegungen der anderen Argu- entstehen und weniger Sprünge zwischen den Signaturdateien statt- mente ab. Eine fix monotone Funktion kann also in einem Argu- finden. Allerdings müssen die gelesenen Daten jeweils solange im ment für bestimmte Wertebelegungen monoton fallend und für alle Hauptspeicher gehalten werden, bis alle genutzten Signaturdateien andere Wertebelegungen monoton steigend sein. In Formel (3) er- in Größe des Lesefensters abgearbeitet wurden. gibt sich die fixe Monotonie daraus, dass das Argument shape≈ in einem Teil der Formel negiert und in einem anderen Teil nicht- 6.4 Begrenzter Hauptspeicher negiert auftritt. Ein Problem des Filter-Refinements ist, dass alle Objekte, die in der Die aggregierte obere Distanzgrenze für fix monotone Funktio- Filterphase nicht ausgeschlossen werden können, bis zur Verfeine- nen ergibt sich durch das Einsetzen aller möglichen Kombinationen rungsphase in einer nach unterer Distanzgrenze sortierten Kandida- von oberen und unteren Grenzen in die Aggregationsfunktion und tenliste gehalten werden müssen. Für große Datenbanken kann es einer Auswahl des maximalen Ergebnisses. jedoch vorkommen, dass der vorhandene Hauptspeicher dazu nicht ausreicht. Ein weiteres Lesefenster ermöglicht daher die Einhal- C = d1lb , d1ub × · · · × {dm m  lb , dub } (5) tung von festen Grenzen für die Hauptspeichernutzung. dagg ub = max agg(c) (6) Nach einem in [15] vorgeschlagenen Prinzip werden Filter- und c∈C Verfeinerungsphase verschränkt. Die Filterphase wird gestoppt, so- Wie zuvor erwähnt, lässt sich die Berechnung der aggregierten bald eine festgelegte Speichergrenze erreicht ist. In der nun folgen- Grenzen in GeVAS und M2 -Baum entsprechend anpassen. den Verfeinerungsphase wird die Kandidatenliste abgearbeitet, bis Es kann gezeigt werden, dass alle mithilfe von CQQL erzeugten k vorläufige nächste Nachbarn ermittelt wurden. Damit diese k Ob- arithmetischen Formeln eine der beschriebenen Monotonien erfül- jekte nicht verloren gehen, werden sie abschließend in die zuvor len. Die Monotonie kann dabei allein anhand der Syntax der An- geleerte Kandidatenliste eingefügt, bevor die Filterphase wieder an frage bestimmt werden. Auf die Darstellung der Beweise dieser Ei- der abgebrochenen Stelle fortgesetzt wird. Der Effizienznachteil genschaften wird an dieser Stelle aus Platzgründen verzichtet. dieses Vorgehens ist, dass das sequentielle Lesen der Filterphase regelmäßig unterbrochen wird und durch einen wahlfreien Zugriff 6.2 Metrisches Filter-Refinement wieder fortgesetzt werden muss. Im Gegensatz zu GeVAS werden die Signaturen beim metrischen Filter-Refinement nicht anhand der Featuredaten der Datenbankob- 6.5 Steigende Featureanzahl jekte ermittelt, sondern ergeben sich aus den Distanzen der Daten- Steigt die Anzahl der in der Anfrage genutzten Features, steigt der bankobjekte zu Referenzobjekten. Jede Signaturdatei besteht daher Approximationsfehler bei der Abschätzung der aggregierten Ähn- aus den Bitsignaturen der Distanzen jedes Datenbankobjekts zu ei- lichkeitsgrenzen, da alle Teildistanzen in Form von Distanzgrenzen ner Menge von Referenzobjekten. Die Reihenfolge der Datenban- eingehen. Für Anfragen mit vielen Features bedeutet dies, dass sich kobjekte ist dabei in allen Signaturdateien gleich. Die kNN-Suche die Anzahl der Objekte, die anhand dieser Grenzen ausgeschlossen verläuft analog zu GeVAS, wobei der Ausschluss von Objekten je- werden können, verringert und die Sucheffizienz des Verfahrens doch anhand aggregierter Ähnlichkeitsgrenzen stattfindet. sinkt. Um diesem Problem zu begegnen, werden bei steigender Featu- 6 reanzahl, statt Distanzgrenzen für jedes einzelne Feature zu nut- Die Beschreibungen lassen sich analog auf Ähnlichkeitsgrenzen anwenden. zen, nur noch für eine Teilmenge der verwendeten Features Di- stanzgrenzen abgeschätzt. Für alle anderen Features werden direkt Unterstützung von Multi-Objekt-Anfragen sowie von Distanzfunk- die exakten Distanzen berechnet. Aus der exakten Berechnung von tionen die keine Metriken sind, stellen weitere Herausforderungen Teildistanzen ergibt sich ein Mehraufwand gegenüber der Nutzung dar. von Distanzgrenzen. Dieser Mehraufwand kann jedoch ausgegli- chen werden, wenn durch diese exakte Berechnung genügend zu- Literatur sätzliche Objekte ausgeschlossen werden können. [1] Stanislav Barton u. a. “Estimating the indexability of multimedia de- Dieses Prinzip lässt sich in der Filterphase anwenden um mehr scriptors for similarity searching”. In: Adaptivity, Personalization Objekte auszuschließen. Analog zum sequentiellen Lesen der Si- and Fusion of Heterogeneous Information. RIAO ’10. 2010, S. 84– gnaturdateien müssen die Features in diesem Fall ebenfalls sequen- 87. tiell gelesen werden, um die Sucheffizienz in der Filterphase zu ga- [2] Klemens Böhm u. a. “Fast Evaluation Techniques for Complex Simi- larity Queries”. In: Proceedings of the 27th International Conference rantieren. on Very Large Data Bases. VLDB ’01. 2001, S. 211–220. Das gleiche Prinzip kann in der Verfeinerungsphase genutzt wer- [3] Benjamin Bustos, Gonzalo Navarro und Edgar Chávez. “Pivot selec- den, um die Suche früher und mit weniger exakten Distanzberech- tion techniques for proximity searching in metric spaces”. In: Pattern nungen abbrechen zu können. Statt für ein Objekt in der Verfei- Recogn. Lett. 24 (14 2003), S. 2357–2366. nerungsphase direkt alle Teildistanzen auf einmal exakt zu berech- [4] Benjamin Bustos und Tomáš Skopal. “Dynamic similarity search in nen und zu aggregieren, wird schrittweise vorgegangen. Jedes Mal, multi-metric spaces”. In: Proceedings of the 8th ACM internatio- wenn ein Objekt in der Verfeinerungsphase am Anfang der Kan- nal workshop on Multimedia information retrieval. MIR ’06. 2006, S. 137–146. didatenliste steht, für das noch nicht alle Teildistanzen berechnet [5] Edgar Chávez u. a. “Searching in metric spaces”. In: ACM Comput. wurden, wird eine Teildistanz berechnet und das Objekt anhand Surv. 33 (3 2001), S. 273–321. der neuen (genaueren) aggregierten Ähnlichkeitsgrenze wieder in [6] Paolo Ciaccia und Marco Patella. “The M2 -tree: Processing Com- die Kandidatenliste einsortiert. Ein Vorteil ergibt sich dann, wenn plex Multi-Feature Queries with Just One Index”. In: DELOS Work- der Ausschluss eines Objekts von nur wenigen Teildistanzen ab- shop: Information Seeking, Searching and Querying in Digital Li- hängt. Bei einer geeigneten Reihenfolge der berechneten Teildi- braries. 2000. stanzen müssen dann nur diese diskriminierenden Distanzen ex- [7] Paolo Ciaccia, Marco Patella und Pavel Zezula. “M-tree: An Effi- cient Access Method for Similarity Search in Metric Spaces”. In: akt berechnet werden, die Berechnung aller weiteren Teildistanzen VLDB’97, Proceedings of 23rd International Conference on Very kann gespart werden. Large Data Bases, August 25-29, 1997, Athens, Greece. Hrsg. von Die Auswahl der Features, für die exakte Distanzen berechnet Matthias Jarke u. a. 1997, S. 426–435. werden, erfolgt statisch (zur Indexierungszeit) oder dynamisch (zur [8] Ronald Fagin, Amnon Lotem und Moni Naor. “Optimal aggrega- Anfragezeit) nach unterschiedlichen Kriterien, wie der (intrinsi- tion algorithms for middleware”. In: Proceedings of the twentieth schen) Dimensionalität der Features oder der Berechnungsdauer ACM SIGMOD-SIGACT-SIGART symposium on Principles of data- base systems. PODS ’01. 2001, S. 102–113. der zugehörigen Distanzfunktion. [9] Antonin Guttman. “R-trees: a dynamic index structure for spatial searching”. In: Proceedings of the 1984 ACM SIGMOD internatio- 6.6 Indexauswahl nal conference on Management of data. SIGMOD ’84. 1984, S. 47– Die Sucheffizienz des beschriebenen Verfahrens hängt besonders 57. von der Anzahl der verwendeten Features und der daraus resul- [10] Yannis Ioannidis. “The history of histograms (abridged)”. In: Pro- tierenden (intrinsischen) Dimensionalität ab. Hierarchische Verfah- ceedings of the 29th international conference on Very large data ba- ses - Volume 29. VLDB ’03. 2003, S. 19–30. ren können bei niedriger (intrinsischer) Dimensionalität, aufgrund [11] Yossi Rubner, Carlo Tomasi und Leonidas J. Guibas. “The Earth Mo- der hohen Lokalität der Daten, größere Mengen von Objekten auf ver’s Distance as a Metric for Image Retrieval”. In: Int. J. Comput. einmal ausschließen und dadurch effizienter als nicht-hierarchische Vision 40 (2 2000), S. 99–121. Verfahren sein. Ein Vergleich des entworfenen Konzepts mit dem [12] Hanan Samet. Foundations of Multidimensional and Metric Data angepassten M2 -Baum dient daher zur Bestimmung der Schnitt- Structures (The Morgan Kaufmann Series in Computer Graphics and punkte bezüglich der Sucheffizienz beider Ansätze. Eine Selektion Geometric Modeling). 2005. des effizienteren Index kann dann entweder bereits bei der Index- [13] Ingo Schmitt. Ähnlichkeitssuche in Multimedia-Datenbanken - Re- erzeugung oder erst zur Anfragezeit anhand der in der Anfrage ge- trieval, Suchalgorithmen und Anfragebehandlung. 2005. nutzten Features und ihrer (intrinsischen) Dimensionalität stattfin- [14] Ingo Schmitt. “QQL: A DB&IR Query Language”. In: The VLDB den. Überschreitet die (intrinsische) Dimensionalität eine bestimm- Journal 17 (1 2008), S. 39–56. te Grenze, ist unter Umständen ein Rückfall auf den linearen Scan [15] Ingo Schmitt und Sören Balko. “Filter ranking in high-dimensional space”. In: Data Knowl. Eng. 56 (3 2006), S. 245–286. sinnvoll. [16] Enrique Vidal. “An algorithm for finding nearest neighbours in (ap- proximately) constant average time”. In: Pattern Recognition Letters 7. ZUSAMMENFASSUNG 4.3 (1986), S. 145 –157. In dieser Arbeit wurde ein Konzept zur flexiblen Indexierung für [17] Roger Weber, Hans-Jörg Schek und Stephen Blott. “A Quantitative Analysis and Performance Study for Similarity-Search Methods in Ähnlichkeitssuche mit logikbasierten Multi-Feature-Anfragen vor- High-Dimensional Spaces”. In: Proceedings of the 24rd Internatio- gestellt. Dazu wurden die spezifischen Anforderungen an geeignete nal Conference on Very Large Data Bases. VLDB ’98. 1998, S. 194– Indexierungsverfahren definiert und der Stand der Technik im Be- 205. zug auf diese Anforderungen analysiert. Das entwickelte Konzept [18] Lofti A. Zadeh. “Fuzzy Logic”. In: Computer 21 (1988), S. 83–93. zur Indexierung basiert auf einer Übertragung und Anpassung des [19] David Zellhöfer und Ingo Schmitt. “A preference-based approach GeVAS-Ansatzes auf den metrischen Raum. Der Index ist dadurch for interactive weight learning: learning weights within a logic- unabhängig von der genutzten logischen Kombination, der Art und based query language”. In: Distributed and Parallel Databases 27 (1 2010), S. 31–51. Struktur der verwendeten Features und unterstützt eine Vielzahl [20] David Zellhöfer und Ingo Schmitt. “Approaching Multimedia Retrie- unterschiedlicher Features und Distanzfunktionen zur Berechnung val from a Polyrepresentative Perspective”. In: Adaptive Multimedia der Unähnlichkeit. Retrieval. Context, Exploration, and Fusion. Hrsg. von Marcin De- Als zukünftige Arbeiten verbleiben Teile der Implementierung, tyniecki u. a. Bd. 6817. Lecture Notes in Computer Science. 2011, die Bestimmung der optimalen Indexparameter und die Evaluati- S. 46–60. on des Konzeptes anhand von synthetischen und realen Daten. Die