A Runtime Analysis of Graph-Theoretical Algorithms to Detect Patterns in Process Model Collections
Zusammenfassung
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.
Schlüsselwörter
Conceptual Model Analysis; Subgraph Isomorphism; Frequent Subgraph Detection; Pattern Matching
Zitieren als
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
Publikationstyp
Forschungsartikel in Sammelband (Konferenz)
Begutachtet
Ja
Publikationsstatus
Veröffentlicht
Jahr
2012
Konferenz
2nd International Workshop on Process Model Collections (PMC) 2012
Konferenzort
Tallinn, Estonia
Buchtitel
Business Process Management Workshops
Herausgeber
Marcello La Rosa, Pnina Soffer
Erste Seite
489
Letzte Seite
500
Band
132
Reihe
Lecture Notes in Business Information Processing
Verlag
Springer
Ort
Berlin, Heidelberg
Sprache
Englisch
DOI