Supervisor(s)

Student

Related projects

HyREX
Hyper-media Retrieval Engine for XML

Finished

2004-03

Task description

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 = K1 or ...or Kn ,
wobei die Kis Basiserereignisse oder Konjunktionen solcher Ereignisse darstellen. Dann ergibt sich die zugehörige Wahrscheinlichkeit als alternierende Summe der Wahrscheinlichkeiten von Kombinationen der Kis.

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.