Effiziente Kandidaten-Generierung und Selektion im Parallelen Subgraph-Mining

Betreuer / Ansprechpartner

  • Holger Meyer

Gutachter

  • Andreas Heuer
  • Holger Meyer

Typ der Arbeit

  • Bachelorarbeit

Charakter der Arbeit

  • Erarbeitung State-of-the-Art

  • Konzeption

  • prototypische Implementierung

Vorkenntnisse

  • Datenbanken 

  • Graphen

  • Algorithmen

Beschreibung

Im Zentrum der Untersuchungen des ISEBEL-Projektes stehen Glaubenssysteme [2], speziell im Bereich der Legenden. Dazu werden drei Sammlungen namhafter Erzählforscher wie Evald Tang Kristensen in Dänemark, Richard Wossidlo zu Mecklenburg und niederländischer Sammler und Forscher aufbereitet, zusammengeführt und mit Graph-Mining-Techniken [3] auf gemeinsame, wiederkehrende Muster untersucht. Diese Muster beschreiben, wie etwa Legenden entstehen, wie sie weitergeben werden, sich entwickeln und in welchem kulturellem Umfeld dies geschieht.

Die Inhalte des Wossidlo-Archivs, die Feldforschungsbelege, Auszüge der Korrespondenzen Wossidlos mit einem umfangreichen Beiträgernetzwerk, Verweise auf publizierte Werke zu den einzelnen Bereichen des täglichen Lebens und weiterer Kollektionen, liegen in digitalisierter Form vor. Das WossiDiA-System [4] verwendet zur Speicherung gerichtete, typisierte Hypergraphen [5].

Um typische Fragestellungen der Erzählforschung effizient und effektiv zu unterstützen, wird an der Parallelisierung von Verfahren des Graph-Mining gearbeitet [1]. Ziel der Arbeit ist der Vergleich mit anderen Verfahren, dessen Bewertung und Verbesserung der Parallelisierung gegebenenfalls. Ansatzpunkte für die Parallelisierung sind in einer geeigneten Graph-Partitionierung sowie der Kandidatengenerierung und -selektion zu sehen und untersuchen. Ausgehen vom State-of-the-Art in diesem Bereich ist eine Analyse, Evaluierung und Performanz-Bewertung geeigneter Frequent Subgraph Mining- Verfahren im Apache Spark-Framework auf dem vorhandenen Rechner-Cluster (RMDRF) vorzunehmen. Der Vergleich ist an exemplarischen Fragestellungen aus dem ISEBEL- Projekt oder existierender Benchmarks zu vollziehen.

Arbeitsschritte

  • Recherche, Aufbereitung und Klassifikation existierender Ansätze für Graph- Partitionierung, Mining-Verfahren und deren Parallelisierung; Darstellung des State-of-the-Art

  • Untersuchung der Übertragbarkeit auf Hypergraphstrukturen

  • Kritische Bewertung der existierenden Frameworks und einer Plattform für den Einsatz auf dem vorhandenen Cluster im Rahmen des ISEBEL-Projektes

  • Demonstration der Tauglichkeit anhand ausgewählter Fragestellungen auf dem WossiDiA-Datensatz

Literatur

  1. Fenske, Ole. Parallele Graph-Mining-Techniken zur Auswertung von Hypergraph- Strukturen. Bachelor-Arbeit, Universität Rostock, 2018.

  2. Usó-Doménech,J.L.&Nescolarde-Selva,J.FoundSci(2016)21:147.

  3. CharuC.Aggarwal,HaixunWang:ManagingandMiningGraphData.Advancesin Database Systems 40, Springer 2010, ISBN 978-1-4419-6044-3

  4. Meyer,Holger,Alf-ChristianSchering,andAndreasHeuer."TheHydra.PowerGraph System." Datenbank-Spektrum (2017): 1-17.

  5. Meyer,Holger,Alf-ChristianScheringandChristophSchmitt,WossiDiA---The Digital Wossidlo Archive, in: Holger Meyer, Christoph Schmitt, Thomas Jansen and Alf-Christian Schering (Hrsg.), Corpora ethnographica online --- Strategien der Digitalisierung kultureller Archive und ihrer Präsentation im Internet, Volume 5 of Rostocker Beiträge zur Volkskunde und Kulturgeschichte, Waxmann, 2014, 61--84.

  6. MichaelJ.Anderson,NarayananSundaram,NadathurSatish,Md.MostofaAli Patwary, Theodore L. Willke, Pradeep Dubey, "GraphPad: Optimized Graph Primitives for Parallel and Distributed Platforms", Parallel and Distributed Processing Symposium 2016 IEEE International, pp. 313-322, 2016, ISSN 1530- 2075.

  7. Maleki S., Evans G.C., Padua D.A. (2015) Tiled Linear Algebra a System for Parallel Graph Algorithms. In: Brodman J., Tu P. (eds) Languages and Compilers for Parallel Computing. LCPC 2014. Lecture Notes in Computer Science, vol 8967. Springer, Cham

  8. Meyer,U.,Sanders,P.:Delta-stepping:aparallelizableshortestpathalgorithm.J. Algorithms 49(1), 114–152 (2003).

  9. Xin,ReynoldS.,etal."Graphx:Unifyingdata-parallelandgraph-parallelanalytics." arXiv preprint arXiv:1402.2394 (2014).

  10. Shiladitya Munshi, Ayan Chakraborty, Debajyoti Mukhopadhyay: Theories of Hypergraph-Graph (HG(2)) Data Structure. CoRR abs/1311.7201 (2013).

  11. Dominguez-Sal, David, et al. "Survey of graph database performance on the hpc scalable graph analysis benchmark." Web-Age Information Management. Springer Berlin Heidelberg, 2010. 37-48.

  12. Barbay, Jérémy, Luca Castelli Aleardi, Meng He, and J. Ian Munro. "Succinct representation of labeled graphs." Algorithmica 62, no. 1-2 (2012): 224-257.
     
  13. Kuramochi, Michihiro, and George Karypis, Finding Topological Frequent Patterns from Graph Datasets. in: Cook, Diane J, and Lawrence B Holder, Mining Graph Data. Wiley, Hoboken NJ, 2007.