Post on 05-Apr-2015
transcript
BTW, 26. Februar 2003 Übertragung von Rangordnungen 1
Ein Ansatz zur Übertragung von Rangordnungen bei derSuche auf strukturierten Daten
Andreas Henrich und Günter RobbertAngewandte Informatik ISoftwaretechnik und InformationssystemeFakultät für Mathematik und PhysikUniversität Bayreuth
BTW, 26. Februar 2003
Übertragung von Rangordnungen S. 2
Übersicht
Ähnlichkeitsanfragen auf strukturierten Dokumenten Anfragebeispiel
Problemstellung
Übertragung von Rangordnungen: Mögliche Semantiken
Algorithmus RSV-Transfer
Prototypische Implementierung: Systemarchitektur
Experimentelle Ergebnisse
Ausblick
BTW, 26. Februar 2003
Übertragung von Rangordnungen S. 3
Thema: Ähnlichkeitsanfragen auf strukturierten Dokumenten
document
titledoc_typedescription
media_object
namedescription
chunk
namechunk_typedescription
segment
temporal_seg
startduration
spatial_seg
x_locationy_locationx_extensiony_extension
image
heightwidthcolordepthresolution
text audio
soundsystemchannelsquantisationsampleratelength
video
heightwidthframeratechannelscolordepthlength
1
1 *
*
1
*
1
*
1
*
Struktur
Medienobjekte
Segmentierung
BTW, 26. Februar 2003
Übertragung von Rangordnungen S. 4
Ein BeispieldokumentThesis : document
Einleitung : chunk
In dieser Arbeit …
Hauptteil : chunk Schluss : chunk
HT1 : chunk HT2 : chunkFerner …
In Zukunft …
Wir sehen …
Außer …
Hier …
Am Ende …
BTW, 26. Februar 2003
Übertragung von Rangordnungen S. 5
Beispielanfrage
chunk
textimage
image segment
ranking withrespect to
colorsimilarity(e.g. fromLSDh-tree)
combine streams(e.g. with Quick
Combine)
combinestreams (e.g.with QuickCombine)
transfer rankingwith RSV-Transfer
rankingaccording to theVSM (e.g. frominverted files)
transfer rankingwith RSV-Transfer
ranking withrespect to
shapesimilarity(e.g. fromLSDh-tree)
ranking withrespect to
texturesimilarity(e.g. fromLSDh-tree)
Image
ImageSegment1
ImageSegment3
ImageSegment2
Chunk
Text2Text1
Anfrage: Suche alle Bilder, dieein bestimmtes Logo enthalten und deren Text in der „Umgebung“ inhaltlich einem gegebenen Beispieltext ähnelt.
Anfrage: Suche alle Bilder, dieein bestimmtes Logo enthalten und deren Text in der „Umgebung“ inhaltlich einem gegebenen Beispieltext ähnelt.
Maximumsemantik
-Semantik
1.
2.
6.
5.
3.
4.
BTW, 26. Februar 2003
Übertragung von Rangordnungen S. 6
Beteiligte Komponenten Ranker
zur Erzeugung initialer Ströme Beispiel:
Bilder nach Farbähnlichkeit zu Anfragebild sortiert Verfahren und Indexstrukturen für Ranker:
invertierte Listen, R-Baum, X-Baum, LSDh-Baum, VA-File, … Combiner
zur Kombination mehrerer Rangordnungen: Buckley-Lewit, Nosferatu, Quick-Combine, J*, …
Transferer Übertragung von Rangordnungen zu verbundenen Objekten
bisher höchsten implizit in „Combinern“ Einführung eines expliziten RSV-Transfer-Algorithmus
BTW, 26. Februar 2003
Übertragung von Rangordnungen S. 7
Problem: Semantik der Übertragung
der Rangordnungen einfaches Beispiel: Suche alle Bilder, die ein Segment enthalten,
dass ähnlich zu einem gegebenen Logo ist
die Ordnung auf den Segmenten erfolgt i.d.R. über ein Ähnlichkeitsmaß retrieval status value (RSV)
Idee: Rangordnung der Bilder durch Übertragung der RSV-Werte der
Segmente bestimmen!
Aber wie? Mehrere Semantiken denkbar: RSV-Wert eines Bildes = maximaler RSV-Wert eines Segmentes
RSV-Wert eines Bildes = RSV-Wert eines Segmentes
…
Image
ImageSegment1
ImageSegment3
ImageSegment2
BTW, 26. Februar 2003
Übertragung von Rangordnungen S. 8
denkbare Übertragungssemantiken: Maximum: Minimum: Durchschnitt: gewichteter Durchschnitt:
…
Wir fordern lediglich:
BTW, 26. Februar 2003
Übertragung von Rangordnungen S. 9
Transferer: grundsätzliches Vorgehen einfache Beispielanfrage:
Gesucht werden die Bilder, die ein Segment enthalten, das einem gegebenen Logo ähnlich ist
Annahme: Bildsegmente werden von einem Eingabestrom bereits nach
Ähnlichkeit sortiert geliefert z.B. durch eine mehrdimensionale Zugriffsstruktur für Farbähnlichkeit z.B. durch eine Kombination von Rangordnungen für Farbe, Textur, …
Dieser Eingabestrom kann inkrementell verarbeitet werden: Initialisierung und dann: GetNext
BTW, 26. Februar 2003
Übertragung von Rangordnungen S. 10
Transferer: grundsätzliches Vorgehen Nimm das erste Segment aus dem Eingabestrom Bestimme das zugehörige Bild
Berechne den Ähnlichkeitswert RSVd für dieses Bild
Ordne das Bild in eine Prioritätswarteschlange AL ein
while ( RSVd-Wert des 1. Eintrags in AL > RSVr-Wert des nächsten Elements im Eingabestrom ) do gibt das Bild im Ausgabestrom aus
betrachte das nächste Bildsegment auf dem Eingabestrom bestimme das zugehörige Bild 1. Fall: dieses Bild ist bereits betrachtet worden
( nicht das ähnlichste Segment des Bildes) 2. Fall: dieses Bild wurde noch nicht betrachtet
BTW, 26. Februar 2003
Übertragung von Rangordnungen S. 11
RSV-Transfer-Algorithmus
Tagungsband
BTW, 26. Februar 2003
Übertragung von Rangordnungen S. 12
RSV-Transfer-Algorithmus: Anmerkungen Wichtige Eigenschaft des Algorithmus:
Inkrementell anwendbar
Spezialfall Maximumsemantik: Erlaubt Vereinfachungen des Algorithmus
Statt RSVd(od) zu berechnen kann beim 1. verbundenen Objekt or zu od direkt RSVr(or) genutzt werden
Weitere Vereinfachung:
Schleife zur Betrachtung mehrerer od Objekte kann bei einer 1:n-
Beziehung zwischen den Objekttypen entfallen
BTW, 26. Februar 2003
Übertragung von Rangordnungen S. 13
Systemarchitektur (1)
Grundlegende Ideen: Alle Daten werden in externen Datenquellen verwaltet Alle Anfragekomponenten arbeiten stream-orientiert
Retrievalfunktionalität wird oberhalb der Datenquellen realisiert
Prototyp stellt API für Entwicklung neuer Retrievaldienste bereit
Bereitstellung von Interfaces für die Erweiterbarkeit der
Retrievalfunktionalität
Implementierung des Prototypen in Java
BTW, 26. Februar 2003
Übertragung von Rangordnungen S. 14
Systemarchitektur (2)
Ranker Combiner Transferer Filter
Streamdeklarative QL Optimierer
grafischeBenutzungsoberfläche
API
Datenquellen-Wrapper
Zugriffss truktur-Wrapper
Stream-Wrapper
......
Met
adat
en
beliebige Anwendungen,die Ähnlichkeitsanfragen
stellen
Merkmalsextraktoren Metriken
M 1 MnFE1 FEm... ...
ORDBMS
BTW, 26. Februar 2003
Übertragung von Rangordnungen S. 15
Systemarchitektur (3)
Featureextraktoren, Metriken: für die inhaltsbasierte Suche auf multimedialen Daten
Hauptkomponenten für Anfrageverarbeitung: Prototypische Implementierung von:
Ranker, Combiner, Transferer, …
Alle Komponenten erweitern Interface Stream: Konstruktor: kreiert einen neuen Stream Init-Methode: initialisiert einen Stream getNext-Methode: liefert das nächste Element eines Streams
BTW, 26. Februar 2003
Übertragung von Rangordnungen S. 16
Systemarchitektur (4)
Metadaten-Repository: enthält alle Daten zur Verwaltung von Streams und Durchführung
von Anfragen
Wrapper (zur Systemerweiterung): Datenquellenwrapper:
Anbindung externer Datenquellen für die Suche
Zugriffsstrukturenwrapper:
Integration externer Zugriffsstrukturen für performante Ähnlichkeitssuche
Streamwrapper:
Anbindung externer Streams (externe Retrievalsysteme)
BTW, 26. Februar 2003
Übertragung von Rangordnungen S. 17
Experimentelle Ergebnisse (1) EckdatenTestkollektion:
Strukturierte Dokumente einer Computerzeitschrift: 2213 Artikel 29414 Textblöcke ca. 5000 Bilder ca. 20000 Bildsegmente
Verwendete Indexstrukturen: Zwei LSDh-Bäume :
10-dimensionale Vektoren für Farbcharakteristika 4-dimensionale Vektoren für Texturcharakteristika
BTW, 26. Februar 2003
Übertragung von Rangordnungen S. 18
Experimentelle Ergebnisse (2)
BTW, 26. Februar 2003
Übertragung von Rangordnungen S. 19
Ausblick
Ansatz für Übertragung von Rangordnungen: RSV-Transfer Algorithmus Prototypisch implementiert und evaluiert
Zur Zeit Gegenstand unserer Forschungen: Optimierungen am Prototyp Messungen bezüglich der Ergebnisqualität (INEX) Entwicklung einer graphischen Oberfläche für Anfragen