Zusammenfassung

In dieser Arbeit werden Schnittstellen f ur mobile Endger ate entwickelt, um kontextbezogene Anfragen in ad-hoc Netzwerken (oine Betrieb) sowie per Client-Server Architektur (online Betrieb) umzusetzen. M oglichkeiten 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  uberpr uft werden soll. Schl usselw orter

ad-hoc, ad-hoc Routing, Bloomlter, Indexierung, Information-Retrieval, invertierte Listen, IR-Modelle, Peer-to-Peer Abstract

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

ad-hoc, ad-hoc routing, bloomlter, indexing, information-retrieval, inverted- lists, IR-model, peer-to-peer

Inhaltsverzeichnis

1  Einleitung  7

1.1  Motivation  7

1.2  Aufbau der Arbeit  8

2  Einordnung der Aufgabenstellung in bestehende Netzwerktopologien  11

2.1  Private Area Networks  11

2.2  ad-hoc Netzwerke  11

2.2.1  Strukturiertheit  11

2.2.2  Hierachiegrad  12

2.2.3  Kopplungsgrad  12

2.2.4  Ergebnisse  13

3  Informationsverwaltung  15

3.1  Indexierung in Datenbanksystemen  15

3.2  Grundlagen des Information-Retrieval  16

3.3  Standard Modelle des Information-Retrieval  19

3.3.1  Das Boolesche Modell  19

3.3.2  Das Vektorraum Modell  21

3.3.3  Das Probabilistische Modell  24

3.4  Informationsangebot durch invertierte Listen und weitere Inde-  

xierungsverfahren  in PANs  24

3.4.1  Invertierte Listen  25

Tries   29

Patricia  B aume  30

Pr  ax B aume  31

Index  Fabric  31

3.4.2  Bloomlter  34

4  Informationsbeschaung  37

4.1  ad-hoc Routing  37

4.1.1  Anforderungen mobiler ad-hoc Netzwerke  37

4.1.2  Routing-Verfahren  38

Link  -State  38

Distance  -Vector  38

Proactive   39

Reactive   39

Topologiebasiert   40

Positionsbasiert   40

3

Inhaltsverzeichnis

Hybrid   40

4.1.3  Routing Algorithmen  41

4.1.4  Replikation  41

Ziele  der Replikation  41

Replikationsm  oglichkeiten  42

Datentypen   43

4.1.5  Fazit  44

4.2  Anfrageverarbeitung kontextbezogener Daten  44

4.2.1  Positionierungsdienste  44

4.2.2  Verwaltung von Kontextinformationen in Nutzerprolen  45

5  Konzeption eines Prototypen  47

5.1  Zielsetzung  47

5.1.1  Grenzen des Tourismusszenarios  47

5.1.2  Initiierung eines Private Area Networks  47

5.1.3  Schnittstellen zur oine/online Kommunikation  48

5.2  IMSY - ein System zum intelligenten Datenaustausch in Private  

Area  Networks  48

5.2.1  Kernkomponenten von IMSY  48

5.3  Suche nach- und P ege von Informationen  51

5.4  Indexierung von Objekten im IMSY System  52

5.4.1  Beschreibung der Objekte anhand von Metadaten  52

5.4.2  invertierte Listen zur Speicherung der Metadaten  53

5.4.3  alternative Speicherungstechniken  53

spektraler  Bloomlter ohne Komprimierung  55

spektraler  Blommlter mit Komprimierung  55

5.5  Datenaustausch im IMSY System  59

5.5.1  Eintritt eines Knotens in das Private Area Network  59

5.5.2  Routen von Objekten  60

5.5.3  Replikation  60

6  Prototyprealisierung  61

6.1  Indexierung  61

6.1.1  Datenbankmodell zur Speicherung von Metadaten  61

6.1.2  lokale Indexierung  61

6.1.3  globale Indexierung  62

6.1.4  Hardwarprole  63

6.2  Suche nach Informationen  63

6.2.1  Schnittstellenbeschreibungen  63

6.2.2  Ranking  64

6.3  ad-hoc Netzwerke mit Bluetooth  64

6.3.1  Obex Protokoll  65

6.3.2  Realisierung eines Bluetooth ad-hoc Netzes in IMSY  65

Bluetooth  Programmierschnittstelle  65

Umsetzung  der Bluetooth Funktionalit aten  66

Auswertung  der Obex Nachrichten  67

6.4  Zusammenspiel der einzelnen Module  68

4

Inhaltsverzeichnis

7  Schlussbetrachtungen  73

7.1  Ergebnisse  73

7.2  Ausblick  73

Abbildungsverzeichnis   75

Tabellenverzeichnis 77   

Literaturverzeichnis   79

A  Anhang  83

A.1  Peer-to-Peer Netzwerke  83

A.2  DSR und AODV  85

A.2.1  Dynamic Source Routing (DSR)  85

A.2.2  Ad-hoc On-Demand Vector Routing (AODV)  87

A.3  Bluetooth Grundlagen zur Realisierung eine P2P Netzwerkes  90

A.3.1  technische Grundlagen  90

A.3.2  Verbindungsaufbau  90

A.3.3  Piconetze  91

A.3.4  Scatternetze  93

5

Inhaltsverzeichnis

6

1 Einleitung

Mobilit at hat in den letzten Jahren sehr an Bedeutung gewonnen. Insbesondere in der Informationstechnologie dienen Mobiltelefone oder PDAs als Wissenquelle in allen Lebenslagen, an jedem Ort und zu jeder Zeit. Der heutige Stand der Technik erm oglicht es, Anwendungen f ur diese Ger ate f ur 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 (Private Area Networks bzw. Personal Area Networks im Folgenden auch PANs ¹ genannt) betrachtet. Ein Tourist m ochte  uber eine Attraktion m oglichst genaue Informationen erlangen. Nicht immer stehen ihm diese sofort zur Verf ugung. 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 M oglichkeiten des Wissensaustausches dieses Szenarios aufzuzeigen und prototypisch mittels Bluetooth zu realisieren. Im Mittelpunkt der Betrachtungen stehen dabei Themen wie:

Informationsverwaltung:

Welche M oglichkeiten gibt es, Daten ezient auf mobilen Ger aten zu verwalten?

Im Vordergrund der Betrachtungen stehen hier vor allem Datenbanksowie Information Retrieval Techniken wie z.B. invertierte Listen und Bloomlter als Grundlage der Indexierung lokaler Datenbest ande.

Informationsbereitstellung in PANs:

Welche M oglichkeiten gibt es, Nutzern eines Private Area Networks vor-handene Daten zug anglich zu machen?

Aufbauend auf Prinzipien der Informationsverwaltung werden hier Bloomlter erneut aufgegrien. Spektrale Bloomlter (vgl. 3.4.2) dienen der lokalen Indexierung des Datenbestandes sowie der Vorlterung von Suchanfragen. Durch Mischvorg ange lokaler Bloomlter mit eingehenden Infor-

¹ Der Begri des PANs soll hier nur als Synonym eines Netzwerkes im Nahbereich aufgegrien werden. Aspekete der Kommunikationstechnologie, wie z.B. Sicherheit in solchen Netzwerken, werden in dieser Arbeit nicht n aher betrachtet, da sie  uber den Rahmen der Aufgabenstellung hinausgehen.

7

1 Einleitung

mationen wird eine globale Sicht des Netzwerk Datenbestandes erzeugt, die im folgenden Proze die Grundlage der Informationssuche ist.

Informationsbeschaung, - erg anzung in PANs:

Wie k onnen kontextbezogene Daten durch Suchanfragen in PANs gefunden bzw. bestehende Daten erg anzt werden?

Schwerpunkt dieses Abschnittes ist die Konzeption einer Schnittstelle zur kontextabh angigen Suche innerhalb eines Private Area Networks. Kontextabh angig bedeutet hier in erster Linie die Einbeziehung hardwarespezischer Gegebenheiten des mobilen Endger ates. Weitere Kontextspeziaktionen werden im Kapitel 4.2 behandelt.

Wird das Problem der Informationssuche innerhalb eine PANs auf den Scanbereich des Endger ates begrenzt, so k onnen Probleme des Routings auen vor gelassen werden. Das Kapitel des ad-hoc Routing wird in dieser Arbeit einf uhrend behandelt, um m ogliche Strategien f ur eine Erweiterung der zu entwickelnen L osung vorzustellen und zu bewerten.

Informationsreplikation:

Wie k onnen Daten innerhalb eines Private Area Networks kontinuierlich zur Verf ugung gestellt, bzw. wie kann der Zugri auf Informationen beschleunigt werden?

Dieser Abschnitt gibt einen Ausblick auf m ogliche Replikationsstrategien, die eine schnellere Suche nach Informationen zur Folge haben k onnen.

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 betrachtet, um eine Einordnung der Problemstellung in bestehende Entwicklungen zu erm oglichen und gegebenfalls Ans atze f ur die Konzeption des Prototyps zu gewinnen.

In Kapitel 3 werden Techniken zur ezienten 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 schnellstm oglich und auf dem k urzesten Wege zu nden, um die Netzlast des Private Area Networks so gering wie m oglich zu halten. Ausgehend von den Indexierungsstrategien werden in Kapitel 4 die Probleme des Routings und der Replikation von Informationen betrachtet.Es werden Konzeptionsvorschl age entwickelt, die teilweise im Prototypen realisiert werden oder aber in einer weiteren Arbeit erg anzend hinzugef ugt werden k onnen. Weiterhin 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-"

8

1.2 Aufbau der Arbeit

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 L osungsans atze zur Realisierung eines Bluetooth ad-hoc Netzwerkes er ortert.

Abschlieend gibt Kapitel 7 einen Ausblick auf m ogliche Erweiterungen der vorgeschlagenen Realisierungkonzepte. Weiterhin werden Alternativm oglichkeiten aufgezeigt.

9

1 Einleitung

10

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 ben otigt werden. Der Daten- bzw. Informationsaustausch erfolgt lediglich zwischen den Netzwerkteilnehmern. Wird als Protokoll zur Daten ubertragung 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 k onnen sich z.B. Mobiltelefone, PDAs und Noteboks verst andigen, um gegenseitig Ressourcen und Dienste zu nutzen oder Daten zur Verf ugung zu stellen. Die Kommunikation zwischen mobilen Endger aten erfolgt zum Groteil im adhoc Modus.

2.2 ad-hoc Netzwerke

Ad-hoc Netzwerke werden dadurch charakterisiert, dass sie nicht durch eine gleichbleibende, permanent vorhande Infrastruktur deniert werden. Teilnehmer eines ad-hoc Netzwerkes k onnen 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 bezeichnet) dieses Netzwerkes beschreibt. Die Verbindungsqualit at zweier Knoten des MANETs kann beeintr achtigt werden, da durch die st andige 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 Daten ubertragung zustande kommt.

2.2.1 Strukturiertheit

In strukturierten P2P Systemen verwalten einzelne Peers globale Informationen (z.B Indexeintr age). Dadurch ist eine zielgerichtete Suche m oglich. (vergleiche Freenet\)

"

11

2 Einordnung der Aufgabenstellung in bestehende Netzwerktopologien

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 m oglich. (vergleiche Napster\)

"

Dezentrales (verteiltes) Modell:

Im Gegensatz zum zentralisierten Modell werden Index-Eintr age im dezentralen Modell verteilt organisiert. Teilnehmer agieren direkt unterein-ander.

Hierachisches Modell:

Eine Mischform der bisher dargelegten Modelle ist das hierarchische Modell. Super-Peers verwalten hier die globalen Indixes. Bei einem Ausfall einzelner Super-Peers sind Suchen innerhalb des System teilweise noch m oglich. Super-Peers sollten  uber einen l angeren Zeitraum zur Verf ugung stehen.

2.2.3 Kopplungsgrad

In stark gekoppelten P2P Systemen geh oren die Teilnehmer immer zu einer Gruppe. Den Knoten wird beim Eintritt eine eindeutige Identikation zugewiesen. In lose gekoppelten Systemen kann sich die logische Adresse  andern.

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

Tabelle 2.1: P2P Systeme

12

2.2 ad-hoc Netzwerke

2.2.4 Ergebnisse

Im vorgestellten Szenario agieren die Teilnehmer direkt miteinander. Jeder Knoten kann dem Netzwerk st andig beitreten oder dieses verlassen. Demnach kann es keine Super-Peers im System geben. Um eine schnelle Suche nach Informationen zu erm oglichen, sollen Peers eine globale Sicht auf das Netzwerk erhalten. Knoten werden im System anhand ihres Bluetooth Ger ates identizert. Werden diese Kriterien verwendet, so handelt es sich bei dem zu entwickelnen System um ein strukturiertes, dezentrales und stark gekoppeltes Modell. Anhang A stellt einige Vertreter vergleichend vor, um diesen Sachverhalt zu verdeutlichen.

13

2 Einordnung der Aufgabenstellung in bestehende Netzwerktopologien

14

3 Informationsverwaltung

Datenbanken bieten in Hinblick auf die Verwaltung kontextbezogener Informationen wesentliche Vorteile. Daten lassen sich strukturiert unter Vermeidung von Redundanzen unab angig 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 k onnen Knoten verschiedene Informationen lokal verwalten. Um die Suche zu vereinfachen bzw. den Zugri auf Daten zu beschleunigen, ist es von N oten, Daten zu indexieren.

3.1 Indexierung in Datenbanksystemen

Datenbanksysteme unterst utzen sogenannte Zugrispfade\. Zugrispfade be-"

zeichnen Zugristrukturen, die  uber grundlegende Dateiorganisationsformen hinausgehen.

Ein Prim arindex kann die Dateiorganisationsform, z.B. eine sortierte

Speicherung, der internen Relation ausnutzen. Somit k onnen schnellere Zugrie erm oglicht werden.

Jeder weitere Zugripfad auf eine interne Relation wird als Sekund arindex bezeichnet

(vergleiche [SHS05])

Indexeintr age haben in der Regel die Form (K; K£). K bezeichnet hier den Wert des Prim ar- oder Sekund arschl ussels. F ur K£ sind folgende Formen m oglich:

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

K£ ist Adresse eines internen Tupels: Hierduch k onnen Prim arschl ussel

(durch einmaliges auftreten des Wertes K) oder auch Sekund arschl ussel (mehrere Eintr age der Form (K; K£ 1 ); :::; (K; K£ n )) unterst utzt werden.

K£ ist eine Liste von Tupeladressen: Hierdurch werden vor allem Se-

kund arschl ussel unterst utzt. Die dynamsiche L ange eines solchen Indexeintrages erschwert aber die Verwaltung dieser Eintr age, da kein fester Speicherbereich f ur derartige Indexeintr age vergeben werden kann.

15

3 Informationsverwaltung

Weiterhin spricht man bei der Verwendung von Datenbanken oft auch von einem d unnbesetzten-/dichtbesetzen Index\ (Anzahl der Datens atze die auch einen

"

Indexeintrag haben)

d unnbesetzt: nicht alle Datens atze

dichtbesetzt : alle Datens atze

oder auch von einem geclusterterten-/nicht-geclusterten Index\ (Organisation

"

des Index in Bezug auf die Organisationsform der internen Realtion). Ausf uhrliche und weitergehende Informationen dazu k onnen [SHS05] entnommen werden.

3.2 Grundlagen des Information-Retrieval

Unabh angig von den Indexierungsm oglichkeiten innerhalb einer Datenbankmanagmentsystems wurden insbesondere im Gebiet des Information Retrieval

"

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

Abbildung 3.1: Information-Retrieval Prozess [Kuropka04]

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

16

3.2 Grundlagen des Information-Retrieval

diese Dokumente durch ein entsprechendes Modell der Suche innerhalb der Nutzergruppe (lokal und global) zur Verf ugung zu stellen. In einigen Systemen ist es nach einem Suchprozess m oglich, Ergebnisse einer Suchanfrage zu bewerten bzw. die Dokumente selbst abzu andern. Diese  Anderungen k onnen das Ergebnis neuer Anfragen beein ussen.

Im Wesentlichen werden folgende IR-Modelle unterschieden:

Abbildung 3.2: Information-Retrieval Modelle [Kuropka04]

Mengentheoretische Modelle bilden Dokumente auf Mengen ab und Ahnlichkeitsuntersuchungen anhand von Mengenoperation wie ‘; ’ f uhren  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: Dn ¡ ~

Kosinusma R n =

Probalistische Modelle betrachten die Wahrscheinlichkeit, dass ein Do-kument relevant ist f ur 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 Wahrscheinlichkeiten:

{ P(Rj ~ d n ): Dokument d n ist relevant. { P(Rj

~ 17

3 Informationsverwaltung

Modelle ohne Terminterdependenzen betrachten Terme als orthogo-

nale Einheiten (unabh angig voneinander)

Modelle mit Terminterdependenzen hingegen gehen von einer Orthogonalit at der Terme aus. Modelle mit Immanenter Terminterdependenz 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 deniert werden.

Speziell f ur 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 N utzlichkeit eines Dokumentes in Bezug auf die Anfrage wird anhand eines Ranking Wertes beschrieben.

Denition 3.2.1 Ein Dokument bezeichnet ein Multiset von W ortern. Beim

IR spielt die Organisation der Worte in S atze oder Kapitel meist keine Rolle.

Dokumente werden im Folgenden mit d oder d i gekennzeichnet. Die Menge aller Dokumente wird durch D beschrieben.

Denition 3.2.2 Eine Anfrage bezeichnet ebenfalls ein Multiset von W ortern

unter Vernachl assigung der Organisation der Worte.

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

Denition 3.2.3 Terme sind Transformationsergebnisse von W orten der Do-

kumente oder Anfragen. Sie dienen der Textsuche als Ausgangsbasis.

Terme werden durch t oder t i repr asentiert. Die Menge alle Terme erh alt die Bezeichnung T.

Denition 3.2.4 Transformationen bezeichnen Prozesse oder Abbildungen ( D A T ) des Information Retrievals, bei denen W orter eines Dokumentes auf Terme durch Verfahren wie Stammwortreduktion oder Worttrennung abgebildet werden.

Denition 3.2.5 Ranking Funktionen verfolgen das Ziel, Dokumente in ei-

ner geordneten Liste bez uglich 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 Termh augkeiten oder Termpositionen den Ranking Wertes eines Dokumentes zu bestimmen.

In mobilen Umgebungen kann der Kontext des Nutzers, z.B. die lokale Position, die Zugrisgeschwindigkeit des mobilen Endger ates auf das Netzwerk oder

18

3.3 Standard Modelle des Information-Retrieval

die Darstellungm oglichkeiten des Endger ates, ausschlaggebend f ur 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 ausf uhrlicheren 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 Termen betrachtet. Diese Mengen werden durch boolesche Operatoren wie and, or oder not verkn upft. Es werden nun die Dokumente als Ergebnis einer Anfrage geliefert, die die Terme der Anfrage in deren Kombination der Verkn upfung (Operatoren) enthalten. Obwohl dieses Modell durch seine Einfachheit sehr efzient zu implemntieren ist, weit es doch einige entscheidene Nachteile auf: Die Terme eines Dokumentes werden nicht gewichtet. Insofern ist ein Do-kument, das durch einen Term t A indexiert wird, gleich relevant in Bezug auf eine Anfrage t A or t B , wie ein Dokument mit der Indexierung t B .

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 umzusetzen versucht.

Das Standard Modell erlaubt es nicht, Terme einer Anfrage zu gewichten.

Demnach kann keine Entscheidung getroen werden, ob ein Term t A einer Anfrage relevanter als ein Term t B dieser Anfrage ist.

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

rank(d k ; t 1 and t 2 ) = MIN(w k1 ; w k2 ) w ki = Gewichtung eines Termes t ⁱ im Dokument d k

rank(d k ; t 1 or t 2 ) = MAX(w k1 ; w k2 )

Einfache Fuzzy-Mengen Operatoren sind auf nur zwei Terme beschr ankt. Hieraus ergibt sich ein Nachteil der anhand des folgenden Beispiels erl autert werden soll:

d 1 = f(Apfel; 0:2); (Birne; 0:2)g

Dies ergibt mathematisch folgende Aussage:

rank(d 1 ; q) = MIN(0:2; 0:2) = 0:2; rank(d 2 ; q) = MIN(0:2; 0:8) = 0:2

19