Querying Similar Process Models Based on the Hungarian Algorithm
Authors:
- 2 August 2016
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Services Computing
- Vol. 10 (1) , 121-135
Abstract
The structural similarity between two process models is usually considered as the main measurement for ranking the process models for a given query model. Current process query methods are inefficient since too many expensive computations of the graph edit distance are involved. To address this issue, using Petri-net as the modeling method, this paper presents the Hungarian algorithm based similarity query method. Unlike previous work where the non-task nodes (i.e., place nodes in the Petri-net) were lightly studied or even ignored, we think these non-task nodes also play an essential role in measuring the structural similarity between process models. First, we extract the context for each place and define the similarity for a pair of place nodes that are from different process models from two perspectives: commonality and the graph edit distance. Then, the place mapping is transformed to classical assignment problem that can be solved by Hungarian algorithm efficiently. Furthermore, we propose a new process similarity measurement on the basis of the place similarity. The extensive experimental evaluation shows that our Hungarian based methods outperform the baseline algorithm in both retrieval quality and query response time.Keywords
Funding Information
- National Natural Science Foundation of China (61602411, 61173097, 61572437)
- Key Research and Development Project of Zhejiang Province (2015C01034, 2015C01029, 2017C01013)
- Major Science and Technology Innovation Project of Hangzhou (20152011A03)
This publication has 35 references indexed in Scilit:
- Efficient and exact query of large process model repositories in cloud workflow systemsIEEE Transactions on Services Computing, 2015
- A Maximal Common Subgraph Based Method for Process Retrieval2013
- Efficient Retrieval of Similar Workflow Models Based on Behavior2012
- Searching Business Process Repositories Using Operational Similarity2011
- Metric Trees for Efficient Similarity Search in Large Process Model Repositories2011
- Querying Business Process Models Based on Semantics2011
- Efficient Consistency Measurement Based on Behavioral Profiles of Process ModelsIEEE Transactions on Software Engineering, 2010
- A workflow net similarity measure based on transition adjacency relationsComputers in Industry, 2010
- Ranking BPEL Processes for Service DiscoveryIEEE Transactions on Services Computing, 2010
- A survey of graph edit distancePattern Analysis and Applications, 2009