Planung HS 2023

Link zum Modul: Information Retrieval & Spatial Queries - Wie rufen wir Daten effizient ab? Wie funktioniert das bei sehr grossen Datenmengen? Wie, wenn die Suchanfrage eine geometrische Grösse ist?

Gruppe B

14.08.2023 (L1)

• in Gruppe zusammensitzen
• selbständig arbeiten, da LP beschäftigt
• Aufgaben 1/2a/2b
• HA: Auftrag fertig

21.08.2023 (L2)

• Aufgaben 1&2 besprechen
• Range queries (Aufgaben 3) besprechen und lösen
• ev. preview auf Spatial Queries / Quadtrees

28.08.2023 (L3)

04.09.2023 (L4)

11.09.2023 (L5)

18.09.2023 (L6)

• Basic Binary Search Tree (BST) zum laufen kriegen Notebook
• Übertragen auf 140k Dataset von http://download.geonames.org/export/dump/ (Cities500)
• HA: github repo mit BST, das im 140k Dataset in weniger als 0.1s eine Range-Query nach Bevölkerungszahl ausführt.
  • Teilen mit hof@ bis Freitag.

25.09.2023 (L7)

• KD-Tree: Theorie, Life-Coding Session

02.10.2023 (L8)

• KD-Tree auf dem mittleren oder grossen Dataset zum laufen bringen
• Optimierungen
  • Metriken: Tiefe des Trees, Laufzeit, Speicherbedarf
    1. Schreibe eine Funktion tree_height(node), die rekursiv die maximale Höhe des Baums berechnet.
    2. Wie viel grösser ist die Höhe im Vergleich zum Optimum? Ist das ein Problem?
    3. Verwende die %time und %timeit iPython magics, um die Laufzeit zu messen (Baum bauen, Query)
  • Wie beeinflusst der Median-Algorithmus die Tiefe und Laufzeit?
    1. Entwickle Strategien, um eine geringere Tiefe zu erreichen, und teste sie aus.
    2. Randomisierung?
    3. Sortieren und Median finden auf jeder Ebene?
  • Speicherbedarf für Build-Tree?

HERBSTFERIEN

23.10.2023 (L9)

• Schritt zurück: wie funktioniert Indexing für Text-Dokumente
  • Query, Retrieval, Ranking
  • Invertierter Index
  • 2 Aufgaben in 04_text_indexing.ipynb lösen

30.10.2023 (L10)

• Text Indexing (Wiederholung):
  • Aufgabe: Indexiere alle Wikipedia-Artikel über Filme von 1985 (387 Artikel, 0.7MB)
    • Die Artikel sind im CSV-Format mit zwei Spalten: Wikipedia URL, Artikeltext (Deutsch)
    • Finde heraus, in welchem epischen Film ein DeLorean-Sportwagen eine Rolle spielt (yup, Sie erleben hier fächerübergreifende Bildung!).
    • Mehr Daten unter https://if.ksr.ch/talit/indexing/
• Ranking
  • Implementiere eine Suche, bei der die Suchresultate die Vereinigung (set.union()) aller Resultate für jeden Term der Query bilden.
  • Die Suche nach Michael Fox gibt eine Vielzahl von Suchresultaten zurück - weshalb?
  • Wir möchten Dokumente, die fox enthalten, höher einstufen, als Dokumente, die michael enthalten, weil zweiteres in viel mehr Dokumenten vorkommt.
  • Enters Inverse Document Frequency (IDF): ein Mass dafür, wie spezifisch ein Term für einen Dokumentenkorpus ist. Grundidee: bei $n$ Dokumenten beträgt die IDF $idf(t) = \frac{n}{countDocs(t)}$, wobei countDocs angibt, wieviele Dokumente den Term $t$ enthalten. Ein Term, der in jedem Dokument vorkommt, hat das Gewicht $1$, ein Term, der maximal spezifisch ist und nur in einem Dokument vorkommt, hat das Gewicht $n$.
    • Erste Aufgabe: Berechne die Liste der Terme und deren Vorkommenshäufigkeit, sortiert nach letzerer.
    • Plotte die Vorkommenshäufigkeit mit pyplot. Was fällt auf?
    • Überlege, welche mathematische Transformation uns helfen könnte, die IDF etwas praktischer zu machen.

Gruppe A

06.11.2023 (L1)

• Range Queries Intro lesen
• Jupyter Notebook in frischem Repository erstellen, Repo mit hof@teilen
• Aufgaben 1/2/3a lösen
• 3b Lösung disktutieren

13.11.2023 (L2)

• Aufgabe 3a
  • Zeit messen (im Notebook) für eine Linearsuche im 140k Dataset.
• Aufgabe 3b: Index-Erstellung
  • Lösung diskutieren
  • Implementieren
  • mit Toydataset testen / Zeit messen
  • mit dem 140k / 12M Dataset
    • wie lange dauert die Index-Erstellung?
    • wie lange dauert der Zugriff
    • Nach wiewielen Zugriffen ist die Index-Erstellung amortisiert (im Vergleich zur Linearsuche)?

20.11.2023 (L3)

• Text Indexing: Aufgaben 1-3

27.11.2023 (L4)

• Text Indexing: Aufgabe 4: Multiple Tokens

04.12.2023 (L5)

• Abschluss Text Indexing: Aufgabe 4: Ranking with IDF

11.12.2023 (L6)

• Zurück zu unserem Geo-Dataset und Spatial Indexing.
• Wir möchten nicht nur nach Text-Werten suchen, die genau übereinstimmen, sondern nach einem Bereich (Range).
• Beispielsweise möchten wir alle Städte finden, die zwischen 10 und 15 Mio Einwohner haben.
• Range queries (Aufgaben 4a & 4b) besprechen und lösen.
• ev. Vorschau auf Binary Search Trees.

18.12.2023 (L7)

• Graph Visualization inkl. Christmas BSTree Challenge

WEIHNACHTSFERIEN

08.01.2024 (L8)

• KD-Tree: Theorie, Life-Coding Session
  • Auf Toy-Dataset implementieren

15.01.2024 (L9)

• KD-Tree auf dem mittleren oder grossen Dataset zum laufen bringen
• Optimierungen
  • Metriken: Tiefe des Trees, Laufzeit, Speicherbedarf
    1. Schreibe eine Funktion tree_height(node), die rekursiv die maximale Höhe des Baums berechnet.
    2. Wie viel grösser ist die Höhe im Vergleich zum Optimum? Ist das ein Problem?
    3. Verwende die %time und %timeit iPython magics, um die Laufzeit zu messen (Baum bauen, Query)
  • Wie beeinflusst der Median-Algorithmus die Tiefe und Laufzeit?
    1. Entwickle Strategien, um eine geringere Tiefe zu erreichen, und teste sie aus.
    2. Randomisierung?
    3. Sortieren und Median finden auf jeder Ebene?
  • Speicherbedarf für Build-Tree?