BTW, 26. Februar 2003Übertragung von Rangordnungen1 Ein Ansatz zur Übertragung von Rangordnungen bei der Suche auf strukturierten Daten Andreas Henrich

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



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



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 …



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


shapesimilarity(e.g. fromLSDh-tree)


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.



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



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



denkbare Übertragungssemantiken: Maximum: Minimum: Durchschnitt: gewichteter Durchschnitt:

…

Wir fordern lediglich:



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



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



RSV-Transfer-Algorithmus

Tagungsband



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



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




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




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




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)



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



Experimentelle Ergebnisse (2)



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

Documents

BTW, 26. Februar 2003Übertragung von Rangordnungen1 Ein Ansatz zur Übertragung von Rangordnungen bei der Suche auf strukturierten Daten Andreas Henrich