Ähnlichkeitssuche in großen Datenbanken
News
- Vorlesungsvideos werden auf Blackboard zur Verfügung gestellt.
Allgemeines
Die Vorlesung wird online abgehalten. Videos mit Erkärungen zu den Folien zur Vorlesung werden regelmäßig online gestellt.
Zur Bewertung der Vorlesung ist eine mündlichen Prüfung geplant. Sollte sich eine mündliche Prüfung aufgrund der hohen Ameldezahlen als nicht praktikable herausstellen, kann eine schriftlichen Prüfung abgehalten werden.
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
Fragen und Diskussionen
Für Fragen und Diskussionen zur Vorlesung (auch unter den Studierenden) steht der Slack Channel #ssdb-vo-2020ws (Workspace dbteaching.slack.com) zur Verfügung.
Folien
Die Vorlesung wird online abgehalten. Videos mit Erkärungen zu den Folien zur Vorlesung werden regelmäßig online gestellt.
Jeder Satz Folien bildet eine thematische Einheit und wird in einer oder mehreren Vorlesungen behandelt. Folien, welche noch nicht in der Vorlesung behandelt wurden, können sich noch ändern. Nach der Vorlesung werden nur noch Fehler ausgebessert. Verschiedene Versionen können Sie anhand des Datums auf der Titelseite unterscheiden.
Die Folien und die entsprechenden Erläuterungen und Diskussionen während der Vorlesung sind wesentliche Grundlage für die Vorbereitung zur Prüfung.
ACHTUNG: Als Vorschau werden die Folien der nächsten Einheiten in einer Vorabversion online gestellt. Die finalen Versionen werden zur Verfügung gestellt, wenn das jeweilige Themengebiet in der Vorlesung durchgenommen wird.
| Thema | Folien | ||||||
|---|---|---|---|---|---|---|---|
| 0. | Course Organisation and Demo | [1up] [4up] | |||||
| 1. | Introduction to Similarity Search | [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
Zur Bewertung der Vorlesung ist eine mündlichen Prüfung geplant. Sollte sich eine mündliche Prüfung aufgrund der hohen Ameldezahlen als nicht praktikable herausstellen, kann eine schriftlichen Prüfung abgehalten werden.
Mündliche Prüfung: Die Prüfung dauert ca. 30 Minuten. Die 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.
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 mündlichen 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 wird der praktische Aspekt von Ähnlichkeitsanfragen beleuchtet. Basierend auf mehreren Implementierungsaufgaben werden Konzepte und Optimierungsmethoden von sogenannten Set Similarity Joins ausgearbeitet. Die Aufgabestellungen werden im Proseminar ausführlich besprochen.
Wichtig: Das Proseminar findet in diesem Semester ausschließlich via Videokonferenz statt. Der Link zur Videokonferenz wird allen angemeldeten Studenten per E-Mail zugesandt. Alle Teilnehmer/-innen müssen mit dem entsprechendem Equipement (Kamera, Mikrofon) für die online Lehre ausgestattet sein. Dieser Modus ändert nichts an der Anwesenheitspflicht des Proseminars.
Aufgabenstellungen
| Aufgabe | Abgabetermin | Daten | ||
|---|---|---|---|---|
| Task 1: Nested Loop, Length Filter | 03.11.2020, 23:55 | [Data] | ||
| Task 2: Prefix Filter | 24.11.2020, 23:55 | [Data] | ||
| Task 3: Inverted List Index | 15.12.2020, 23:55 | [Data] | ||
| Task 4: Efficient Verification | 19.01.2021, 23:55 | [Data] |
Terminübersicht
| Datum | Thema | |||
|---|---|---|---|---|
| 01.10.2020 | Introduction | [PDF] | ||
| 08.10.2020 | Set Similarity Queries | [PDF] | ||
| 15.10.2020 | Task 1 | [PDF] | ||
| 22.10.2020 | Task 1 On-Demand Session | --- | ||
| 29.10.2020 | Task 1 On-Demand Session | --- | ||
| 05.11.2020 | Task 2 | [PDF] | ||
| 12.11.2020 | Task 2 On-Demand Session | --- | ||
| 19.11.2020 | Task 2 On-Demand Session | --- | ||
| 26.11.2020 | Task 3 | [PDF] | ||
| 03.12.2020 | Task 3 On-Demand Session | --- | ||
| 10.12.2020 | Task 3 On-Demand Session | --- | ||
| 17.12.2020 | Task 4 | [PDF] | ||
| 07.01.2021 | Task 4 On-Demand Session | --- | ||
| 14.01.2021 | Task 4 On-Demand Session | --- | ||
| 21.01.2021 | Final Session | [PDF] | ||
| 28.01.2021 | --- | --- |
Q&A
Dieses Semester besteht die Möglichkeit Fragen über den Slack-Channel #ssdb-ps-2020ws 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-ps-2020ws anmelden und zur Diskussion beitragen.
Abgaberichtlinien
- Als Abgabedatei wird ein *.zip-Archiv erwartet, welche die Source Code Dateien enthält.
- 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 taskX bzw. taskX.class heißen, also die main-Prozedur muss darin liegen. Falls Python verwendet wird, heißt das Executable taskX.py. X muss an den jeweiligen Task angepasst werden.
-
Erwartete Parameter:
- Parameter 1: Datensatz
- Parameter 2: Threshold
-
Erwarteter Output:
- Zeile 1: Anzahl der gefundenen Paare
- Zeile 2: CPU-Time in Sekunden
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: 1,5 Punkte
- Overall Code Quality (Datenstrukturen, Style, Kommentare): 1,5 Punkte
| Punkte | Note | |
|---|---|---|
| ≥ 10.5 | 1 | |
| (9, 10.5] | 2 | |
| (7.5, 9] | 3 | |
| (6, 7.5] | 4 | |
| < 6 | 5 |