Ähnlichkeitssuche in großen Datenbanken
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] | |
| 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 | [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] | |
| 10. | Windowed pq-Grams for Unordered Trees | [1up] [4up] [animation] |
|
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 bzw. über das Universitätsnetzwerk 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
- die technische Korrektheit der Antwort,
- der Detailgrad der Antwort, d.h. wie tief-schürfend wurde das Thema behandelt,
- die Vollständigkeit der Antwort, d.h. wurden alle Aspekte berücksichtigt,
- der Gebrauch der passenden Fachterminologie,
- die Fähigkeit, auf vertiefende Fragen einzugehen.
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.
Hier ein Beispiel des Fragebogen. Der tatsächliche Fragebogen kann – angepasst an das Thema des Vortrages – von diesem Beispiel etwas abweichen.
Jeder Student / jede Studentin nimmt an mindestens 5 Vorträgen als Zuhörer / Zuhörerin teil, bei genau 5 Vorträgen werden die Fragen zum Vortrag beantwortet. Fragebögen, die abgegeben werden, werden bewertet und können nicht verbessert werden. Die Vorträge können frei gewählt werden, unabhängig von der Zugehörigkeit zu einer der beiden Proseminar-Gruppen.
Die Noten sind personenbezogen und können sich innerhalb einer Gruppe unterscheiden.
Zeitplan
Die Vorbesprechung findet jeweils im Büro 1.16 statt.
Jeder Student / jede Studentin nimmt an mindestens 5 Vorträgen als Zuhörer / Zuhörerin teil, bei genau 5 Vorträgen werden die Fragen zum Vortrag beantwortet. Fragebögen, die abgegeben werden, werden bewertet und können nicht verbessert werden. Die Vorträge können frei gewählt werden, unabhängig von der Zugehörigkeit zu einer der beiden Proseminar-Gruppen.
| 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 |
|||
Forschungspapiere
Die Forschungspapiere sind in thematische Gruppen geordnet.
Blocking Methods
- Peter Christen: A Survey of Indexing Techniques for Scalable Record Linkage and Deduplication. IEEE TKDE 24(9): 1537-1555 (2012)
- Giovanni Simonini, Sonia Bergamaschi, H.V. Jagadish: BLAST: a Loosely Schema-aware Meta-blocking Approach for Entity Resolution. PVLDB 9(12): 1173-1184 (2016)
- George Papadakis, George Alexiou, George Papastefanatos, Georgia Koutrika: Schema-agnostic vs Schema-based Configurations for Blocking Methods on Homogeneous Data. PVLDB 9(4): 781-792 (2015)
- George Papadakis, Jonathan Svirsky, Avigdor Gal, Themis Palpanas: Comparative Analysis of Approximate Blocking Techniques for Entity Resolution. PVLDB 9(9): 684-695 (2016)
Clustering Techniques
- Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, Jörg Sander: OPTICS: Ordering Points To Identify the Clustering Structure. ACM SIGMOD: 49-60 (1999)
- Keyu Yang , Yunjun Gao, Rui Ma, Lu Chen, Sai Wu, Gang Chen: DBSCAN-MS: Distributed Density-Based Clustering in Metric Spaces. IEEE ICDE: 1346-1357 (2019)
- Martin Ester, Hans-Peter Kriegel, Jiirg Sander, Xiaowei Xu: A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. KDD: 226-231 (1996)
- Hwanjun Song, Jae-Gil Lee: RP-DBSCAN: A Superfast Parallel DBSCAN Algorithm Based on Random Partitioning. ACM SIGMOD: 1173-1187 (2018)
- Junhao Gan, Yufei Tao: Dynamic Density Based Clustering. ACM SIGMOD: 1493-1507 (2017)
- Junhao Gan, Yufei Tao: DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation. ACM SIGMOD: 519-530 (2015)
Entity Resolution
- William W. Cohen: Integration of Heterogeneous Databases Without Common Using Queries Based on Textual Similarity. ACM SIGMOD: 201-212 (1998)
- Yufei Tao: Entity Matching with Active Monotone Classification. ACM PODS: 42-62 (2018)
- Donatella Firmani, Barna Saha, Divesh Srivastava: Online Entity Resolution Using an Oracle. PVLDB 9(5): 384-395 (2016)
String and Set Similarity
- Pei Wang, Chuan Xiao, Jianbin Qin, Wei Wang, Xiaoyang Zhang, Yoshiharu Ishikawa: Local Similarity Search for Unstructured Text. ACM SIGMOD: 1991-2005 (2016)
- Roberto J. Bayardo, Yiming Ma, Ramakrishnan Srikant: Scaling Up All Pairs Similarity Search. WWW: 131-140 (2007)
- Dong Deng, Guoliang Li, He Wen, Jianhua Feng: An Efficient Partition Based Method for Exact Set Similarity Joins. PVLDB 9(4): 360-371 (2015)
- Ji Sun, Zeyuan Shang, Guoliang Li, Dong Deng, Zhifeng Bao: Balance-aware distributed string similarity-based query processing system. PVLDB 12(9): 961-974 (2019)
- Dong Deng, Yufei Tao, Guoliang Li: Overlap Set Similarity Joins with Theoretical Guarantees. ACM SIGMOD: 905-920 (2018)
- Erkang Zhu, Dong Deng, Fatemeh Nargesian, Renée J. Miller: JOSIE: Overlap Set Similarity Search for Finding Joinable Tables in Data Lakes. SIGMOD Conference 2019: 847-864
Semantic Similarity Queries
- Dong Deng, Guoliang Li, He Wen, Jianhua Feng: K-Join: Knowledge-Aware Similarity Join. IEEE TKDE 28(12): 3293-3308 (2016)
- Yeye He, Kris Ganjam, Xu Chu: SEMA-JOIN: Joining Semantically-Related Tables Using Big Table Corpora. PVLDB 8(12): 1358-1369 (2015)
- Dong Deng, Albert Kim, Samuel Madden, Michael Stonebraker: SilkMoth: An Efficient Method for Finding Related Sets with Maximum Matching Constraints. PVLDB 10(10): 1082-1093 (2017)
Time Series and Metric Spaces
- Karima Echihabi, Kostas Zoumpatianos, Themis Palpanas, Houda Benbrahim: The lernaean hydra of data series similarity search: an experimental evaluation of the state of the art. PVLDB 12(2): 112-127 (2018)
Threshold-join in Euclidean space
- Martin Perdacher, Claudia Plant, Christian Böhm: Cache-oblivious High-performance Similarity Join. SIGMOD Conference 2019: 87-104