Calculation And Application Of High-level Edit Distance Between Workflows

Workflow or(business)process originated from office automation,plays an increasingly crucial role in information systems.With the development of cloud computing and big data,many applications which are related to workflow,such as Web services and cloud scientific workflows,are put into use.A large number of business processes are often stored as files in a workflow repository for management and being reused.Workflows often need to be adjusted and optimized in an open,dynamic and ever-changing environment such that many similar workflows are saved.For many engineering applications scenarios such as workflow retrieval,workflow comparison,workflow merging,it is necessary to identify the edit distance between workflows.And the workflow edit distance is determined by the minimum sequence of change operations which is to transfer a workflow into another.Among the existing methods for calculating the edit distance between workflows,most of them are based on low-level change primitives,such as adding or deleting an edge(node)in a workflow.However,it is difficult to understand and it cannot guarantee the soundness of the workflow.For this reason,some studies use high-level change operations to calculate the edit distance between workflows.A high-level change operation is a set of low-level change primitives,which is based on the business level and is easy to be understood.However,the edit distance between workflows has been proved to be an NP-hard problem,and the existing methods are deficient in scalability and applicability.This paper presents a new method combining A~*(A-star)algorithm and heuristic rules to calculate the edit distance between workflows.The main work of this paper is as follows:(1)We present an alternative approach which improves an exhaustive search algorithm.Our approach is based on the A-star algorithm,starting from the source workflow,it applies all possible moves to the source workflow such that a set of middle workflows is obtained.Evaluating the middle workflow status according to the heuristic function proposed in this paper to get the best position and then search from this position,until we found the target workflow.(2)Based on the aforementioned A-star algorithm,we propose a set of pruning rules to remove a large number of move operations that will not be in the optimal solution.Compared with the existing methods,our approach applies to workflows with loops and scales better with the workflow size.(3)In order to support the theory,we implemanted our method as a tool which is named as AHWCI and provided a visualization window for further research and pratical applications.(4)In purpose to verify the feasibility of prototype tools,this paper uses real workflow,and compared with the state-of-the-art approach to clarify the effectiveness and efficiency of the method.