Ähnlichkeitssuche in großen Datenbanken

Vorlesung:
Proseminar:
Sprache:
Deutsch/Englisch
Sprechstunde:
auf Anfrage via Email
Semester:
Wintersemester 2018/2019
PlusOnline:

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
7. Reference Sets: Pruning with Reference Sets
8. Binary Branch Distance: Algorithm, Lower Bound Proof, Complexity
9. pq-Gram Distance: Algorithm and Lower Bound Theorem

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

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

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.