A Runtime Analysis of Graph-Theoretical Algorithms to Detect Patterns in Process Model Collections

Becker Jörg, Breuker Dominic, Delfmann Patrick, Dietrich Hanns-Alexander, Steinhorst Matthias


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



Publikationstyp
Aufsatz (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