Abgeschlossene Diplomarbeit: Effiziente Wahrscheinlichkeitsberechnung für Ereignisausdrücke

Betreuer

• Dipl.-Inform. Henrik Nottelmann
• Prof. Dr.-Ing. Norbert Fuhr

Bearbeiter

• Twain Hoffmann

Verwandte Projekte

HyREX

Hyper-media Retrieval Engine for XML

Abgabetermin

2004-03

Aufgabenstellung

HyREX ist eine XML-Retrievalengine. Die Berechnung von Wahrscheinlichkeiten in HyREX erfolgt über Ereignisausdrücke, die die Abhängigkeit eines Antwortelements von den (probabilistischen) Basisereignissen (Erfüllung der einzelnen Fragebedingungen durch das aktuelle Element) in Form eines booleschen Ereignisausdrucks beschreiben.

Bisher erfolgt die Berechnung der zugehörigen Wahrscheinlichkeit mit Hilfe der Siebformel (oder Einschluß-Ausschluß-Formel). Dabei muss der Ereignisausdruck zunächst in die disjunktive Normalform überführt werden:
e = K₁ or ...or K_n ,
wobei die K_is Basiserereignisse oder Konjunktionen solcher Ereignisse darstellen. Dann ergibt sich die zugehörige Wahrscheinlichkeit als alternierende Summe der Wahrscheinlichkeiten von Kombinationen der K_is.

Die Siebformel hat exponentielle Komplexität. Im Rahmen dieser Arbeit soll nun eine alternative Strategie realisiert werden:

Modifiziert man die disjunktive Normalform so, dass die einzelnen Minterme zueinander disjunkt sind (z.B.\ durch Bildung der vollständigen disjunktiven Normalform), so kan man anstelle der Siebformel einfach die Summe der Wahrscheinlichkeiten der einzelnen Konjunktionen berechnen. Dabei ist auch eine partielle Auswertung möglich, d.h.\ man berechnet Teilsummen, die jeweils bessere untere Schranken für die gesuchte Wahrscheinlichkeit bilden. Durch die Anwendung des Verfahrens auf die Gegenwahrscheinlichkeit erhält man jeweils bessere obere Schranken, was für das Ranking in IR-Anwendungen relevant ist.

Im Rahmen dieser Arbeit soll die neue Strategie implementiert und in HyREX integriert werden. Ferner soll ein Verfahren zur Auswahl der jeweils effizienteren Strategie entwickelt und integriert werden. Die Realisierung soll anhand von Testdaten auf ihre Laufzeiteffizienz hin untersucht werden.