DAG Mining for Code Compaction

Werth T, Dreweke A, Wörlein M, Fischer I, Philippsen M (2009)

Publication Language: English

Publication Type: Book chapter / Article in edited volumes

Publication year: 2009

Publisher: Springer

Edited Volumes: Data Mining for Business Applications

City/Town: Berlin Heidelberg

Pages Range: 209-224

ISBN: 978-0-387-79419-8

URI: http://www2.informatik.uni-erlangen.de/publication/download/WDWFP09.pdf

DOI: 10.1007/978-0-387-79420-4_15


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.

Authors with CRIS profile

How to cite


Werth, T., Dreweke, A., Wörlein, M., Fischer, I., & Philippsen, M. (2009). DAG Mining for Code Compaction. In Cao, L. ; Yu, P. S. ; Zhang, C. ; Zhang, H. (Eds.), Data Mining for Business Applications. (pp. 209-224). Berlin Heidelberg: Springer.


Werth, Tobias, et al. "DAG Mining for Code Compaction." Data Mining for Business Applications. Ed. Cao, L. ; Yu, P. S. ; Zhang, C. ; Zhang, H., Berlin Heidelberg: Springer, 2009. 209-224.

BibTeX: Download