A quantitative comparison of the subgraph miners MoFa, gSpan, FFSM, and Gaston - Wörlein, Marc; Meinl, Thorsten; Fischer, Ingrid; Philippsen, Michael (Knowledge Discovery in Database: PKDD 2005, 2005)
Several new miners for frequent subgraphs have been published recently. Whereas new approaches are presented in detail, the quantitative evaluations are often of limited value: only the performance on a small set of graph databases is discussed and the new algorithm is often only compared to a single competitor based on an executable. It remains unclear, how the algorithms work on bigger/other graph databases and which of their distinctive features is best suited for which database. We have re-implemented the subgraph miners MoFa, gSpan, FFSM, and Gaston within a common code base and with the same level of programming expertise and optimization effort. This paper presents the results of a comparative benchmarking that ran the algorithms on a comprehensive set of graph databases. © Springer-Verlag Berlin Heidelberg 2005.
UnivIS-Import:2015-04-16:Pub.2005.tech.IMMD.IMMD2.aquant
Keywords: graph; mining; comparison; MoFa; gSpan; FFSM; Gaston

DAGMA: Mining Directed Acyclic Graphs (Outstanding Paper Award) - Werth, Tobias; Dreweke, Alexander; Wörlein, Marc; Fischer, Ingrid; Philippsen, Michael (Proceedings of the IADIS European Conference on Data Mining, 2008)
We present how to efficiently mine a set of directed acyclic graphs (DAGs) for unconnected, both multi- or single-rooted, and induced fragments. With a new canonical form that is based on the nodes' topological levels, our miner is faster and uses less storage than general purpose gSpan (Yan, X. and Han, J., 2002). Moreover, it can base support resp. frequency either on the number of embeddings of a fragment in the database or on the number of graphs a fragment appears in. This is crucial for finding frequent fragments in data flow graphs generated from assembly code. Extracting them into new procedures reduces the total code size. The paper shows that our miner outperforms general purpose mining and demonstrates the quantitative effects of DAG mining in program size reduction.
UnivIS-Import:2015-04-16:Pub.2008.tech.IMMD.IMMD2.dagmam

DAG Mining for Code Compaction - Werth, Tobias; Dreweke, Alexander; Wörlein, Marc; Fischer, Ingrid; Philippsen, Michael (Data Mining for Business Applications, 2009)
In order to reduce cost and energy consumption, code-size optimization is an important issue for embedded systems. Traditional instruction saving techniques recognize code duplications only in exactly the same order within the program. As instructions can be reordered with respect to their data dependencies, Procedural Abstraction achieves better results on data flow graphs that reflect these dependencies. Since these graphs are always directed acyclic graphs (DAGs), a special mining algorithm for DAGs is presented in this chapter. Using a new canonical representation that is based on the topological order of the nodes in a DAG, the proposed algorithm is faster and uses less memory than the general graph mining algorithm gSpan. Due to its search lattice expansion strategy, an efficient pruning strategy is applied to the algorithm while using it for Procedural Abstraction. Its search for unconnected graph fragments outperforms traditional approaches for code-size reduction. © 2009 Springer US.
UnivIS-Import:2015-04-20:Pub.2009.tech.IMMD.IMMD2.dagmin

Edgar: the Embedding-baseD GrAph MineR - Wörlein, Marc; Dreweke, Alexander; Meinl, Thorsten; Fischer, Ingrid; Philippsen, Michael (Proceedings of the International Workshop on Mining and Learning with Graphs, 2006)
UnivIS-Import:2015-04-16:Pub.2006.tech.IMMD.IMMD2.edgart

Extension and parallelization of a graph-mining-algorithm - Wörlein, Marc (Friedrich-Alexander-Universität Erlangen-Nürnberg, 2006)
UnivIS-Import:2016-07-26:Pub.2006.tech.IMMD.IMMD2.extens

Graph-based procedural abstraction - Dreweke, Alexander; Wörlein, Marc; Fischer, Ingrid; Schell, Dominic; Meinl, Thorsten; Philippsen, Michael (International Symposium on Code Generation and Optimization (CGO'07), 2007)
Procedural abstraction (PA) extracts duplicate code segments into a newly created method and hence reduces code size. For embedded micro computers the amount of memory is still limited so code reduction is an important issue. This paper presents a novel approach to PA, that is especially targeted towards embedded systems. Earlier approaches of PA are blind with respect to code reordering, i.e., two code segments with the same semantic effect but with different instruction orders were not detected as candidates for PA. Instead of instruction sequences, in our approach the data flow graphs of basic blocks are considered. Compared to known PA techniques more than twice the number of instructions can be saved on a set of binaries, by detecting frequently appearing graph fragments with a graph mining tool based on the well known gSpan algorithm. The detection and extraction of graph fragments is not as straight forward as extracting sequential code fragments. NP-complete graph operations and special rules to decide which parts can be abstracted are needed. However, this effort pays off as smaller sizes significantly reduce costs on mass-produced embedded systems. © 2007 IEEE.

Mining Molecular Datasets on Symmetric Multiprocessor Systems - Meinl, Thorsten; Wörlein, Marc; Fischer, Ingrid; Philippsen, Michael (Proceedings of the 2006 IEEE International Converence on Systems, Man and Cybernetics, 2006)
Although in the last few years about a dozen sophisticated algorithms for mining frequent fragments in molecular databases have been proposed, searching big databases with 100,000 compounds and more is still a time-consuming process. Even the currently fastest algorithms like gSpan, FFSM, Gaston, or MoFa require hours to complete their tasks. This paper presents thread-based parallel versions of MoFa [5] and gSpan [26] that achieve speedups up to 11 on a shared-memory SMP system using 12 processors. We discuss the design space of the parallelization, the results, and the obstacles that are caused by the irregular search space and by the current state of Java technology.
UnivIS-Import:2015-04-16:Pub.2006.tech.IMMD.IMMD2.mining

Text Mining in Program Code - Dreweke, Alexander; Fischer, Ingrid; Werth, Tobias; Wörlein, Marc (Handbook of Research on Text and Web Mining Technologies, 2009)
Searching for frequent pieces in a database with some sort of text is a well-known problem. A special sort of text is program code as e.g. C++ or machine code for embedded systems. Filtering out duplicates in large software projects leads to more understandable programs and helps avoiding mistakes when reengineering the program. On embedded systems the size of the machine code is an important issue. To ensure small programs, duplicates must be avoided. Several different approaches for finding code duplicates based on the text representation of the code or on graphs representing the data and control flow of the program and graph mining algorithms.
UnivIS-Import:2015-04-20:Pub.2009.tech.IMMD.IMMD2.textmi

The ParMol Package for Frequent Subgraph Mining - Meinl, Thorsten; Wörlein, Marc; Urzova, Olga; Philippsen, Michael; Fischer, Ingrid (Electronic Communications of the EASST, 2006)
UnivIS-Import:2015-03-09:Pub.2006.tech.IMMD.IMMD2.thepar

The ParMol package for frequent subgraph mining - Meinl, Thorsten; Wörlein, Marc; Urzova, Olga; Fischer, Ingrid; Philippsen, Michael (Third International Workshop on Graph Based Tools, 2006)
UnivIS-Import:2015-04-16:Pub.2006.tech.IMMD.IMMD2.thepar_5