Study On An Efficient Approach To Repair The Missing-order Event Logs Based On Process Models

Event logs record the execution information for different kinds of systems.The order information in a sequence indicates the logical relation and firing succession between events.However,with various issues raised by systems or manipulation,events may be recorded in a wrong order,which is called missing order.Without recovering missing order issues,applications such as provenance analysis or complex event processing built on event data may get paralyzed.A basic method for recovering an event log is to enumerate all the possible sequences and find the best recovery solution.Although it can handle almost every kind of recovery problems such as missing events and missing order,it doesn't give a shot on efficiency.In this paper,we study the efficient techniques for recovering missing order in a sequence(i.e.,efficient recovery of missing order,Etremo for short).According to the theoretical results,the recovery problem is proved to be NP-hard.We use an unfolding technique to simplify the behavioral analysis of process specifications.Three advanced strategical rules are developed to improve the efficiency.The experimental results demon-strate that our recovery approach significantly outperforms the state-of-the-art technique for up to 4-5 orders of magnitudes improvement in time costs.The main contributions are summarized as follows:1.we give a proof on the NP-hardness of finding the recovery of missing order in general settings,2.we propose a linear time algorithm with backtracking for the recovery on causal nets and branching nets(available for both free-choice and non-free-choice nets),3.we propose an efficient algorithm with backtracking for the recovery on specifica-tions with complex iterative routing structures,4.we show the experimental evaluation on real and synthetic data.