Graph-Based Token Replay for Online Conformance Checking
Conformance checking detects deviations in business process executions. An online detection method is needed to give immediate response to anticipate possible impacts. The state-of-the-art online conformance checking is the Prefix-Alignment (PA) technique. However, this technique has a limitation of...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2022-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9895396/ |
| _version_ | 1811204897806221312 |
|---|---|
| author | Indra Waspada Riyanarto Sarno Endang Siti Astuti Hanung Nindito Prasetyo Raden Budiraharjo |
| author_facet | Indra Waspada Riyanarto Sarno Endang Siti Astuti Hanung Nindito Prasetyo Raden Budiraharjo |
| author_sort | Indra Waspada |
| collection | DOAJ |
| description | Conformance checking detects deviations in business process executions. An online detection method is needed to give immediate response to anticipate possible impacts. The state-of-the-art online conformance checking is the Prefix-Alignment (PA) technique. However, this technique has a limitation of maintaining all of the administration data of cases in memory. In an online environment, the last event of a case is never known, whereas a PA requires last event information to release the case from memory to free up space for other cases. Hence, the PA does not meet the requirements of online conformance checking in processing infinite data of event stream without memory constraints. PA also has a complex state space search computation especially for large and complex process model references. In this paper, a Graph-Based Online Token Replay (GO-TR) method is proposed. This method takes benefit from Graph Database to adapts the Token-Based Replay (TBR) technique which has simple replay computation. We propose a Replay Image (RI) to store the case administration and develop a cypher based algorithm to simulate token replay on the RI to handle the event stream. We also propose a cypher-based algorithm to identify and replay invisible paths. The experiment results show that GO-TR has been successful in adapting TBR and solving the problem of wrong-placed tokens in TBR. GO-TR outperforms PA in yielding replay throughputs of relatively small amount of data in online conformance checking. In terms of memory usage, GO-TR shows its superiority over PA because it does not have memory limitations problems. |
| first_indexed | 2024-04-12T03:21:24Z |
| format | Article |
| id | doaj.art-0769075b649a4856907385b9e7bbcf97 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-04-12T03:21:24Z |
| publishDate | 2022-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-0769075b649a4856907385b9e7bbcf972022-12-22T03:49:53ZengIEEEIEEE Access2169-35362022-01-011010273710275210.1109/ACCESS.2022.32080989895396Graph-Based Token Replay for Online Conformance CheckingIndra Waspada0https://orcid.org/0000-0003-1817-2460Riyanarto Sarno1https://orcid.org/0000-0001-5373-660XEndang Siti Astuti2Hanung Nindito Prasetyo3https://orcid.org/0000-0001-5717-9337Raden Budiraharjo4Department of Informatics, Faculty of Intelligent Electrical and Informatics Technology, Institut Teknologi Sepuluh Nopember, Surabaya, IndonesiaDepartment of Informatics, Faculty of Intelligent Electrical and Informatics Technology, Institut Teknologi Sepuluh Nopember, Surabaya, IndonesiaDepartment of Business Administration, Brawijaya University, Malang, IndonesiaDepartment of Informatics, Faculty of Intelligent Electrical and Informatics Technology, Institut Teknologi Sepuluh Nopember, Surabaya, IndonesiaDepartment of Informatics, Faculty of Intelligent Electrical and Informatics Technology, Institut Teknologi Sepuluh Nopember, Surabaya, IndonesiaConformance checking detects deviations in business process executions. An online detection method is needed to give immediate response to anticipate possible impacts. The state-of-the-art online conformance checking is the Prefix-Alignment (PA) technique. However, this technique has a limitation of maintaining all of the administration data of cases in memory. In an online environment, the last event of a case is never known, whereas a PA requires last event information to release the case from memory to free up space for other cases. Hence, the PA does not meet the requirements of online conformance checking in processing infinite data of event stream without memory constraints. PA also has a complex state space search computation especially for large and complex process model references. In this paper, a Graph-Based Online Token Replay (GO-TR) method is proposed. This method takes benefit from Graph Database to adapts the Token-Based Replay (TBR) technique which has simple replay computation. We propose a Replay Image (RI) to store the case administration and develop a cypher based algorithm to simulate token replay on the RI to handle the event stream. We also propose a cypher-based algorithm to identify and replay invisible paths. The experiment results show that GO-TR has been successful in adapting TBR and solving the problem of wrong-placed tokens in TBR. GO-TR outperforms PA in yielding replay throughputs of relatively small amount of data in online conformance checking. In terms of memory usage, GO-TR shows its superiority over PA because it does not have memory limitations problems.https://ieeexplore.ieee.org/document/9895396/Conformance checkingevent streamgraph databasetoken-based replaymemory limitation |
| spellingShingle | Indra Waspada Riyanarto Sarno Endang Siti Astuti Hanung Nindito Prasetyo Raden Budiraharjo Graph-Based Token Replay for Online Conformance Checking IEEE Access Conformance checking event stream graph database token-based replay memory limitation |
| title | Graph-Based Token Replay for Online Conformance Checking |
| title_full | Graph-Based Token Replay for Online Conformance Checking |
| title_fullStr | Graph-Based Token Replay for Online Conformance Checking |
| title_full_unstemmed | Graph-Based Token Replay for Online Conformance Checking |
| title_short | Graph-Based Token Replay for Online Conformance Checking |
| title_sort | graph based token replay for online conformance checking |
| topic | Conformance checking event stream graph database token-based replay memory limitation |
| url | https://ieeexplore.ieee.org/document/9895396/ |
| work_keys_str_mv | AT indrawaspada graphbasedtokenreplayforonlineconformancechecking AT riyanartosarno graphbasedtokenreplayforonlineconformancechecking AT endangsitiastuti graphbasedtokenreplayforonlineconformancechecking AT hanungninditoprasetyo graphbasedtokenreplayforonlineconformancechecking AT radenbudiraharjo graphbasedtokenreplayforonlineconformancechecking |