On the efficient application of Aho-Corasick algorithm in process mining
Andrey Konchagin, Anna Kalenkova
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Springer International Publishing | Published : 2018
In this paper we present an approach for searching sub-traces in event logs, generated by information systems. Our technique is heavily based on the Aho-Corasick algorithm, and extends it with simultaneous search on several event log traces. The computational complexity of the proposed approach was estimated. Moreover, the approach was implemented and verified on real-life event logs. It was shown that it allows to reduce the search time for event logs with a high proportion of similar traces.
Awarded by Moscow city Government
This work was supported by the Basic Research Program at the National Research University Higher School of Economics and funded by RFBR and Moscow city Government according to the Research project No 15-37-70008 "mol_a_mos".