Vorlesung Information Retrieval und Datenbanken

Alexander Hinneburg

• Aktuelles
• Beschreibung
• Termine, Übungen, Material

Aktuelles

• Die Vorlesung beginnt am Do. 7.4., die erste Übung findet am Mo. 11.4. statt.

Inhalte

Wie funktioniert eine Suchmaschine? Wie werden unstrukturierte Texte (Webseiten) aufbereitet, um effizient relevante Informationen zu finden? Ist das Problem seit der Existenz von Google nicht schon gelöst?

Suchen in großen Informationsbeständen tritt in vielen Anwendungsbereichen auf. Die Vorlesung wird in die folgenden Bereiche einführen:

• Suche in Texten
• Suche in Multimedia-Daten
• Suche in Webseiten

Der erste Bereich beschäftigt sich mit klassischem Information Retrieval. Es werden verschiedene Modelle und Konzepte vorgestellt, um Texte zu repräsentieren und sinnvoll zu durchsuchen. Besonders vertieft werden das Vektorraum-Modell und Latent Semantic Indexing. Weiterhin werden Methoden zur Evaluation, Anfrage und Textverarbeitung sowie zur Implementierung diskutiert.

Der zweiten Teil geht auf die erweiterten Anforderungen bei der Verarbeitung von Multimedia-Daten ein. Der Schwerpunkt wird hier auf neuen Indexstrukturen liegen, welche die Suchoperationen auf Multimedia-Daten unterstützen.

Information Retrieval ist erst durch den Erfolg des WWW zu einer Schlüsseltechnologie geworden. In Webseiten sind neben den Textinformationen auch Links enthalten. Es werden Verfahren vorgestellt, die speziell die Struktur der Verbindungen analysieren und zum Ordnen der Suchergebnisse nutzen. Der Schwerpunkt wird auf den Methoden Random Walk (Google) und HITS liegen.

Termine, Übungen, Material

1. alle Folien
2. Vorlesung 07. 04.: Einführung (Folien), IR Modelle (Folien, rel. Seiten aus dem Buch)
   Übung 11.4.: Blatt 1, Musterlösung 1
3. Vorlesung 14. 04.: IR Modelle (Folien)
   Übung 18.4.: Blatt 2, cystis.txt, Musterlösung zu 2.2
4. Vorlesung 21. 04.: Evaluierung (Folien)
   Übung 25.4.
5. Vorlesung 28. 04.: Anfrage Sprachen & Anfrage Operationen (Folien)
   Übung 2.5.: Blatt 3, Musterlösung zu 3.1
6. Vorlesung 05. 05.: Christi Himmelfahrt -- keine Vorlesung
   Übung 9.5.
7. Vorlesung 12. 05.: Text Repräsentationen & Text Operationen (Folien)
   • Weitere Erklärung zum Zipfschen Gesetz
   23.5. Pfingstmontag
8. Vorlesung 19. 05.: Text Indexing 1 (Folien)
   Übung 23.5.: Blatt 4, Gutenberg Texte (26 MB)
9. Vorlesung 26. 05.: Text Indexing 2
   Übung 30.5.: Blatt 5, Konzepte (AH), Start Marker, preprocessing.sh
10. Vorlesung 09. 06.: Multimedia IR Indexing 1 (Folien)
    Übung 13.6.: Blatt 6, extrahierte Dokumente der Gutenberg-Texte: gutDok.zip (30 MB)
    • A Gentle Introduction to the FFT
    • Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331
    • Berchtold S., Keim D. A., Kriegel H.-P.: The X-Tree: An Index Structure for High-Dimensional Data, Proc. 22nd Int. Conf. on Very Large Data Bases (VLDB'96), Bombay, India, 1996, pp. 28-39.
    • Roger Weber, Hans-Jörg Schek, Stephen Blott: A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces. VLDB 1998: 194-205
    • Implementierungen zur R-Bäumen finden unter: www.rtreeportal.org
11. Vorlesung 16. 06.: Multimedia IR Indexing 2, (Folien)
    Übung 20.6.: Blatt 7, Invertiertes File der Gutenberg Texte (10 MB), die Datei all_sorted.txt enthält die gestemmten Wörter ohne Stoppwörter lexikographisch sortiert. An jeden Term ist mit _ zuerst die Dok-ID (Zeile in file_list.txt) und dann die Häufigkeit angehängt. Musterlösung zu 7.1 und 7.2, Musterlösung zu 7.3
    • Aristides Gionis, Piotr Indyk, Rajeev Motwani: Similarity Search in High Dimensions via Hashing. VLDB 1999: 518-529
    • LSH Erweiterungen und Implementierung
    • Paolo Ciaccia, Marco Patella, Pavel Zezula: M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. VLDB 1997: 426-435
    • Das M-Tree Projekt mit Erweiterungen und Implementationen
12. Vorlesung 23. 06.: Web IR: Kompression des Webgraphen (Folien)
    Übung 27.6.: Dokument Clustering (Folien)
    • Das Webgraph Projekt mit Daten, Erweiterungen und Implementationen
13. Vorlesung 30. 06.: Web IR: Ranking (Folien, Notizen)
    Übung 4.7.: Blatt 12
    • Link zur Originalseite des Kurses Algorithms for Large Data Sets
14. Vorlesung 07. 07.: Web IR 2
    Übung 11.7.: Wiederholung und Fragen
15. 14. 07.: Klausur