Visualisation of the Alpha Algorithm

This algorithm was the first algorithm proposed for the construction of a Petri net from an event log. It has been built on a lot since to be generalised for more event log attributes and a variety of other complexities.

Process discovery begins with an event log which in its simplest form is a table with columns of activity, timestamp and case. If we sort by timestamp and then filter by case we can easily extract traces (individual end to end process instances) by just looking at the activity column.

We can generate a table that shows the pairwise relationship between activities.

While the footprint matrix is not strictly required to be defined mathematically for the algorithm, it is practically helpful for the implementation.

We need to define a set that contains one instance of each of the activities that occurred one or more times.

We need to define a set that contains one instance of each of the activities that occurred at the start of a trace one or more times.

We need to define a set that contains one instance of each of the activities that occurred at the end of a trace one or more times.

Now, we need to construct pairs of sets where:

Looking at the figure of all the related pairs of independent sets it is clear that many of them are combinations of the others. A non-maximal pair of sets is one that can be combined with another set to form a pair we already have. We can throw these away since they don't contain additional information.

Each one of the maximal pairs of sets we kept in step 5 of the algorithm now become a place/state in our Petri net. We create a transition/activity on the diagram for each activity in the set of unique activities.

Then, iterating over the pairs of sets that each correspond to a place/state in the Petri net:

Using the sets of start and end activities, we can finally link these to the start and end virtual places.