Querying Similar Process Models Based on the Hungarian Algorithm

Abstract

The structural similarity between two process models is usually considered as the main measurement for ranking the process models for a given query model. Current process query methods are inefficient since too many expensive computations of the graph edit distance are involved. To address this issue, using Petri-net as the modeling method, this paper presents the Hungarian algorithm based similarity query method. Unlike previous work where the non-task nodes (i.e., place nodes in the Petri-net) were lightly studied or even ignored, we think these non-task nodes also play an essential role in measuring the structural similarity between process models. First, we extract the context for each place and define the similarity for a pair of place nodes that are from different process models from two perspectives: commonality and the graph edit distance. Then, the place mapping is transformed to classical assignment problem that can be solved by Hungarian algorithm efficiently. Furthermore, we propose a new process similarity measurement on the basis of the place similarity. The extensive experimental evaluation shows that our Hungarian based methods outperform the baseline algorithm in both retrieval quality and query response time.