This post is by Alessandro Berti, Software Engineer in the Process And Data Science group at RWTH Aachen University. Contact him via email for further inquiries.
Process mining is a branch of data science that includes a wide set of different techniques for automated process discovery, compliance/conformance checking, process simulation and prediction. The tools support for process mining has developed in the recent years in different directions: standalone tools, libraries for the most known programming languages, cloud solutions that store and analyze event data. All of these require the support of different standards, numeric calculus and optimization techniques, visualizations. Examples are the XES standard (XML) for the storage of event logs, the support of Petri nets and their importing/exporting from PNML (XML) files, the inclusion of LP/ILP solvers for process discovery (ILP-based process discovery) and conformance checking (A* alignments).
The inclusion of a vast set of functionalities in the more advanced tools/libraries (like ProM 6.x or PM4Py) has therefore led to an uncontrollable growth in the amount of memory required to run the tool/library. As per now, simply opening ProM 6.9 requires more than 650 MB of RAM, and importing PM4Py along with its dependencies requires more than 80 MB of RAM. On the other hand, cloud solutions such as the Celonis IBC or MyInvenio require an active Internet connection for the transmission of event data and the delivery of process mining analysis/dashboards.
This cuts the possibility to apply process mining on the most numerous class of computers in the world: the microcontrollers. As example, a modern car contains from 30 to 70 microcontrollers. Microcontrollers are usually adopted to control the operational status of a system (for example, the acceleration, temperature, magnetic field, humidity). For minimizing idle/light sleep power consumption, these come with a very limited amount of RAM (usually from 32 KB to 512 KB) and a very low power CPU (examples are the Cortex M0/M4/M7 CPUs for microcontrollers). Applying existing process mining tools/libraries on these is simply impossible.
Hence, a new library (MicroPM4Py) is being developed in the MicroPython language (www.micropython.org), that is a complete reimplementation for microcontrollers of a basic set of features of Python 3.4. The aim of the MicroPython language is not being faster than the normal Python (indeed, Python is much faster than MicroPython for the same script) but to minimize the memory footprint of the application. The goal of MicroPM4Py is to enable some process mining features directly at the microcontroller level:
- Full support for Petri nets without invisible transitions: a memory-efficient data structure is deployed that supports the semantics of a Petri net, the verification of the fitness of a trace, PNML importing/exporting.
- Basic support (A1 import; A1 export) for the XES standard for event logs: the traces can be loaded from the XES event log with different modalities (full DFG; distinct variants; full list of traces in memory; iterator trace by trace).
- Basic support for importing/exporting logs in the CSV format.
- Basic support for process discovery (discovery of a DFG, DFG mining, Alpha Miner algorithm) on top of XES/CSV event logs
- Generation of the DOT (Graphviz) visualization of a DFG / Petri net.
All the data structures have been optimized in order to minimize the memory consumption. As example, the following table estimates the RAM occupation (in bytes) of the three log structures in MicroPM4Py reading the DFG from the XES; reading the variants; reading all the traces from the log. Generally, the numbers are competitive and among the most efficient XES importers ever done (remind the limitation: only the case ID and the activity is read).
| Log name | DFG obj size | Variants obj size | Loaded log obj size |
| running-example | 3200 | 1568 | 2016 |
| receipt | 17112 | 22072 | 213352 |
| roadtraffic | 10696 | 37984 | 19392280 |
| LevelA1.xes | 6456 | 16368 | 154792 |
| BPIC17.xes | 29240 | 7528144 | 11474448 |
| BPIC15_4.xes | 453552 | 488200 | 587656 |
| BPIC17 – Offer log.xes | 3768 | 2992 | 6051880 |
| BPIC13_incidents.xes | 2696 | 380216 | 1333200 |
| BPIC15_3.xes | 600304 | 600312 | 743656 |
| BPIC15_1.xes | 541824 | 534216 | 652696 |
| BPIC15_5.xes | 555776 | 589688 | 703712 |
| BPIC12.xes | 20664 | 1819848 | 3352352 |
| BPIC13_closed_problems.xes | 2320 | 33504 | 226856 |
| BPIC15_2.xes | 551656 | 457496 | 531176 |
| BPIC13_open_problems.xes | 1872 | 16096 | 122672 |
The following table estimates the memory usage of an use case of MicroPM4Py: from a log, the DFG is obtained and the DFG mining technique is applied to obtain a Petri net. Then, an iterator is created on the log, in order to iterate over the single traces of the log. The memory usage of the MicroPM4Py module and data structure is then measured. The following aspects are taken into account (estimations were done on a X86-64 Debian 9 with Miniconda Python 3.7):
- The maximum size of the iterator+current trace (in bytes)
- The size of the DFG-mined Petri net (in bytes)
- The size of the MicroPM4Py Python module (in bytes)
- An estimated overapproximated size (16 KB) of a kernel + Micropython interpeter running on a microcontroller (in bytes)
The values are summed to get an estimation of the memory usage of the application for such use case, for several real-life logs. Except for the BPIC 2015 logs, the memory allocation is always under 128 KB! 🙂
| Log name | Max XES iterable size | DFG mining net size | MicroPM4Py module size | MicroPython size (est.max.) | MAX EST. SIZE |
| running-example | 2512 | 6384 | 20624 | 16384 | 45904 |
| receipt | 6312 | 27328 | 20624 | 16384 | 70648 |
| roadtraffic | 3416 | 18104 | 20624 | 16384 | 58528 |
| LevelA1.xes | 3656 | 9952 | 20624 | 16384 | 50616 |
| BPIC17.xes | 6664 | 41352 | 20624 | 16384 | 85024 |
| BPIC15_4.xes | 49560 | 757680 | 20624 | 16384 | 844248 |
| BPIC17 – Offer log.xes | 2392 | 6760 | 20624 | 16384 | 46160 |
| BPIC13_incidents.xes | 2696 | 5352 | 20624 | 16384 | 45056 |
| BPIC15_3.xes | 49912 | 1084872 | 20624 | 16384 | 1171792 |
| BPIC15_1.xes | 51592 | 993800 | 20624 | 16384 | 1082400 |
| BPIC15_5.xes | 54048 | 1027648 | 20624 | 16384 | 1118704 |
| BPIC12.xes | 6368 | 30744 | 20624 | 16384 | 74120 |
| BPIC13_closed_problems.xes | 2056 | 5160 | 20624 | 16384 | 44224 |
| BPIC15_2.xes | 54080 | 1012512 | 20624 | 16384 | 1103600 |
| BPIC13_open_problems.xes | 1864 | 4480 | 20624 | 16384 | 43352 |
While it is impossible on such level (microcontrollers) to support the wide set of features of other tools, it is still possible to apply some process mining algorithms on top of microcontrollers. MicroPM4Py can also be deployed on old workstations or other kinds of low-power computers (such as the Raspberry Pis).
As future work, the library will include some other process models (e.g. transition systems, NFA, continuous time markov chains).
