Projekt: Indexing and Compressing the Textual Web

Voraussetzungen

  • Gute Programmierkenntnisse
  • Interesse an Algorithmen und Datenstrukturen

Ziele

Web-Suchmaschinen bestehen aus mehreren Komponenten.

  1. Crawler: Dieses Programm lädt Seiten und Dokumente rekursiv aus dem Netz und speichert sie in einer Datenbank ab.
  2. Index: Um Suchbegriffe schnell in den Dokumenten zu finden, wird ein Index für die Dokumente in der Datenbank angelegt. Dabei werden die Dokumente gleichzeitig komprimiert. Hier gibt es verschiedene Ansätze. Der wohl beliebteste ist das Benutzen von sog. Inverted Indexes.
    Im Projekt sollen stattdessen neue Indexdatenstrukturen verwendet werden. 
  3. Ranking Algorithmen: Um die Relevanz eines Dokumentes bezüglich eines Suchbegriffs gegenüber anderen Dokumenten zu berechnen, werden Ranking Algorithmen eingesetzt. Beispiele sind etwa die Okapi BM25-Funktion oder der PageRank(tm), der bei Google (mit)eingesetzt wird.



Ziel des Praktikums ist es, eine kleine Suchmaschine zu schrieben, die alle Komponenten implementiert und Suchanfragen effizient beantwortet.

Themen

Die Themen sollen - je nach Umfang - alleine oder in Gruppen bis zu drei Studierenden bearbeitet werden. Die Themen stammen aus den Bereichen 1.-3. des vorherigen Absatzes.


Verantwortlich

Prof. Dr. Enno Ohlebusch

 

Termin

Vorbesprechung am 11.04.2011 um 16:00 Uhr im Raum O27/531.