A more efficient deterministic algorithm in process model discovery

Alpha is a basic deterministic discovery algorithm that has been enhanced by Alpha*, Alpha++ and Alpha#. Alpha does an analysis of place, transition, and firing locally on each trace in the event log, which causes the time complexity of Alpha to be high for large event logs. In this paper, the Alpha-Tree (Alpha-T) algorithm is proposed to enhance Alpha’s time complexity performance and quality of discovery. Based on generalized tuple pattern recognition (GTPR) inside the adjacency list tree (ALT) data structure, Alpha-T is able to simplify the tuple pattern analysis, resulting in a more efficient time complexity (O(t³)) compared to Alpha (O(t⁴)). Alpha-T reduces the time complexity by localizing the effect of the event log size to the preprocessing stage, which diminishes the number of steps in the discovery processing stage. Then within processing, Alpha-T does execution pattern of logic directly and induction in the places gateway, and make it have more dynamically pattern that produces more completeness and correctness model than other algorithms. Finally, in the post-processing stage, Alpha-T has a single graph structure, which reduces the complexity and memory space needed for workflow firing between place and transition.