Ähnlichkeitssuche in großen Datenbanken

Vorlesung:
Proseminar:
Sprache:
Deutsch/Englisch
Sprechstunde:
Fragen bitte über Slack.
Semester:
Wintersemester 2020/2021
PlusOnline:

News

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]

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

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: TBA 19.01.2021, 23:55

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
07.01.2021 Task 4 On-Demand Session ---
14.01.2021 Task 4 On-Demand Session ---
21.01.2021 Final Session ---
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

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:
  1. Korrektheit: 1,5 Punkte
  2. 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