Entwurf und Implementation eines DAG-Miners

Student:Tobias Werth
Title:Entwurf und Implementation eines DAG-Miners
Type:diploma thesis
Advisors:Wörlein, M.; Dreweke, A.; Fischer, I.; Philippsen, M.
State:submitted on January 15, 2007
Prerequisits:

Die Suche nach häufigen interessanten Daten in Graphdatenbanken ist ein Forschungsgebiet, das in den letzten Jahren sehr reges Interesse geweckt hat. Da viele Forschungs- und Wirtschaftsdaten in strukturierter Form erfasst werden können, bietet sich die Speicherung komplexer Zusammenhänge in Form von allgemeinen oder speziellen Graphen an. Diese meist unüberschaubaren Datenmengen sind nur schwere von Hand zu durchschauen, darum sind Algorithmen zur Entdeckung interessanter Korrelationen unabdingbar. Da diese auf Graphen im Allgemeinen sehr aufwändig sind, ist die Suche nach paralellen und spezialisierten Algorithmen notwendig, die den benötigen Rechenzeit- und Speicheranforderungen auch bei immer größer werdenden Datenmengen gewachsen sind.

Topic:

Neben der allgemeinen Suche nach häufigen Subgraphen in Graphdatenbanken existieren auch schon diverse effiziente Algorithmen, die sich auf spezielle Graphen (Bäume und Ketten) beschränken. Durch den beschränkten Suchraum können Vergleiche und kanonische Darstellungen, die im allgemeinen NP-vollständige Laufzeit und/oder Speicherplatz erfordern, durch lineare oder polynomielle Methoden ersetzt werden. Für gerichtete Graphen sind neben Bäumen und Ketten noch weitere spezielle Graphen bekannt: die gerichteten azyklischen Graphen(DAG).
In Hinsicht auf das Anwendungsgebiet Prozedurale Abstraktion(PA) rücken eben solche DAGs ins Blickfeld, da die zugrunde liegenden Datenflussgraphen von Basisblöcken DAGs sind. In dieser Arbeit sollen die vorteilhaften Eigenschaften von DAGs genutzt werden, um einen spezialisierten Graph-Miner für DAGs zu entwerfen und implementieren. Das Vorgehen sieht wie folgt aus:

  • Erarbeitung, Entwurf und Implementierung notwendiger Expansionsregeln von Fragmenten zum Erzeugen und Vergleichen unzusammenhängender DAG Fragmente vgl. [1]
  • Integration und Vervollständigung als funktionsfähiger Miner in die am Lehrstuhl vorhandenen Strukturen
  • Erweiterung auf graph- und einbettungsbasierte Suche [2]
  • Optional: Implementation und Vergleich mit einem heuristischen DFG-basierten PA-Algo (z.B. [3,4])
  • Optional: Einbau von problem-spezifischen Ergänzungen für PA
  • Vergleichende Messungen zwischen dem spezialisierten DAG-Miner und allgemeinen Graphminern [5]

[1] S. Nijssen and J. N. Kok. A quickstart in frequent structure mining can make a difference. Technical report, LIACS, Leiden University, Leiden, The Netherlands, 2004.
[2] Michihiro Kuramochi and George Karypis. Finding frequent patterns in a large sparse graph. Data Min. Knowl. Discov., 11(3):243-271, November 2005.
[3] David C. Zaretsky, Gaurav Mittal, Robert P. Dick, and Prith Banerjee. Dynamic template generation for resource sharing in control and data flow graphs. In Proceedings of the 19th Int'l Conf. on VLSI Design, pages 465-468, Hyderabad, India, January 2006. IEEE Computer Society.
[4] Philip Brisk, Adam Kaplan, Ryan Kastner, and Majid Sarrafzadeh. Instruction generation and regularity extraction for reconfigurable processors. In Proceedings of the Int'l Conf. on Compilers, Architecture, and Synthesis for Embedded Systems, pages 262-269, New York, NY, USA, 2002.
[5] Wörlein, M., Meinl, Thorsten, Fischer, Ingrid, Philippsen, Michael A quantitative comparison of the subgraph miners MoFa, gSpan, FFSM, and Gaston PKDD 2005, Porto, Portugal, 2005.

watermark seal