A New Similarity Search Approach on Process Models - Process-Aware Systems - page 16

Given any n1, m1 from correspondence set 1 and n2, m2 from correspondence
set 2, if n1, m1, n2, m2 satisfy: m1 is reachable from n1 and m2 is reachable
from n2. Then we consider correspondence set 1 is neighboring to correspondence
set 2.
Based on such a rule, we prune the correspondence sets by removing irrelevant
nodes from structural perspective and assemble the final retrieved patterns by
including the path nodes between correspondence sets.
What's more, in view of the time complexity, looking-up process in adjacency
matrixes is far lower than the most graph matching algorithms that are NP-
complete [10].
4 Evaluation
In this section, we first analyze the computational complexity and then present
an experimental evaluation of the approaches discussed above in terms of the
retrieval quality.
4.1 Computational Complexity
The proposed approach involves determining initial correspondence sets, pruning
the correspondence sets and assembling the final patterns. In the process of
determining the initial correspondence sets, nodes from model N are compared
to nodes in model M respectively, which leads to a complexity of O( n × m ),
where n,m is the number of nodes in model N and model M. As the basis of
our pruning process, we need to construct adjacency matrixes once for all, so
its complexity is not our big concern. The pruning process can be carried out
via a finite number of look-ups in the adjacency matrixes. One look-up step has
complexity of O(1). In the final part, we assembly the final patterns by including
the path nodes in-between the correspondence sets. These path nodes are already
stored when checking the correspondence sets are reachable to each other.
4.2 Experimental Setup
In this paper, we utilize the four process models shown in Figure 1 as our exper-
imental dataset. On average each model contains 16 nodes with a minimum of 9
and a maximum of 22. We randomly pick up Process (b) as the target model and
apply both Approach A and Approach B onto three process model pairs, i.e.,
Process (a) and (b), Process (c) and (b), Process (d) and (b). In constructing the
correspondence sets, we omit those node pair with similarity score lower than
half of the highest score in the set.
In the experiment, we applied both approaches to the three process model
pairs respectively. The results are recorded in Table 2. With comparison to the
gold standard in Figure 2-4, we drew out the retrieval quality of each approach,
as shown in Table 3.