A Runtime Analysis of Graph-Theoretical Algorithms to Detect Patterns in Process Model Collections
Abstract
Pattern detection serves different purposes in managing large collections of process models, ranging from syntax checking to compliance validation. This paper presents a runtime analysis of four graph-theoretical algorithms for (frequent) pattern detection. We apply these algorithms to large collections of process and data models to demonstrate that, despite their theoretical intractability, they are able to return results within (milli-) seconds. We discuss the relative performance of these algorithms and their applicability in practice.
Keywords
Conceptual Model Analysis; Subgraph Isomorphism; Frequent Subgraph Detection; Pattern Matching
Cite as
Becker, J., Breuker, D., Delfmann, P., Dietrich, H.-A., & Steinhorst, M. (2012). A Runtime Analysis of Graph-Theoretical Algorithms to Detect Patterns in Process Model Collections. In Marcello, L. R., & Pnina, S. (Eds.), Business Process Management Workshops (pp. 489–500). Lecture Notes in Business Information Processing: Vol. 132. Berlin, Heidelberg: Springer.Details
Publication type
Research article in proceedings (conference)
Peer reviewed
Yes
Publication status
Published
Year
2012
Conference
2nd International Workshop on Process Model Collections (PMC) 2012
Venue
Tallinn, Estonia
Book title
Business Process Management Workshops
Editor
Marcello La Rosa, Pnina Soffer
Start page
489
End page
500
Volume
132
Title of series
Lecture Notes in Business Information Processing
Publisher
Springer
Place
Berlin, Heidelberg
Language
English
DOI