A Difference Detection Algorithm For Process Models Based On Tree Structure

Detecting difference between business process models is one of the process model management technologies,which has been widely used in the business process management.However,there exist several problems in the existing difference detection methods: 1.Most of the process models are modeled by graphs that contain more than one kind of nodes.In this way,the traditional graph edit distance(GED)can't be directly used to detect difference between these kinds of models.2.Existing methods,either quantitative calculation for process model difference(process similarity calculation)or studying the classification for the differences,can't reflect the entire composition of the difference.To overcome the mentioned problems,we first studies and analyzes the existing related work,then presents a new model to represent the process model,finally an efficiently algorithm for detecting difference between process models is proposed.The research work mainly contains the following aspects:(1)GED can't be directly used to detect difference between process models,it is because the graph based process model contains more than one kinds of nodes.Thus,this paper adopts a task based process structure tree(TPST)that is semi-ordered to represent a process model,where the leaf node corresponds with the task node and non-leaf node represents the control flow structure of process model.In this way,detecting difference between process models is transformed to detect difference between their corresponding TPSTs,and some related experiments are designed to evaluate the efficiency of constructing the TPST.(2)The divide and conquer strategy is used in the first phase of detecting difference between process models,which is used to quickly obtain the optimal mapping node set.In the first phase,two TPSTs are split into their corresponding several fragments,the mapped fragment pair set of two TPST is obtained by Hungarian algorithm,which can reduce the mapping space and then quickly find the mapped node pairs.(3)In the second phase of detecting difference between two process models,based on the node mapping,this paper defines the edit operations and their corresponding costs,and then designs an approximate cost minimum edit script generation algorithm,where the edit script is regarded as the difference between two process models.The related experiments designed for this phase show that the process model difference detection algorithm can meet the real requirements in terms of efficiency and quality...