Ähnlichkeitssuche in großen Datenbanken
Dies ist eine Vorabversion der LV-Website. Die enthaltenen Informationen können sich bis zum Start der Lehrveranstaltungen (VO+PS) ändern!
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] | |
| 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.
Das Buch ist über die Bibliothek der Universität Salzburg online zugänglich.
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 Aufgabestellungen werden im Proseminar ausführlich besprochen.
Aufgabenstellungen
| Aufgabe | Abgabetermin | Aufgabenstellung | ||
|---|---|---|---|---|
| 1. Implementation AllPairs | 12.12.2018, 23:55 | [PDF] | ||
| 2. Implementation Weighted AllPairs | 19.02.2019, 23:55 | [PDF] |
Terminübersicht
| Datum | Thema | |||
|---|---|---|---|---|
| 10.10.2018 | --- | --- | ||
| 17.10.2018 | AllPairs Session 1 | [PDF] | ||
| 24.10.2018 | --- | --- | ||
| 31.10.2018 | AllPairs Session 2 | [PDF] | ||
| 07.11.2018 | AllPairs On-Demand Session | --- | ||
| 14.11.2018 | AllPairs On-Demand Session | --- | ||
| 21.11.2018 | AllPairs On-Demand Session | --- | ||
| 28.11.2018 | AllPairs On-Demand Session | --- | ||
| 05.12.2018 | --- | --- | ||
| 12.12.2018 | AllPairs On-Demand Session | --- | ||
| 19.12.2018 | Weighted AllPairs Session 1 | [PDF] | ||
| 09.01.2019 | Weighted AllPairs On-Demand Session | --- | ||
| 16.01.2019 | Weighted AllPairs On-Demand Session | --- | ||
| 23.01.2019 | Weighted AllPairs On-Demand Session | --- | ||
| 30.01.2019 | Weighted AllPairs On-Demand Session | --- |
Q&A
Dieses Semester besteht die Möglichkeit Fragen über den Slack-Channel #ssdb zu stellen. Dies ist der bevorzugte Weg für die Kommunikation mit dem LV-Leiter außerhalb des Proseminars. Studierende können sich für den Channel #ssdb anmelden und zur Diskussion beitragen.
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 genügt.
Sollten Komplikationen auftreten, wie nicht-vorhandene Libraries am Abgabesystem, können diese gegebenfalls auf Anfrage nachinstalliert werden.
Bewertung
Die folgenden Kriterien werden zur Bewertung der Abgaben herangezogen:- Korrektheit: 2 Punkte
- Indexstruktur (Hash table vs. Array): 1 Punkt
- Caching (eqoverlap, Prefixlängen - Bonus): 1 Punkt (nur Aufgabe 1)
- Filter (Length Filter, Start im Index): 2 Punkte
- Verifikation (Fortsetzung bei Overlap): 1 Punkt
- Overall Code Quality: 2 Punkte
| Punkte | Note | |
|---|---|---|
| > 10.5 | 1 | |
| (8.5, 10.5] | 2 | |
| (6.5, 8.5] | 3 | |
| (4.5, 6.5] | 4 | |
| < 4.5 | 5 |