Intelligenter Austausch von Daten in Private Area Networks

Inhaltsverzeichnis

1 Einleitung
1.1 Motivation
1.2 Aufbau der Arbeit

2 Einordnung der Aufgabenstellung in bestehende Netzwerktopologien
2.1 Private Area Networks
2.2 ad-hoc Netzwerke
2.2.1 Strukturiertheit
2.2.2 Hierachiegrad
2.2.3 Kopplungsgrad
2.2.4 Ergebnisse

3 Informationsverwaltung
3.1 Indexierung in Datenbanksystemen
3.2 Grundlagen des Information-Retrieval
3.3 Standard Modelle des Information-Retrieval
3.3.1 Das Boolesche Modell
3.3.2 Das Vektorraum Modell
3.3.3 Das Probabilistische Modell
3.4 Informationsangebot durch invertierte Listen und weitere Indeierungsverfahren in PANs

3.4.1 Invertierte Listen
Tries
Patricia Baume
Pra x Baume
Index Fabric

3.4.2 Bloom lter

4 Informationsbescha ung
4.1 ad-hoc Routing
4.1.1 Anforderungen mobiler ad-hoc Netzwerke
4.1.2 Routing-Verfahren
Link-State
Distance-Vector
Proactive
Reactive
Topologiebasiert
Positionsbasiert
Inhaltsverzeichnis
Hybrid
4.1.3 Routing Algorithmen
4.1.4 Replikation
Ziele der Replikation
Replikationsmoglichkeiten
Datentypen
4.1.5 Fazit
4.2 Anfrageverarbeitung kontextbezogener Daten
4.2.1 Positionierungsdienste
4.2.2 Verwaltung von Kontextinformationen in Nutzerpro len

5 Konzeption eines Prototypen
5.1 Zielsetzung
5.1.1 Grenzen des Tourismusszenarios
5.1.2 Initiierung eines Private Area Networks
5.1.3 Schnittstellen zur o ine/online Kommunikation
5.2 IMSY - ein System zum intelligenten Datenaustausch in Private Area Networks
5.2.1 Kernkomponenten von IMSY
5.3 Suche nach- und P ege von Informationen
5.4 Indexierung von Objekten im IMSY System
5.4.1 Beschreibung der Objekte anhand von Metadaten
5.4.2 invertierte Listen zur Speicherung der Metadaten
5.4.3 alternative Speicherungstechniken
spektraler Bloom lter ohne Komprimierung
spektraler Blomm lter mit Komprimierung
5.5 Datenaustausch im IMSY System
5.5.1 Eintritt eines Knotens in das Private Area Network
5.5.2 Routen von Objekten
5.5.3 Replikation

6 Prototyprealisierung
6.1 Indexierung
6.1.1 Datenbankmodell zur Speicherung von Metadaten
6.1.2 lokale Indexierung
6.1.3 globale Indexierung
6.1.4 Hardwarpro le
6.2 Suche nach Informationen
6.2.1 Schnittstellenbeschreibungen
6.2.2 Ranking
6.3 ad-hoc Netzwerke mit Bluetooth
6.3.1 Obex Protokoll
6.3.2 Realisierung eines Bluetooth ad-hoc Netzes in IMSY
Bluetooth Programmierschnittstelle
Umsetzung der Bluetooth Funktionalitaten
Auswertung der Obex Nachrichten
6.4 Zusammenspiel der einzelnen Module

7 Schlussbetrachtungen
7.1 Ergebnisse
7.2 Ausblick

Abbildungsverzeichnis

Tabellenverzeichnis

Literaturverzeichnis

A Anhang
A.1 Peer-to-Peer Netzwerke
A.2 DSR und AODV
A.2.1 Dynamic Source Routing (DSR)
A.2.2 Ad-hoc On-Demand Vector Routing (AODV)
A.3 Bluetooth Grundlagen zur Realisierung eine P2P Netzwerkes
A.3.1 technische Grundlagen
A.3.2 Verbindungsaufbau
A.3.3 Piconetze
A.3.4 Scatternetze

Zusammenfassung

In dieser Arbeit werden Schnittstellen fur mobile Endgerate entwickelt, um kontextbezogene Anfragen in ad-hoc Netzwerken (o ine Betrieb) sowie per ClientServer Architektur (online Betrieb) umzusetzen. Moglichkeiten der Indexierung und Verbreitung von Index Informationen in Netzwerken werden betrachtet, die in einem Prototyp zum Einsatz kommen, mit deren Hilfe das Echtzeitverhalten der Strategien uberpruft werden soll.

Schlusselworter

ad-hoc, ad-hoc Routing, Bloom lter, Indexierung, Information-Retrieval, invertierte Listen, IR-Modelle, Peer-to-Peer

Abstract

In this thesis interfaces for mobile terminals will be developed to realize context- referred queries in ad-hoc and client-server networks. Possibilities of indexing and spreading of this index-informations will be discussed. After all, a prototy- pe will be developed, to test the real-time behaviour of the strategies.

Keywords

ad-hoc, ad-hoc routing, bloom lter, indexing, information-retrieval, invertedlists, IR-model, peer-to-peer

1 Einleitung

Mobilitat hat in den letzten Jahren sehr an Bedeutung gewonnen. Insbesondere in der Informationstechnologie dienen Mobiltelefone oder PDAs als Wissenquel- le in allen Lebenslagen, an jedem Ort und zu jeder Zeit. Der heutige Stand der Technik ermoglicht es, Anwendungen fur diese Gerate fur spezielle Szenarien zu entwickeln.

1.1 Motivation

In dieser Arbeit wird anhand eines exemplarischen Tourismusszenarios\ der in- " telligente Austausch von Daten (Informationen) in mobilen Umgebungen (Pri- 1 vate Area Networks bzw. Personal Area Networks im Folgenden auch PANs genannt) betrachtet.

Ein Tourist mochte uber eine Attraktion moglichst genaue Informationen erlangen. Nicht immer stehen ihm diese sofort zur Verfugung. Mit Hilfe seines PDAs oder Mobiltelefons kann der Tourist nun nach Informationen suchen. Dies kann durch eine Anfrage an einen Server oder durch die Anfrage gleichberechtigter Teilnehmer eines Private Area Networks realisiert werden. Ziel der Arbeit ist es, die Moglichkeiten des Wissensaustausches dieses Szenarios aufzuzeigen und prototypisch mittels Bluetooth zu realisieren. Im Mittelpunkt der Betrachtungen stehen dabei Themen wie:

Informationsverwaltung:

Welche Moglichkeiten gibt es, Daten e zient auf mobilen Geraten zu ver- walten?

Im Vordergrund der Betrachtungen stehen hier vor allem Datenbank- sowie Information Retrieval Techniken wie z.B. invertierte Listen und Bloom lter als Grundlage der Indexierung lokaler Datenbestande.

Informationsbereitstellung in PANs:

Welche Moglichkeiten gibt es, Nutzern eines Private Area Networks vorhandene Daten zuganglich zu machen?

Aufbauend auf Prinzipien der Informationsverwaltung werden hier Bloom- lter erneut aufgegri en. Spektrale Bloom lter (vgl. 3.4.2) dienen der lo- kalen Indexierung des Datenbestandes sowie der Vor lterung von Suchan- fragen. Durch Mischvorgange lokaler Bloom lter mit eingehenden Infor- mationen wird eine globale Sicht des Netzwerk Datenbestandes erzeugt, die im folgenden Proze die Grundlage der Informationssuche ist.

Informationsbescha ung, - erganzung in PANs:

Wie konnen kontextbezogene Daten durch Suchanfragen in PANs gefunden bzw. bestehende Daten erganzt werden?

Schwerpunkt dieses Abschnittes ist die Konzeption einer Schnittstelle zur kontextabhangigen Suche innerhalb eines Private Area Networks. Kontextabhangig bedeutet hier in erster Linie die Einbeziehung hardwarespezi scher Gegebenheiten des mobilen Endgerates. Weitere Kontextspezi aktionen werden im Kapitel 4.2 behandelt.

Wird das Problem der Informationssuche innerhalb eine PANs auf den Scanbereich des Endgerates begrenzt, so konnen Probleme des Routings au en vor gelassen werden. Das Kapitel des ad-hoc Routing wird in dieser Arbeit einfuhrend behandelt, um mogliche Strategien fur eine Erweiterung der zu entwickelnen Losung vorzustellen und zu bewerten.

Informationsreplikation:

Wie konnen Daten innerhalb eines Private Area Networks kontinuierlich zur Verfugung gestellt, bzw. wie kann der Zugri auf Informationen beschleunigt werden?

Dieser Abschnitt gibt einen Ausblick auf mogliche Replikationsstrategien, die eine schnellere Suche nach Informationen zur Folge haben konnen.

1.2 Aufbau der Arbeit

Kapitel 2 gibt einen Uberblick uber Techniken dynamischer ad-hoc Netzwerke. Es werden die Vor- und Nachteile der einzelnen Anwendungsgebiete betrach- tet, um eine Einordnung der Problemstellung in bestehende Entwicklungen zu ermoglichen und gegebenfalls Ansatze fur die Konzeption des Prototyps zu ge- winnen.

In Kapitel 3 werden Techniken zur e zienten Verwaltung von Daten (geringer Speicherverbrauch, gewinnbringende Indexierung von Information, Replikation) sowie deren Publizierung innerhalb eines PANs betrachtet. Hierbei steht vor allem die Indexierung der Daten im Mittelpunkt, deren Ziel es ist, Informationen schnellstmoglich und auf dem kurzesten Wege zu nden, um die Netzlast des Private Area Networks so gering wie moglich zu halten.

Ausgehend von den Indexierungsstrategien werden in Kapitel 4 die Proble- me des Routings und der Replikation von Informationen betrachtet.Es werden Konzeptionsvorschlage entwickelt, die teilweise im Prototypen realisiert werden oder aber in einer weiteren Arbeit erganzend hinzugefugt werden konnen. Wei- terhin wird auf das Thema der Anfrageverarbeitung kontextbezogener Daten eingegangen.

Kapitel 5 fast die Ergebnisse der betrachteten Fragestellungen in Hinblick auf das Szenario zusammen und stellt den resultierenden Prototyp , eine Anwen- " dung zum intelligenten Austausch von Informationen innerhalb eines Private Area Networks\ , vor. Kapitel 6 gibt einen Uberblick uber die konkrete Umsetzung des Prototyps. Des Weiteren werden hier Fragestellungen und Losungsansatze zur Realisierung eines Bluetooth ad-hoc Netzwerkes erortert.

Abschlie end gibt Kapitel 7 einen Ausblick auf mogliche Erweiterungen der vorgeschlagenen Realisierungkonzepte. Weiterhin werden Alternativmoglichkei- ten aufgezeigt.

2 Einordnung der Aufgabenstellung in bestehende Netzwerktopologien

2.1 Private Area Networks

Netzwerke, die einen privaten Adressbereich teilen, werden als sogenannte Pri- " vate Netzwerke\ bezeichnet. Teilnehmer dieses Netzwerktyps haben in der Regel keinen Zugang zu Diensten des Internets, da diese nicht benotigt werden. Der Daten- bzw. Informationsaustausch erfolgt lediglich zwischen den Netzwerk- teilnehmern. Wird als Protokoll zur Datenubertragung der Bluetooth Standard verwendet, so wird im Allgemeinen von Private Area Networks\ gesprochen.

Einher mit dieser Bezeichnung geht auch der Begri des Personal Area Net- " works\ . Hiermit werden Netzwerke bezeichnet, die im Umkreis von wenigen Metern um einen Nutzer ihren Einsatz nden [BG01]. In PANs konnen sich z.B. Mobiltelefone, PDAs und Noteboks verstandigen, um gegenseitig Ressour- cen und Dienste zu nutzen oder Daten zur Verfugung zu stellen. Die Kommunikation zwischen mobilen Endgeraten erfolgt zum Gro teil im ad- hoc Modus.

2.2 ad-hoc Netzwerke

Ad-hoc Netzwerke werden dadurch charakterisiert, dass sie nicht durch eine gleichbleibende, permanent vorhande Infrastruktur de niert werden. Teilnehmer eines ad-hoc Netzwerkes konnen diesem jederzeit ohne administrativen Aufwand beitreten oder dieses verlassen.

Es werden Mobile ad-hoc Netzwerke (MANET)\ und Immobile ad-hoc Netz- " " werke\ unterschieden, wobei die Bezeichnung mobil\ dabei den Bewegungsgrad " eines Teilnehmers (im Folgenden auch als Knoten, Node oder Station bezeich- net) dieses Netzwerkes beschreibt. Die Verbindungsqualitat zweier Knoten des MANETs kann beeintrachtigt werden, da durch die standige Bewegung der Stationen der Ubertragungsweg nicht permanent garantiert werden kann. Die folgenden Betrachtungen beziehen sich im Weiteren auf wireless MA- " NETs\ , da bei dem vorgestellten Szenario nur eine kabellose Datenubertragung zustande kommt.

2.2.1 Strukturiertheit

In strukturierten P2P Systemen verwalten einzelne Peers globale Informationen (z.B Indexeintrage). Dadurch ist eine zielgerichtete Suche moglich. (vergleiche Freenet\ )

Im Gegensatz dazu wird bei unstrukturierten P2P Systemen eine Suchanfrage an alle erreichbaren Knoten weitergereicht, solange die Lebensdauer einer Anfrage nicht abgelaufen ist. Hierdurch steigt die Netzbelastung des Systems immens. (vergleiche Gnutella\ )

2.2.2 Hierachiegrad

Im Wesentlichen werden drei hierachische Strukturen unterschieden:

Zentralisiertes Modell:

Ein zentraler Knoten verwaltet alle Indixes des gesamten Netzwerkes. Nachdem der Index einer Information abgefragt wurde, kommunizieren die entsprechenden Peers direkt untereinander. Bei einem Ausfall des Index-Knotens ist eine Suche innerhalb des Netzwerkes nicht mehr moglich. (vergleiche Napster\ )

Dezentrales (verteiltes) Modell:

Im Gegensatz zum zentralisierten Modell werden Index-Eintrage im de- zentralen Modell verteilt organisiert. Teilnehmer agieren direkt unterein- ander.

Hierachisches Modell:

Eine Mischform der bisher dargelegten Modelle ist das hierarchische Mo- dell. Super-Peers verwalten hier die globalen Indixes. Bei einem Ausfall einzelner Super-Peers sind Suchen innerhalb des System teilweise noch moglich. Super-Peers sollten uber einen langeren Zeitraum zur Verfugung stehen.

2.2.3 Kopplungsgrad

In stark gekoppelten P2P Systemen gehoren die Teilnehmer immer zu einer Gruppe. Den Knoten wird beim Eintritt eine eindeutige Identi kation zugewie- sen. In lose gekoppelten Systemen kann sich die logische Adresse andern.

Abschlie end ein Uberblick vorhandener P2P System in Hinblick auf die vorgestellten Charakteristika:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2.1: P2P Systeme

2.2 ad-hoc Netzwerke

2.2.4 Ergebnisse

Im vorgestellten Szenario agieren die Teilnehmer direkt miteinander. Jeder Kno- ten kann dem Netzwerk standig beitreten oder dieses verlassen. Demnach kann es keine Super-Peers im System geben. Um eine schnelle Suche nach Informatio- nen zu ermoglichen, sollen Peers eine globale Sicht auf das Netzwerk erhalten. Knoten werden im System anhand ihres Bluetooth Gerates identi zert. Werden diese Kriterien verwendet, so handelt es sich bei dem zu entwickel- nen System um ein strukturiertes, dezentrales und stark gekoppeltes Modell. Anhang A stellt einige Vertreter vergleichend vor, um diesen Sachverhalt zu verdeutlichen.

3 Informationsverwaltung

Datenbanken bieten in Hinblick auf die Verwaltung kontextbezogener Informationen wesentliche Vorteile. Daten lassen sich strukturiert unter Vermeidung von Redundanzen unabangig von ihren Speicherungstrukturen in Relationen ablegen. Des Weiteren lassen sich Beziehungen auf einfachstem Wege darstellen. Datenbankmanagmentsysteme garantieren unter anderem eine konsistente Datenhaltung, Datenschutz sowie einen synchronisierten Zugri , der vor allem in P2P Anwendungen eine herausragende Bedeutung hat.

Innerhalb eines Netzwerks konnen Knoten verschiedene Informationen lokal verwalten. Um die Suche zu vereinfachen bzw. den Zugri auf Daten zu beschleunigen, ist es von Noten, Daten zu indexieren.

3.1 Indexierung in Datenbanksystemen

Datenbanksysteme unterstutzen sogenannte Zugri spfade\ . Zugri spfade be- " zeichnen Zugri strukturen, die uber grundlegende Dateiorganisationsformen hinausgehen.

Ein Primarindex kann die Dateiorganisationsform, z.B. eine sortierte Speicherung, der internen Relation ausnutzen. Somit konnen schnellere Zugri e ermoglicht werden. Jeder weitere Zugri pfad auf eine interne Relation wird als Sekundarindex bezeichnet (vergleiche [SHS05])

Indexeintrage haben in der Regel die Form (K; K ). K bezeichnet hier den Wert des Primar- oder Sekundarschlussels. Fur K sind folgende Formen moglich:

K ist ein Datensatz: Der Zugri spfad wird hier nun zu einer Datei- organisationsform, da die internen Werte nach K organisiert gespeichert werden.

K ist Adresse eines internen Tupels: Hierduch konnen Primarschlussel (durch einmaliges auftreten des Wertes K) oder auch Sekundarschlussel (mehrere Eintrage der Form (K; K 1); :::; (K; K n)) unterstutzt werden.

K ist eine Liste von Tupeladressen: Hierdurch werden vor allem Se- kundarschlussel unterstutzt. Die dynamsiche Lange eines solchen Index- eintrages erschwert aber die Verwaltung dieser Eintrage, da kein fester Speicherbereich fur derartige Indexeintrage vergeben werden kann.

3 Informationsverwaltung

Weiterhin spricht man bei der Verwendung von Datenbanken oft auch von einem dunnbesetzten-/dichtbesetzen Index\ (Anzahl der Datensatze die auch einen " Indexeintrag haben)

dunnbesetzt: nicht alle Datensatze

dichtbesetzt : alle Datensatze

oder auch von einem geclusterterten-/nicht-geclusterten Index\ (Organisation " des Index in Bezug auf die Organisationsform der internen Realtion). Ausfuhrli- che und weitergehende Informationen dazu konnen [SHS05] entnommen werden.

3.2 Grundlagen des Information-Retrieval

Unabhangig von den Indexierungsmoglichkeiten innerhalb einer Datenbankma- nagmentsystems wurden insbesondere im Gebiet des Information Retrieval "

(IR)\ Strategien zum Au nden von Daten anhand von Anfragen entwickelt. Der Information-Retrieval Prozess kann Abbildung 3.1 entnommen werden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.1: Information-Retrieval Prozess [Kuropka04]

Nachdem Dokumente einer Nutzergruppe zur Verfugung gestellt worden sind, zum Beispiel Teilnehmern eines Netzwerkes, ist es die Aufgabe eines IR-Systems,

3.2 Grundlagen des Information-Retrieval

diese Dokumente durch ein entsprechendes Modell der Suche innerhalb der Nutzergruppe (lokal und global) zur Verfugung zu stellen. In einigen Systemen ist es nach einem Suchprozess moglich, Ergebnisse einer Suchanfrage zu bewerten bzw. die Dokumente selbst abzuandern. Diese Anderungen konnen das Ergebnis neuer Anfragen beein ussen.

Im Wesentlichen werden folgende IR-Modelle unterschieden:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.2: Information-Retrieval Modelle [Kuropka04]

Mengentheoretische Modelle bilden Dokumente auf Mengen ab und fuhren Ahnlichkeitsuntersuchungen anhand von Mengenoperation wie [; \ durch.

Im Gegensatz dazu bilden Algebraische Modelle oder Vektorraum Modelle Dokumente auf Vektoren oder Tupel ab. Zwischen Anfrage- und Dokumentenvektor wird dann ein Ahnlichkeitsma betrachtet:

Abbildung in dieser Leseprobe nicht enthalten

Probalistische Modelle betrachten die Wahrscheinlichkeit, dass ein Do- kument relevant ist fur eine Anfrage. Die Menge aller Dokumente D wird in relevante Dokumente R und nicht relevante Dokumente R unterteilt. Das Ranking eines Dokumentes berechnet sich dann aus den Wahrschein- lichkeiten:

Abbildung in dieser Leseprobe nicht enthalten

3 Informationsverwaltung

Modelle ohne Terminterdependenzen betrachten Terme als orthogonale Einheiten (unabhangig voneinander)

Modelle mit Terminterdependenzen hingegen gehen von einer Ortho- gonalitat der Terme aus. Modelle mit Immanenter Terminterdepen- denz gehen davon aus, dass durch das Modell selbst der Zusammenhang zweier Terme gegeben ist. Im Gegensatz dazu muss bei Transzendenter Terminterdependenz die Beziehung der Terme von aussen z.B durch den Nutzer de niert werden.

Speziell fur den Bereich der Textsuche gelten invertierte Listen\ als ein sehr " verbreitetes Verfahren. Das Hauptziel des IR ist [...] nding the documents that are useful to the information need " expressed by a query.\ ([Hust04]).

Die Nutzlichkeit eines Dokumentes in Bezug auf die Anfrage wird anhand eines Ranking Wertes beschrieben.

De nition 3.2.1 Ein Dokument bezeichnet ein Multiset von Wortern. Beim IR spielt die Organisation der Worte in Satze oder Kapitel meist keine Rolle. Dokumente werden im Folgenden mit d oder di gekennzeichnet. Die Menge aller Dokumente wird durch D beschrieben.

De nition 3.2.2 Eine Anfrage bezeichnet ebenfalls ein Multiset von Wortern unter Vernachlassigung der Organisation der Worte.

Anfragen werden im Folgenden mit q oder qi gekennzeichnet. Die Menge aller Anfragen wird beschrieben durch Q.

De nition 3.2.3 Terme sind Transformationsergebnisse von Worten der Dokumente oder Anfragen. Sie dienen der Textsuche als Ausgangsbasis.

Terme werden durch t oder ti reprasentiert. Die Menge alle Terme erhalt die Bezeichnung T. De nition 3.2.4 Transformationen bezeichnen Prozesse oder Abbildungen ( D ) T ) des Information Retrievals, bei denen Worter eines Dokumentes auf Terme durch Verfahren wie Stammwortreduktion oder Worttrennung abgebildet werden.

De nition 3.2.5 Ranking Funktionen verfolgen das Ziel, Dokumente in einer geordneten Liste bezuglich der relativen Relevanz dieser Dokumente im Vergleich mit einer Anfrage wiederzugeben. Die Ordnung der Dokumente wird durch einen Ranking Wert des Dokumentes bestimmt.

Eine Ranking Funktion wird im folgenden durch rank() beschrieben.

Standard Verfahren des Information-Retrieval betrachten oft nur Terme eines Dokumentes und versuchen anhand von Termhau gkeiten oder Termpositionen den Ranking Wertes eines Dokumentes zu bestimmen.

In mobilen Umgebungen kann der Kontext des Nutzers, z.B. die lokale Positi- on, die Zugri sgeschwindigkeit des mobilen Endgerates auf das Netzwerk oder die Darstellungmoglichkeiten des Endgerates, ausschlaggebend fur ein globales Ranking der Dokumente sein.

3.3 Standard Modelle des Information-Retrieval

Im vorherigen Kapitel wurden bereits einige Modelle kurz vorgestellt. Dieser Abschnitt soll nun einen ausfuhrlicheren Einblick in diese Modelle geben sowie Vor- und Nachteile der einzelnen Systeme genauer betrachten.

3.3.1 Das Boolesche Modell

Beim booleschen Modell werden Dokumente und Anfragen als Mengen von Ter- men betrachtet. Diese Mengen werden durch boolesche Operatoren wie and, or oder not verknupft. Es werden nun die Dokumente als Ergebnis einer Anfrage geliefert, die die Terme der Anfrage in deren Kombination der Verknupfung (Operatoren) enthalten. Obwohl dieses Modell durch seine Einfachheit sehr ef- zient zu implemntieren ist, wei t es doch einige entscheidene Nachteile auf:

Die Terme eines Dokumentes werden nicht gewichtet. Insofern ist ein Do- kument, das durch einen Term tA indexiert wird, gleich relevant in Bezug auf eine Anfrage tA or tB , wie ein Dokument mit der Indexierung tB .

Boolesche Operatoren haben einen strengen mathematischen Hintergrund. Oft ist die mathematische Interpretierung dieser Operatoren eine andere, als die Interpretation, die ein Nutzer bei der Anfrageformulierung umzu- setzen versucht.

Das Standard Modell erlaubt es nicht, Terme einer Anfrage zu gewichten. Demnach kann keine Entscheidung getro en werden, ob ein Term tA einer Anfrage relevanter als ein Term tB dieser Anfrage ist.

Erweiterungen des Standard Modells ([Hust04],[Homann04],[Wol 04]) versuchen diesen Limitierungen entgegenzuwirken. Hierzu zahlen unter anderem das Fuzzy-Mengen Modell:

Abbildung in dieser Leseprobe nicht enthalten

Die Dokumente d1; d2 sind in Bezug auf die Anfrage also gleich relevant. Viele Menschen wurden aber behaupten, dass das Dokument d2 der Anfrage q ahn- licher ist.

Ein weiteres Modell, dass hier zu nennen ist, wird als Waller-Kraft Modell bezeichnet:

Abbildung in dieser Leseprobe nicht enthalten

Hier werden die Maximum und Minimum Operatoren gemischt, wodurch eine bessere E ektivitat erzielt wird.

Das Paice-Modell sortiert vor der eigentlichen Berechnung die Gewichte der Terme:

Abbildung in dieser Leseprobe nicht enthalten

Wie man ersehen kann, werden hier alle Termgewichte zur Berechnung der Ahnlichkeit herangezogen. Wenn n = 2 ist, so verhalt sich dieses Modell wie das Mixed Min And Max Modell von Fox, Sharat [FS86]. Bei AND-Anfragen werden kleine Termgewichte priorisiert und im Gegensatz dazu bei OR-Anfragen gro e Termgewichte:

Abbildung in dieser Leseprobe nicht enthalten

Damit den Minimalwerten der Dokumentgewichte bei AND-Anfragen sowie den

Maximalwerten der Dokumentgewichte bei OR-Anfragen mehr Bedeutung zu-

gewiesen wird, gilt:

Cand1 > Cand2

Cor1 > Cor2

oder zur Vereinfachung:

Cand2 = 1 Cand1

Cor2 = 1 Cor1

[Wol 04] kann eine ausfuhrliche Erlauterung entnommen werden.

Abschlie end erlaubt das P-Norm Modell eine zusatzliche Gewichtung der Anfrage Terme, das hei t, jedem Term ti der Anfrage q wird ein Gewicht ai zugewiesen:

rank(dk; qand)

sPn p

(a wp )

i ki

= p Pn p

(a )

i=1 i

s

p rank(dk; qor ) = 1

Pn p

(a (1

i=1 i

Pn p

i=1(a )i

wp )) ki

p = Grad der Genauigkeit; 1 p 1

3.3 Standard Modelle des Information-Retrieval

Bei p Werten gro er 1 kann der Berechnungsaufwand fur dieses Modell aber schnell sehr gro sein, da viele Exponentenberechnungen durchgefuhrt werden mussen.

3.3.2 Das Vektorraum Modell

Beim Vektorraum Modell werden Dokumente und Anfragen als Punkte in einem hochdimensionalen metrischen Vektorraum betrachtet.

De nition 3.3.1 Die Menge der N Dokumente wird charakterisiert durch:

Abbildung in dieser Leseprobe nicht enthalten

die Menge der L Anfragen anhand:

Abbildung in dieser Leseprobe nicht enthalten

wobei jedes einzelne Dokument durch:

Abbildung in dieser Leseprobe nicht enthalten

und jede einzelne Anfrage mit:

Abbildung in dieser Leseprobe nicht enthalten

M: Anzahl der Terme der Kollektion beschrieben wird.

Jede i 'te Position des Vektors gehort zu einem Term ti der Kollektion. Die Werte wij , wik indizieren dementsprechend die gewichtete Reprasentation eines

Termes des Dokumentes dj bzw. der Anfrage qk

Die Abbildung eines Dokumentes d auf einen Punkt im Vektorraum Vd wird durch eine Indexierungsfunktion durchgefuhrt. Zum Bilden der Indexierungs- funktion werden sogenannte Features Fi herangezogen.

Als erstes wird die absolute Hau gkeit des Auftretens des Features Fi im Doku- ment dj (h(Fi)jdj ) betrachtet. Weiterhin wird die absolute Hau gkeit des Fea- tures Fi in der gesamten Dokumentmenge D betrachtet (h(FijD)). Aus h(FijD) werden sogenannte globale Merkmalsgewichtungen berechnet und daraus dann dokumentenspezi sche Merkmalsgewichtungen w(Fijdj ). Oft werden hier Merk- male wie Termfrequenz tf und inverse Dokumenthau gkeit idf herangezogen. Das folgende Beispiel soll diesen Sachverhalt verdeutlichen: [HMK05]

Wortmenge W : Menge der Worte die bei der Indezierung berucksichtigt werden W= fInformation; Retrieval; Ranking; Indexingg

Dokumente di mit Angabe der Vorkommenshau gkeiten einzelner Terme: d1 = fInformation(3); Retrieval(3); Ranking(2)g

Abbildung in dieser Leseprobe nicht enthalten

Phase 1: Gewichteberechnung tf; idf :

Abbildung in dieser Leseprobe nicht enthalten

Hierraus ergeben sich folgende Werte:

Abbildung in dieser Leseprobe nicht enthalten

Dementsprechend lassen sich nun die Termgewichte wij mit [Abbildung in dieser Leseprobe nicht enthalten]berechnen.

Phase 2: Kosinus zwischen Anfragevektor und Dokumentenvektor[Abbildung in dieser Leseprobe nicht enthalten]

Zu den Hauptvorteilen des Vektor Modells zahlen:

Abbildung in dieser Leseprobe nicht enthalten

Die Retrieval Performance wird durch die Gewichtung der Terme verbes- sert.

Durch den Ahnlichkeitsvergleich von Anfragen und Dokumenten lassen sich Ranking Werte der Dokumente ableiten.

Ranking im Vektorraummodell

Bei der Suche nach Dokumenten anhand einer Anfrage werden alle Dokumente einer Kollektion entsprechend ihrer Ahnlichkeit\ zur Anfrage bewertet (ge- " rankt). Die top-gewerteten Dokumente werden an den Nutzer, der die Anfrage gestellt hat, zuruckgeliefert. Ahnlichkeit ist dabei als ein mathematischer Be- gri zur verstehen. Es gibt verschiedene Ansatze um den Begri der Ahnlichkeit zu erlautern:

Fur eine Menge U mit den Elementen x; y; z 2 U kann folgendes gelten:

1. x und y sind ahnlich
2. x und y sind nicht ahnlich
3. x und y sind ahnlicher als x und z

Wird Aussage 3 benutzt, so lasst sich ein Formalismus ableiten, der fur ein Ran- king geeignet ist. Im Gegensatz dazu lassen die Aussagen 1 und 2 dies nicht zu. Zum Ranking im Vektorraummodell wird meistens die Kosinus Ahnlichkeit\ " verwendet.

De nition 3.3.2 dj , und qk sind gema 3.3 bzw 3.4 de niert. Die Ahnlichkeit zwischen der Anfrage q und einem Dokument d wird dann durch den Kosinus des Winkels zwischen diesen Vektoren de niert.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.3: Vektorraum Modell

Analog zu De nition 3.1.7 lassen sich Ahnlichkeiten zwischen Dokumenten, sim(di; dj ), und Anfragen, sim(qi; qj ), de nieren.

Vektorraum Modelle haben den Nachteil, dass als Grundlage der Abbildung der Dokumente oder Anfragen eine endliche Termmenge oft unausweichlich ist. Dies ist aber nicht in allen Systemen sofort gegeben bzw. der Austausch dieser Terminformationen (den weiteren Teilnehmern muss bekannt gemacht werden, welche Terme lokal vorhanden sind, ein einzelner Nutzer muss demnach eine globale Sicht auf das System haben) ist sehr komplex.

3.3.3 Das Probabilistische Modell

Ein Hauptziel des Information Retrieval liegt in der Bestimmung der Wahr- scheinlichkeit, ob ein Dokument fur eine Anfrage relevant ist oder nicht. Rele- vanz ist hier eine Beziehung zwischen einem Dokument d und dem Informations- bedarf eines Nutzers, beschrieben durch eine Anfrage q. Falls der Nutzer das Dokument fur seine Anfrage akzeptiert, so ist das Dokument relevant. Die Rele- vanz wird mathematisch ausgedruckt durch die Wahrscheinlichkeit P(Rjqi; dj ).

Als ein Vertreter dieses Modells gilt das Okapi Modell [Hust04]. Jedem Term ti eines Dokumentes wird ein Termgewicht zugewiesen, das fur Terme, die in vielen relevanten- und wenig nicht relevanten Dokumenten auftreten, gro ist:

Abbildung in dieser Leseprobe nicht enthalten

Da die Einteilung der Dokumente in relevante und nicht relevante sehr aufwandig ist, nden probabilistische Modelle kaum Einsatz in der Praxis.

3.4 Informationsangebot durch invertierte Listen und weitere Indexierungsverfahren in PANs

Alle bisher vorgestellten Modelle basieren auf der Tatsache, dass bekannt sein muss, welche Terme in welchen Dokumenten vorkommen. Diese Informationen mussen aber auch verwaltet werden, bzw. den einzelnen Teilnehmern eines Peerto-Peer Netzes zur Verfugung gestellt werden.

[...]