Ähnlichkeitssuche in großen Datenbanken
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.
Proseminar
Im Proseminar werden Projekte zu aktuellen Forschungsthemen ausgearbeitet. Details werde in der Vorbesprechung bekannt gegeben.