Ähnlichkeitssuche in großen Datenbanken
News
- Erklärungen zum Prüfungsmodus sind online.
Allgemeines
Die Vorlesung wird im Frontalunterricht abgehalten. Die Folien zur Vorlesung werden jeweils vor Beginn der Vorlesung online gestellt.
Die Bewertung der Vorlesung erfolgt in einer mündlichen oder schriftlichen Prüfung (je nach Zahl der Anmeldungen).
Vorlesungstermine: siehe PlusOnline
Prüfungstermine: werden in PlusOnline bekanntgegeben. Die An- und Abmeldung zur Prüfung ist bis 48 Stunden vor dem Prüfungszeitpunkt möglich. Bei Fernbleiben von einer Prüfung ohne Abmeldung erfolgt eine Sperre gemäß den Satzungen der Universität.
Proseminartermine: siehe PlusOnline
Vorlesung
Folien
Die Folien zur Vorlesung werden spätestens am Vortag der Vorlesung hier veröffentlicht. Jeder Satz Folien bildet eine thematische Einheit und wird in einer oder mehreren Vorlesungen behandelt. Die Folien und die entsprechnenden Erläuterungen und Diskussionen während der Vorlesung sind wesentliche Grundlage für die Vorbereitung zur Prüfung.
| Thema | Folien | ||
|---|---|---|---|
| 1. | General Introduction: Similarity Search, Introductory Example and Demo | [1up] [4up] | |
| 2. | Edit Distance: Definition, Brute Force Algorithm, Dynamic Programming Algorithm, Edit Distance Variants | [1up] [4up] | |
| 2a. | Set Similarity Joins: Set Size Lower and Upper Bounds, Equivalent Overlap, Probing and Indexing Prefix, AllPairs Algorithm | [1up] [4up] | |
| 3. | q-Gram Distance: Approximate String Join, Lower Bound Filtering, Length Filter, q-Gram Count Filter, q-Gram Position Filter, q-Gram Distance, Experiments | [1up] [4up] | |
| 4. | Trees: Tree Definition | [1up] [4up] | |
| 5. | Tree Edit Distance: Definition, Edit Cost, Edit Mapping, Deriving the Recursive Formulas, Dynamic Programming Algorithm, Complexity | [1up] [4up] | |
| 6. | Pruning: Traversal String Lower Bound, Constrained Edit Distance Upper Bound | [1up] [4up] | |
| 7. | Reference Sets: Pruning with Reference Sets | [1up] [4up] | |
| 8. | Binary Branch Distance: Algorithm, Lower Bound Proof, Complexity | [1up] [4up] | |
| 9. | pq-Gram Distance: Algorithm and Lower Bound Theorem | [1up] [4up] | |
Lektüre
Folgendes Buch behandelt mehrere Themen der Vorlesung:
N. Augsten, M. H. Böhlen. Similarity joins in relational database systems.
Synthesis lectures on data management. Morgan Claypool Publishers, 2013.
Prüfung
Die Prüfung zur Vorlesung ist mündlich. Sie erhalten während der Prüfung eine Frage, die zufällig ausgewählt wird. Sie haben 20 Minuten Zeit, die Frage auszuarbeiten und stellen die Antwort in ca. 15 Minuten im Rahmen eines Prüfungsgespräches vor.
Die vorzubereitenden Fragen decken den gesamten Vorlesungsstoff ab und sind zum Teil sehr konkret: Es wird erwartet, dass Sie Beweise führen sowie Algorithmen an Beispielen (die Sie teilweise selbst erfinden müssen) durchrechnen und erklären können.
Während des Prüfungsgespräches werden vertiefende Fragen gestellt um das Verständnis zu prüfen. Nach Bedarf können auch weitere Themen abgefragt werden.
Bewertet werden
- die technische Korrektheit der Antwort,
- der Detailgrad der Antwort, d.h. wie tief-schürfend wurde das Thema behandelt,
- die Vollständigkeit der Antwort, d.h. wurden alle Aspekte berücksichtigt,
- der Gebrauch der passenden Fachterminologie,
- die Fähigkeit, auf vertiefende Fragen einzugehen.
Zur Prüfung können keine Unterlagen verwendet werden.
Die An- und Abmeldung zur Prüfung ist bis 48 Stunden vor dem Prüfungszeitpunkt möglich. Bei Fernbleiben von einer Prüfung ohne Abmeldung erfolgt eine Sperre gemäß den Satzungen der Universität.
Proseminar
Im Proseminar werden Projekte zu aktuellen Forschungsthemen ausgearbeitet. Die Aufgabestellung wird im Proseminar ausführlich besprochen.
| Teilaufgabe | Abgabetermin | |
|---|---|---|
| Task 1: Implementierung von AllPairs | 2017-12-05 | |
| Task 2: Gewichte in AllPairs einbauen |
2018-01-21 (funktionierende Version) 2018-02-07 23:59 (endgültige Version) |
Abgaberichtlinien
- Als Abgabedatei wird ein *.zip-Archiv erwartet.
- Alle Dateien die kompiliert werden müssen liegen direkt im Archiv, zum Beispiel das Makefile oder alle *.java Dateien. D.h. keine Verwendung von selbsterstellten Packages in Java.
- Für C++ ist ein Makefile erforderlich.
- Das Executable muss nach dem Compile-Vorgang AllPairs bzw. AllPairs.class heißen, also die main-Prozedur muss darin liegen. Falls Python verwendet wird, heißt das Executable AllPairs.py.
- Erwarteter Output:
- Zeile 1: Anzahl der gefundenen Paare
- Zeile 2: CPU-Time
Abgabe erfolgt über: abgaben.cosy.sbg.ac.at. Eine Abgabe pro Team ist genügend.
Sollten Komplikationen auftreten, wie nicht-vorhandene Libraries am Abgabesystem, können diese gegebenfalls auf Anfrage nachinstalliert werden.