TAGER: Transition-Labeled Graph Edit Distance Similarity Measure on Process Models

详细信息    查看全文

• 作者：Zixuan Wang (23)
  Lijie Wen (23)
  Jianmin Wang (23)
  Shuhao Wang (23)
  
• 关键词：Business Process Model ; Transition ; labeled Graph ; Edit Distance ; Behavioral Similarity
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：8841
• 期：1
• 页码：184-201
• 全文大小：318 KB
• 参考文献：1. Becker, M., Laue, R.: A comparative survey of business process similarity measures. Computers in Industry聽63(2), 148鈥?67 (2012) CrossRef
  2. Dijkman, R., Dumas, M., Garc铆a-Ba帽uelos, L.: Graph matching algorithms for business process model similarity search. In: Dayal, U., Eder, J., Koehler, J., Reijers, H.A. (eds.) BPM 2009. LNCS, vol.聽5701, pp. 48鈥?3. Springer, Heidelberg (2009) CrossRef
  3. Dijkman, R., Dumas, M., Dongen, B.V., K盲盲rik, R., Mendling, J.: Similarity of business process models: Metrics and evaluation. Information Systems聽36(2), 498鈥?16 (2011) CrossRef
  4. Kunze, M., Weske, M.: Metric trees for efficient similarity search in large process model repositories. In: Muehlen, M.z., Su, J. (eds.) BPM 2010 Workshops. LNBIP, vol.聽66, pp. 535鈥?46. Springer, Heidelberg (2011) CrossRef
  5. Messmer, B.T.: Efficient graph matching algorithms (1995)
  6. Murata, T.: Petri nets: Properties, analysis and applications. Proceedings of the IEEE聽77(4), 541鈥?80 (1989) CrossRef
  7. Petri, C.A.: Kommunikation mit automaten (1962)
  8. Rosemann, M.: Potential pitfalls of process modeling: part a. Business Process Management Journal聽12(2), 249鈥?54 (2006) CrossRef
  9. van der Aalst, W.M.P., ter Hofstede, A.H.M., Weske, M.: Business process management: A survey. In: van der Aalst, W.M.P., ter Hofstede, A.H.M., Weske, M. (eds.) BPM 2003. LNCS, vol.聽2678, pp. 1鈥?2. Springer, Heidelberg (2003) CrossRef
  10. Verbeek, H.M.: Verification of wf-nets (2004)
  11. Wang, J., He, T., Wen, L., Wu, N., ter Hofstede, A.H.M., Su, J.: A behavioral similarity measure between labeled petri nets based on principal transition sequences. In: Meersman, R., Dillon, T.S., Herrero, P. (eds.) OTM 2010. LNCS, vol.聽6426, pp. 394鈥?01. Springer, Heidelberg (2010) CrossRef
  12. Wang, J., Jin, T., Wong, R.K., Wen, L.: Querying business process model repositories. World Wide Web, 1鈥?8 (2013)
  13. Wang, S., Wen, L., Wei, D., Wang, J., Yan, Z.: Ssdt-matrix based behavioral similarity algorithm for process models. Computer Integrated Manufacturing System聽19(8), 1822鈥?831 (2013)
  14. Weidlich, M., Mendling, J., Weske, M.: Efficient consistency measurement based on behavioral profiles of process models. IEEE Transactions on Software Engineering聽37(3), 410鈥?29 (2011) CrossRef
  15. Zha, H., Wang, J., Wen, L., Wang, C., Sun, J.: A workflow net similarity measure based on transition adjacency relations. Computers in Industry聽61(5), 463鈥?71 (2010) CrossRef
  
• 作者单位：Zixuan Wang (23)
  Lijie Wen (23)
  Jianmin Wang (23)
  Shuhao Wang (23)
  
  23. School of Software, Tsinghua University, Beijing, 100084, P.R. China
  
• ISSN：1611-3349

文摘

Although several approaches have been proposed to compute the similarity between process models, they have various limitations. We propose an approach named TAGER (Transition-lAbeled Graph Edit distance similarity MeasuRe) to compute the similarity based on the edit distance between coverability graphs. As the coverability graph represents the behavior of a Petri net well, TAGER, based on it, has a high precise computation. Besides, the T-labeled graphs (an isomorphic graph of the coverability graph) of models are independent, so TAGER can be used as the index for searching process models in a repository. We evaluate TAGER from efficiency and quality perspectives. The results show that TAGER meets all the seven criteria and the distance metric requirement that a good similarity algorithm should have. TAGER also balances the efficiency and precision well.