Mining for Hyperedges --- Structure Mining in Property Graphs

Masterarbeit, gegebenenfalls auch als BA

Betreuer / Ansprechpartner

  • Holger Meyer,
  • Alf-Christian Schering

    Charakter

      • Darstellung State of the Art,
      • Konzeption,
      • prototypische Implementierung

      Vorkenntnisse

      • Datenbanken I
      • Datenbanken II und III wünschenswert

      Beschreibung

      Im Zentrum der Untersuchungen des ISEBEL-Projektes stehen Glaubenssysteme [1], 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 [2] 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.

      Um typische Fragestellungen der Erzählforschung effizient und effektiv zu unterstützen, sollen Techniken des Graph-Mining untersucht werden. Dazu ist der State-of-the-Art in diesem Bereich eingehend zu untersuchen und darzustellen.

      Im weiteren ist dann eine Analyse geeigneter Graph-Mining-Frameworks (etwa GraphX von Apache Spark, Gelly bzw. Gradoop unter Nutzung von Apache Flink) vorzunehmen, mit dem Ziel, eine geeignete Plattform auszuwählen und auf dem vorhandenen Rechner-Cluster (RMDRF) einzusetzen. Die Eignung ist an exemplarischen Fragestellungen zu demonstrieren.

      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 [3] verwendet zur Speicherung gerichtete, typisierte Hypergraphen [4].

      Dagen liegen die Daten beim dänischen Erzählforscher Ewald Tang Kristensen und der niederländischen Verhalenbank in relationalen Strukturen vor.  Um die Daten aller drei Datenbanken zusammenzufuehren, soll nach haeufigen Strukturen (Frequent Pattern Mining) in diesen Bestaenden gesucht werden mit dem Ziel, diese dann in typisierte Hyperkanten zu überführen.

      Arbeitsschritte

      • Recherche, Aufbereitung und Klassifikation existierender Ansätze zum Graph-Mining
      • 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-, ETKBase bzw. Volksverhalen-Datensätzen

      Technologien

      • Graph-Mining-Framrworks: Apache Spark/GraphX, Flink, Gradoop
      • NoSQL/Graphdatenbanken und Hypergraphen

      Literatur

        1. Usó-Doménech, J.L. & Nescolarde-Selva, J. Found Sci (2016) 21: 147.
        2. Charu C. Aggarwal, Haixun Wang: Managing and Mining Graph Data. Advances in Database Systems 40, Springer 2010, ISBN 978-1-4419-6044-3
        3. Meyer, Holger, Alf-Christian Schering, and Andreas Heuer. "The Hydra. PowerGraph System." Datenbank-Spektrum (2017): 1-17.
        4. Holger Meyer, Alf-Christian Schering and Christoph Schmitt, 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.
        5. Michael J. Anderson, Narayanan Sundaram, Nadathur Satish, Md. Mostofa Ali 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.
        6. 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
        7. Meyer, U., Sanders, P.: Delta-stepping: a parallelizable shortest path algorithm. J. Algorithms 49(1), 114–152 (2003).
        8. Xin, Reynold S., et al. "Graphx: Unifying data-parallel and graph-parallel analytics." arXiv preprint arXiv:1402.2394 (2014).
        9. Shiladitya Munshi, Ayan Chakraborty, Debajyoti Mukhopadhyay: Theories of Hypergraph-Graph (HG(2)) Data Structure. CoRR abs/1311.7201 (2013).
        10. 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.
        11. 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.