基于过程结构树的流程间差别检测算法
|
摘要
流程模型差别检测是业务流程管理的关键技术之一.针对流程模型大多是由图结构建模,而流程图模型中有多种类型节点,因此经典的图编辑距离方法无法直接应用于流程差别检测的问题,提出了基于过程结构树的流程间差别检测算法.算法首先将流程模型转化为基于任务节点的过程结构树;然后采用分治思想快速获得流程间的最佳对等节点映射集合;最后基于节点映射集合生成一个近似最小代价编辑操作序列来表示两个流程的差别.实验结果表明,本文算法在准确率和效率两方面都能满足实际的应用需求.
Detecting difference between process models is one of the key technologies in business process management.The classical graph edit distance cannot directly be used to detect the difference between process models because there are many kinds of nodes in a process model. To solve this problem,we present an algorithm for detecting difference between process models based on process structure tree. Firstly, the process models are converted to their corresponding task based process structure trees( TPSTs). Then the divide and conquer strategy is used to obtain the optimal mapped node set between two TPSTs. Finally, an edit script with approximate minimum cost is generated based on the mapped nodes,which is considered as the difference between two process models. The experimental results show that this algorithm can meet the real requirements in terms of precision and efficiency.
Detecting difference between process models is one of the key technologies in business process management.The classical graph edit distance cannot directly be used to detect the difference between process models because there are many kinds of nodes in a process model. To solve this problem,we present an algorithm for detecting difference between process models based on process structure tree. Firstly, the process models are converted to their corresponding task based process structure trees( TPSTs). Then the divide and conquer strategy is used to obtain the optimal mapped node set between two TPSTs. Finally, an edit script with approximate minimum cost is generated based on the mapped nodes,which is considered as the difference between two process models. The experimental results show that this algorithm can meet the real requirements in terms of precision and efficiency.
引文
[1]WEBER B,RINDERLE S,REICHERT M.Change Patterns and Change Support Features in Process-Aw are Information Systems[M].Berlin Heidelberg Germany:Springer,2007,574-588.
[2]LA ROSA M,DUMAS M,UBA R.Merging business process models[A].On the M ove to M eaningful Internet Systems:Confederated International Conferences[C].Greece:DBLP,2010.96-113.
[3]POLYVYANYY A,VANHATALO J,VLZER H.Simplified computation and generalization of the refined process structure tree[J].International Workshop on Web Services and Formal M ethods,2010,6551(3):25-41.
[4]VANHATALO J,VLZER H,LEYMANN F.Faster and more focused control-flow analysis for business process models through SESE decomposition[J].Lecture Notes in Computer Science,2007,4749:43-55.
[5]ZHANG K,STATMAN R,SHASHA D.On the editing distance betw een unordered labeled trees[J].Information Processing Letters,1992,42(3):133-139.
[6]KUHN H W.The Hungarian method for the assignment problem[J].Naval Research Logistics,2005,52(1):7-21.
[7]DIJKMAN R.Diagnosing differences between business process models[A].International Conference on Business Process M anagement[C].Germany:Springer-Verlag,2008.261-277.
[8]DIJKMAN R.A classification of differences between similar business processes[A].Enterprise Distributed Object Computing Conference[C].IEEE,2007.37.
[9]LIU K,YAN Z,WANG Y,et al.Efficient syntactic process difference detection using flexible feature matching[A].Asia Pacific Business Process M anagement Conferences[C].Germany:Springer,2014.103-116.
[10]YAN Z,WANG Y,WEN L,et al.Efficient behavioral difference detection betw een business process models[A].Otm Conferences[C].Germany Berlin Heidelberg:Springer,2014.220-236.
[11]Küster J M,GERTH C,FRSTER A,et al.Detecting and resolving process model differences in the absence of a change log[A].International Conference on Business Process M anagement[C].USA:ACM,2008.244-260.
[12]CAO J,YAO Y,WANG Y.Mining change operations for w orkflow platform as a service[J].World Wide Web,2015,18(4):1071-1092.
[2]LA ROSA M,DUMAS M,UBA R.Merging business process models[A].On the M ove to M eaningful Internet Systems:Confederated International Conferences[C].Greece:DBLP,2010.96-113.
[3]POLYVYANYY A,VANHATALO J,VLZER H.Simplified computation and generalization of the refined process structure tree[J].International Workshop on Web Services and Formal M ethods,2010,6551(3):25-41.
[4]VANHATALO J,VLZER H,LEYMANN F.Faster and more focused control-flow analysis for business process models through SESE decomposition[J].Lecture Notes in Computer Science,2007,4749:43-55.
[5]ZHANG K,STATMAN R,SHASHA D.On the editing distance betw een unordered labeled trees[J].Information Processing Letters,1992,42(3):133-139.
[6]KUHN H W.The Hungarian method for the assignment problem[J].Naval Research Logistics,2005,52(1):7-21.
[7]DIJKMAN R.Diagnosing differences between business process models[A].International Conference on Business Process M anagement[C].Germany:Springer-Verlag,2008.261-277.
[8]DIJKMAN R.A classification of differences between similar business processes[A].Enterprise Distributed Object Computing Conference[C].IEEE,2007.37.
[9]LIU K,YAN Z,WANG Y,et al.Efficient syntactic process difference detection using flexible feature matching[A].Asia Pacific Business Process M anagement Conferences[C].Germany:Springer,2014.103-116.
[10]YAN Z,WANG Y,WEN L,et al.Efficient behavioral difference detection betw een business process models[A].Otm Conferences[C].Germany Berlin Heidelberg:Springer,2014.220-236.
[11]Küster J M,GERTH C,FRSTER A,et al.Detecting and resolving process model differences in the absence of a change log[A].International Conference on Business Process M anagement[C].USA:ACM,2008.244-260.
[12]CAO J,YAO Y,WANG Y.Mining change operations for w orkflow platform as a service[J].World Wide Web,2015,18(4):1071-1092.