Conference Proceedings

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

Abstract

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.

Grants

Awarded by Moscow city Government


Funding Acknowledgements

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".