Cache Enhanced Split-Point-Based Alignment Calculation

The execution of (business) processes often deviates from their behavioral specification (e.g., captured in a BPMN model). Conformance checking techniques evaluate whether event logs, i.e., data records capturing process behavior, and process models conform to each other. As such, conformance checking techniques provide insights into the correctness of the process execution. Alignments are conformance checking artifacts used to compute conformance metrics and, particularly, diagnostics. Several alignment algorithms exist, yet most existing methods solve an underlying search problem in which one typically calculates a heuristic to guide the search. Recently, a promising novel search approach was presented that reduces the overall number of heuristics required to solve the alignment problem. This paper extends this approach by proposing a caching strategy that improves the overall search speed and efficiency. We conducted a large set of experiments, confirming that the overall search efficiency increases significantly due to our contribution.