A Maximal Common Subgraph Based Method for Process Retrieval

Process retrieval is critical for workflow repository management. Structural similarity metric based on graph matching could achieve highest retrieval quality. Nowadays, researchers mainly adopt graph edit distance (GED) as the approach for comparing process models. However, the computation complexity of GED based methods are high and their cost functions depend heavily on the application domain. To overcome these shortcomings, we use the maximal common subgraph (MCS) approach instead and propose a depth-first search (DFS) code based method to implement the MCS. The minimum DFS codes are used to canonically label the process models and their fragments. By comparing the minimum DFS codes of the fragments, the maximal common subgraphs between the search model (i.e., a given process model or fragment) and the processes in the repository could be found. The experimental evaluations show that our method is feasible for real applications.