Ähnlichkeitssuche in großen Datenbanken

Vorlesung:
Proseminar:
Sprache:
Deutsch/Englisch
Sprechstunde:
auf Anfrage via Email
Semester:
Wintersemester 2016/2017
PlusOnline:

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 Prüfung am Ende des Semesters.

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 and Relational Databases: Tree Definition, Adjacency List Encoding, Dewey Encoding, Interval Encoding, XML as a Tree [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.

Proseminar

Im Proseminar werden Projekte zu aktuellen Forschungsthemen ausgearbeitet. Details werde in der Vorbesprechung bekannt gegeben.