DIG-DAG: pattern storage and search in an event flow

The search for patterns in a character string is easily done with a tool such as grep. In this article, we consider a flow of events characterized by a start and end date. Finding patterns in such a structure then becomes more complex. In order to efficiently perform this operation, we propose a new structure, called DIG-DAG (Directed Interval Graph - Directed Acyclic Graph). We show how to compactly build this structure when the flow is discovered on the fly. We then explain how to extract from the DIG-DAG the patterns that match a user's query. Finally, we illustrate the use of these algorithms on real traces from GSM networks. This article synthesizes two articles published in CNSM'2018 and MLN'2019.