Ähnlichkeitssuche in großen Datenbanken

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

News

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.

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]

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.

Als weiterführende Literatur wird außerdem auf die originalen Forschungsarbeiten verwiesen, die auf den Vorlesungsfolien referenziert sind.

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

Organisation

Die Studierenden erarbeiten aktuelle und klassische Forschungsergebnisse im Bereich der Ähnlichkeitssuche in großen Datenbanken anhand der Orginalpapiere und stellen diese im Rahmen der Lehrveranstaltung vor. Die Forschungsergebnisse werden in Gruppen von 2-3 Personen erarbeitet.

Details und Terminplan werden während der Vorbesprechung besprochen.

Bewertet werden die Qualität des Vortrages, die Teilnahme an den Diskussionen, sowie die Qualität der Diskussionsbeiträge. Am Ende des Vortrags wird ein Fragebogen zum Vortrag ausgefüllt, der ebenfalls bewertet wird.

Die Noten sind personenbezogen und können sich innerhalb einer Gruppe unterscheiden.

Forschungspapiere

Die Forschungspapiere sind in thematische Gruppen geordnet.

Blocking Methods

Clustering Techniques

Entity Resolution

String and Set Similarity

Semantic Similarity Queries

Time Series and Metric Spaces

Threshold-join in Euclidean space

Zeitplan

Die Vorbesprechung findet jeweils im Büro 1.16 statt.


Datum Zeit Titel Vorbesprechung
13.11. 16:00 A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise
V. Eibl, J. Geissbauer, D. Schmid
Mi 30.10.
16:00
13.11. 17:15 OPTICS: Ordering Points To Identify the Clustering Structure
J. Himmelsbach, V. Lorber, K. Thiel
Mi 30.10.
16:40
20.11. 16:00 DBSCAN-MS: Distributed Density-Based Clustering in Metric Spaces
L. Berer, I. Maier
Mi 06.11.
16:00
20.11. 17:15 RP-DBSCAN: A Superfast Parallel DBSCAN Algorithm Based on Random Partitioning
J. Kanzler, M. Nening, M. Widmoser
Mi 06.11.
16:40
27.11. 16:00 DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation
J. Hettegger, A. Paschos, T. Matheis
Di 12.11.
17:30
27.11. 17:15 Dynamic Density Based Clustering
S. Schütz, J. Spasojevic
Di 12.11.
18:10
04.12. 16:00 Local Similarity Search for Unstructured Text
C. Brugger, T. Fuchs, M. Tschimpke
Do 21.11.
16:00
04.12. 17:15 SEMA-JOIN: Joining Semantically-Related Tables Using Big Table Corpora
T. Hilgart, S. Milla
Do 21.11.
16:40
11.12. 16:00 A Survey of Indexing Techniques for Scalable Record Linkage and Deduplication
D. Arifi, S. Reischl, D. Schwarz
Do 28.11.
16:00
11.12. 17:15 Online Entity Resolution Using an Oracle
N. Großegesse, P. Huber, T. Ungerhofer
Do 28.11.
16:40