Title:
|
DAGMA: MINING DIRECTED ACYCLIC GRAPHS |
Author(s):
|
T. Werth , A. Dreweke , M. Wörlein , I. Fischer , M. Philippsen |
ISBN:
|
978-972-8924-63-8 |
Editors:
|
Hans Weghorn and Ajith P. Abraham |
Year:
|
2008 |
Edition:
|
Single |
Keywords:
|
Graph Mining, Compiler Construction |
Type:
|
Full Paper |
First Page:
|
11 |
Last Page:
|
18 |
Language:
|
English |
Cover:
|
|
Full Contents:
|
click to dowload
|
Paper Abstract:
|
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. |
|
|
|
|