ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2017, Vol. 54 ›› Issue (4): 832-843.doi: 10.7544/issn1000-1239.2017.20151176

Previous Articles     Next Articles

A Similarity Measure for Process Models Based on Task Occurrence Relations

Song Jinfeng, Wen Lijie, Wang Jianmin   

  1. (School of Software, Tsinghua University, Beijing 100084)
  • Online:2017-04-01

Abstract: Similarity measures between process models are increasingly important for management, reuse, and analysis of process models in modern enterprises. So far, several approaches have been proposed and behavioral profile (BP) is a good concept to judge the behavioral consistency of process models, which describes the observable relations between tasks. However, all those approaches have their own advantages and disadvantages. Towards the hard problem of behavioral similarity measure between process models, especially to improve the effectiveness of BP, a new method for measuring the behavioral similarity between process models named TOR based on the occurrence relation among tasks is proposed. Based on complete prefix unfolding (CPU) technique of Petri nets, we propose the algorithms for numbering the nodes in a CPU and computing the least common precursors for each pair of nodes. Then we define the three basic occurrence relations between tasks: causal relation, concurrent relation and conflict relation. The algorithm for efficiently computing the relations and the formalism for computing the similarity are also given. TOR can handle both invisible tasks and non-free choice constructs. The experimental results show the effectiveness and efficiency of TOR. Compared with the existing mainstream behavioral similarity algorithms for process models, TOR can satisfy all the five properties that a good similarity algorithm should have.

Key words: similarity measure, occurrence relations of tasks, process model, complete prefix unfolding (CPU), Petri nets

CLC Number: