Graph matching algorithms for business process model similarity search

R.M. Dijkman, M. Dumas, L. García-Bañuelos

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

306 Citations (Scopus)
1 Downloads (Pure)

Abstract

We investigate the problem of ranking all process models in a repository according to their similarity with respect to a given process model. We focus specaifically application of graph matching algorithms to this similarity search problem. Since the corresponding graph matching problem is NP-complete, we seek to find a compromise between computational complexity and quality of the computed ranking. Using a repository of 100 process models, we evaluate four graph matching algorithms, ranging from a greedy one to a relatively exhaustive one. The results show that the mean average precision obtained by a fast greedy algorithm is close to that obtained with the most exhaustive algorithm.
Original languageEnglish
Title of host publicationBusiness process management : 7th international conference, BPM 2009, Ulm, Germany, September 8-10, 2009 : proceedings
EditorsU. Dayal, J. Eder, J. Koehler, H.A. Reijers
Place of PublicationBerlin
PublisherSpringer
Pages48-63
ISBN (Print)978-3-642-03848-8
DOIs
Publication statusPublished - 2009
Event7th International Conference on Business Process Management (BPM 2009), September 8-10, 2009, Ulm, Germany - Ulm, Germany
Duration: 8 Sep 200910 Sep 2009

Publication series

NameLecture Notes in Computer Science
Volume5701

Conference

Conference7th International Conference on Business Process Management (BPM 2009), September 8-10, 2009, Ulm, Germany
Abbreviated titleBPM 2009
Country/TerritoryGermany
CityUlm
Period8/09/0910/09/09

Fingerprint

Dive into the research topics of 'Graph matching algorithms for business process model similarity search'. Together they form a unique fingerprint.

Cite this