Get these flashcards, study & pass exams. For free! Even on iPhone/Android!

Objektrelationale DB sind eine Erweiterung relationaler DB. Ein Attribut kann hier auch eine Menge von Werten statt einem atomaren Attribut sein, die OODB erfüllen also nicht zwangsläufig die 1NF.

Der Vorteil ist, dass man N:M-Relationen zusammenfassen kann, die nicht-atomaren Mengen sind dabei Referenzen auf Daten, die in anderen Relationen gespeichert sind. Attribute können auch selber wieder Relationen sein. Neben User-defined Types können Objekte auch spezialisiert werden. Alle Tupel der Unter-Relation sind dann implizit auch in der Ober-Relation enthalten.

Um das in 1NF zu bringen, muss sich die Anwendung selbst darum kümmern.

Multimedia-Daten haben eine Semantik. Sie uninterpretiert zu speichern und zu durchsuchen bringt nicht viel, relationale DBMS sind auf Text- und Zahlenwerte ausgelegt. Das Ziel einer MMDB ist die inhaltsbasierte Suche, die MM-Daten werden strukturiert gespeichert. Beispielanfrage: "Zeige mir alle Bilder von Häusern vor einem blauen Himmel"

Die Suche selbst wird als Erweiterung von Information Retrieval implementiert, die neben klassischen Relationen die Mediendaten durchsuchen lamm.

Man könnte

• die Anfrage verändern (hier beschrieben)
• nutzerprofile verwenden
• dokumentbeschreibungen anpassen
• den Suchalgorithmus modifizieren
• Anfragetermgewichte modifizieren

Üblicherweise muss der Anwender seine Suche selbst anpassen (etwa bei Google). Alternativ könnte man Relevance Feedback anbieten.

Der Anwender markiert relevante und irrelevante Dokumente. Es geht auch über Pseudorelevanz, wo das System selber die nach seiner Meinung relevanten Dokumente aussucht (manuell ist aber besser).
Nach der Methode von Rocchio kann man aus dem alten Anfragevektor anhand der Bewertungen einen neuen machen, indem er in die Richtung der relevanten Dokumente verschoben wird:
, wobei und Gewichte für relevant und irrelevant sind, und die Menge der relevanten bzw. irrelevanten Dokumente sind.

Dazu unterschieden wir vier Stati von Dokumenten unterscheiden:

• false alarms: Als relevant eingestuft aber irrelevant
• false dismissals: Als irrelevant eingestuft aber relevant
• correct alarams: Korrekt als relevant eingestuft
• correct dismissals: Korrekt als irrelevant eingestuft

Darauf können Qualitätsmaße aufgebaut werden: Precision, Recal, Fallout

• Einfügen: Die relationalen Daten (Metadaten wie Typ, Format, Name, ...) werden in eine relationale DB gespeichert. Komplexe Objekte werden in primitive zerlegt, die Struktur wird aber für die Rekonstruktion gespeichert. Objekte werden ggf. normalisiert.
• Feature-Extraktion: Ein Feature ist ein inhaltstragender Eigenschaftswert eines Medienobjekts. Die Features sind eine kompakte Form des Objekts und sind die Grundlage der Ähnlichkeitsberechnung. Die Berechnung hängt vom Medientyp, beabsichtiger Ähnlichkeitsberechnung und verfügbaren Extraktionsalgorithmen ab. Nach der E kommt die Aufbereitung (skalieren, Abhängigkeiten beseitigen, überflüssige F entfernen). Abschließend werden die F für schnellen Zugriff indiziert.

To be continued...

Anforderungen an die FE:

• Adäquatheit: Die berechneten Werte einer Eigenschaft müssen diese Eigenschaft auch tatsächlich angemessen ausdrücken
• effiziente Berechnung
• Berücksichtigung von Invarianzen: Unabhängigkeit von ungewollten Eigenschaften wie verfälschende Lichtverhältnisse, Rotation etc
• Minimalität: Die Eigenschaft wird mit einer minimalen Anzahl von Feature-Werten ausgedrückt.
• Orthogonalität: Die Feature-Werte sind voneinander unabhängig (sonst ist keine isolierte Bearbeitung der Daten möglich).

Wir kennen:

• Die diskrete Fourier-Transformation (Ortsraum->Frequenzraum)
• Die diskrete Wavelet-Transformation (Ortsraum->lokal begrenzte Frequenzräume)
• Karhunen-Loeve-Transformation (Minimalität einer Menge von Medienobjekten)
• Latent Semantic Indexing (ähnlich KLT)

Der Nachteil der DFT ist, dass sich lokale Änderungen im einen Raum als globale Änderung im anderen Raum niederschlägt. Bei der Wavelet-Transformation werden Frequenzanteile für verschieden großen Intervalle berechnet.
Features können sich auch aus Orts- und Frequenzinformationen zusammensetzen. Ausserdem ist der Aufwand der WT O(n) statt ON(n*log n).

Angewendet wird die DWT zur:

• Feature-Normalisierung: Störfrequenzen können lokal entfernt werden. Mutterwavelet kann an Störsignal angepasst werden.
• Feature-Erkennung/Aufbereitung: Lokale Frequenz-Analyse, etwa Textur-Analyse.

Es gibt zwei Verfahren:

• Standardzerlegung: DWT wird komplett auf allen Zeilen durchgeführt, Ergebnis als 2D-Funktion aufgefasst. Auf diese wird die DWT auf alle Spalten ausgeführt.
• Nonstandard-Zerlegung: Alternierend pro neuer Auflösungsstufe zwischen beiden Dimensionen wechseln.

Klasse	Selbstidentität	Positivität	Symmetrie	Dreiecksu.
Distanzfunktion	x	x	x	x
Pseudo-DF	x	-	x	x
Semi-DF	x	x	x	-
Semi-Pseudo-DF	x	-	x	-

Selbstidentität:
Positivität:
Symmetrie:
Dreiecksungleichung:

Die Minkowski-DF ist die Verallgemeinerung der euklidischen und Cityblock-Distance:


Also Manhattan/Cityblock-Distance mit m=1, euklidische mit m=2.

Sie ist für m=2 rotationsinvariant (Einheiskreis), und immer translationsinvariant.

Indextrukturen dienen der effizienten Suche. Da Medienobjekt meist mehrdimensionale Features haben und die Schnittmengenbildung auf eindimensionalen Indexstrukturen suboptimal ist, werden hochdimensionale Indexstrukturen benötigt.

MI sollten

• korrekte und vollständige Ergebnisse finden
• bezüglich ihrer Dimensionen skalierbar sein (hochdimensional)
• Suche nach verschiedendimensionalen Objekten ermöglichen
• mit höchstens linearem Aufwand suchen
• möglichst viele Anfragearten unterstützen
• Updates effizient durchführen können
• verschiedene Distanzfunktionen erlauben
• möglichst speichersparend sein

Die Idee des BaB-Algo ist, Teilbäume von der Suche auszuschließen, wenn der Mindestabstand dieses Teilbaums
Eingabedaten sind ein Referenzpunkt p und ein Startknoten im Baum T.
Es wird eine obereGrenze mitgeführt (am Anfang unendlich), und eine Referenz auf den nächsten Nachbarn NN.

Nun wird T nach der lb-Distanz aufsteigend sortiert. Die lb-Distanz ist die kleinste quadratische Distanz zwischen Punkt und Cluster. Nun über sortiertes T iterieren:
Ist k aus T ein Blatt, so wird für jeden Punkt p aus k geprüft, ob die Distanz kleiner als obereGrenze ist. Falls ja: obereGrenze auf dist(k), NN=p.
Wenn k kein Blatt ist, wird geprüft, ob die kleinstmöglichste Distanz von q zu k größer ist als obereGrenze. Falls ja, wird der Knoten ignoriert, ansonsten wird BaB rekursiv auf k aufgerufen.

Der RKV-Algo ist ein modifizierter Branch-and-Bound-Algo. Er setzt voraus, dass ein Baum mit lokaler Gruppierung, Minimum Bounding Rectangles (MBRs) als Cluster-Geometrie und Feature-Objekten nur in den Blättern vorliegt.

Die Kindknoten werden anhand der MIN- (optimistisch) oder MINMAX-Dist (pessimistisch) sortiert. Die sortierten Kindknoten werden in der Active Branch List verwaltet. Es gibt drei Strategien, um nicht die gesamte ABL durchsuchen zu müssen:
1. Alle Knoten mit MIN-Dist > MINMAX-Dist entfernen.
2. obereGrenze auf kleinste MINMAX-Dist setzen.
3. Alle Knoten mit MINMAX-Dist > obereGrenze entfernen.

Für KNN-Anfragen: Sortierte Warteschlange mit k NN-Kandidaten, obereGrenze ist Distanz zum letzten Kandidat.

Der HS-Algorithmus verwendet statt einer Tiefensuche eine global sortierte Warteschlange mit Knoten, Blätter und Feature-Objekten mit minimaler Distanz lb zum Anfragepunkt:

1. Mit Wurzel initialisieren
2. Wenn entnommenes Kopfelement Knoten, dann werden Kinder eingefügt.
2. Wenn entnommenes Kopfelement Blatt, dann werden Feature-Objekte eingefügt.
2. Wenn entnommenes Kopfelement Feature-Objekt, dann fertig

Gut für getNext-Anfragen geeignet, aber viel Speicher nötig und keine Tiefen/Breitensuche und daher kein sequentieller Festplattenzugriff
Aufwand, um alle FOs auszugeben ist O(n * log(n))

Ist eine Erweiterung des B-Baums um mehrere Dimensionen. FOs können beliebige räumliche Ausdehnung haben.

Cluster-Bildung: lokal gruppierend.
Cluster-Überlappung: Können überlappen, führt zu weniger effizienter Suche
Balance: Ist balanciert durch Split-Algorithmus beim Seitenüberlauf und Seitenzusammenfassung beim Unterlauf.
Objektspeicherung: Nur in den Blättern.
Geometrie: MBR
Anzahl der Kindknoten: An Seitengröße angepasst.

Einfügen:

• Von der Wurzel ausgehend den Kindknoten suchen, dessen Volumen nur minimal erweitert werden müsste.
• Ist dies nicht eindeutig, den Kindknoten wählen, dessen Volumen das kleinste ist.
• Objekt einfügen und Vaterknoten anpassen.
• Wenn ein Knoten überläuft, MBR in zwei kleinere MBR mit minimaler Volumensumme zerlegen. Es gibt verschiedene Algorithmen, üblicherweise nimmt man den linearen.

Suche geht über BaB, HS- und RKV-Algorithmen. Bei Bereichsanfragen muss man in jeden Unterbaum navigieren, dessen MBR den Suchbereich schneidet. Ab Dimension 10 ist NN-Suche nicht mehr effizient. Ausserdem bei hohen Dimensionen stärkere Überlappung -> hoher Suchaufwand

Der R+-Baum ist ein R-Baum ohne Überlappung und erfordert daher einen neuen Einfügealgorithmus. Ein Einfügen kann die Anpassung mehrerer Blätter erfordern. Wenn kein umfassender MBR gefunden werden kann, müssen Einträge mehrfach vorkommen. Ist trotzdem effizienter als R-Baum aber in hohen Dimensionen immer noch ineffizient.

Der X-Baum ist ein hybrider Baum, der mit hohen Dimensionen umgehen können soll. Die Idee ist, dass bei starker Überlappung ein sequentieller Durchlauf schneller ist als ein Baum. Dann werden Superknoten eingefügt, die beliebig viele DB-Seiten umfassen können und sequentiell durchsucht werden.

Jeder MBR verwaltet eine Split-Historie, die alle bereits verwendeten Zerlegungsdimensionen speichert.

Beim Überlauf wird nun
1. zuerst eine herkömmliche topologische Zerlegung gemacht.
2. wird ein vordefinierter Überlappungsgrad überschritten, so wird unter Ausnutzung der Split-Historie eine Zerlegungsdimension ausgesucht.
3. wird dadurch die Balance-Bedingung verletzt (Mindestfüllgrad), wird ein Superknoten erzeugt.

Ab etwa 15 Dimensionen wird der X-Baum zu einem einzigen Superknoten.

Bei der Suche sind RKV und HS möglich. Die minimale Distanz (d(Op, Q)-d(O, Op)) gibt es in angenäherter Form als schnellen Filter. Cluster können mit der minimalen Distanz (d(o, Q) - r) und der Hilfe der Dreiecksungleichung ausgeschlossen werden.

Beim Einfügen analog zum R-Baum: Geeignetes Blatt ist das, dessen Radius nicht vergrößert werden muss (bei Gleichstand das mit dem nächstgelegenen Routing Object nehmen). Ansonsten das mit der minimalen Vergrößerung nehmen. Falls Radius verändert wurde, müssen die Radien auf dem Pfad bis zur Wurzel verändert werden.

Beim Überlauf muss ein Cluster in zwei neue Cluster mit eigenen Routing Objects zerlegt werden. Das Ziel ist, Volumen und Überlappung zu minimieren. Danach werden die FOs abwechselnd zugeordnet, um gleichgroße Cluster zu entwickeln.

Ab 20 Dimensionen versagt NN-Suche in Indexbäumen, es werden keine Teilbäume mehr ausgeschlossen, und ein sequentieller Durchlauf wäre effizienter: Der Fluch der hohen Dimensionen. Der Grund liegt in steigenden Approximationsfehlern und konstantem Abstand zwischen größter und kleinster Distanz. Das gilt auch für Metrik-Bäume wie den M-Baum.

Man kann versuchen:
Komplexe Distanzfunktionen durch einfache Distanzfunktion substituieren, solange diese Objekte korrekt ausschließt.
FastMap etwa bildet eine Metrik (Objekte und Distanzen) approximativ auf k-dimensionale Punkte und euklidische Distanzfunktionen ab.

Das Haar-Wavelet ist die einfachste Wavelet-Transformation. Die Ausgangsfunktion ist eine Funktion mit Funktionswerten. Diese Funktion wird auf Detailkoeffizienten und einen Skalierungswert abgebildet, indem iterativ nebeneinander stehende Werte der Funktion addiert bzw. subtrahiert werden. Höhere Auflösungsstufen haben weniger Skalierungswerte und Detailkoeffizienten.