Since the environment for businesses is becoming more competitive by the day, business organizations have to be more adaptive to environmental changes and are constantly in a process of optimization. Fundamental parts of these organizations are their business processes. Discovering and understanding the actual execution ow of the processes deployed in organizations is an important enabler for the management, analysis, and optimization of both, the processes and the business. This has become increasingly di cult since business processes are now often dynamically changing and may produce hundreds of events per second. The basis for this paper is the Constructs Competition Miner (CCM): A divide-and-conquer algorithm which discovers block-structured processes from event logs possibly consisting of exceptional behaviour. In this paper we propose a set of modi cations for the CCM to enable scalable dynamic business process discovery of a run-time process model from a stream of events. We describe the di erent modi cations and carry out an evaluation, investigating the behaviour of the algorithm on event streams of dynamically changing processes.
The success of modern organizations has become increasingly dependent on the
e ciency and performance of their employed business processes (BPs). These
processes dictate the execution order of singular tasks to achieve certain business
goals and hence represent fundamental parts of most organizations. In the
context of business process management, the recent emergence of Big Data yields
new challenges, e.g. more analytical possibilities but also additional run-time
constraints. An important discipline in this area is Process Discovery: It is
concerned with deriving process-related information from event logs and, thus,
enabling the business analyst to extract and understand the actual behaviour of
a business process. Even though they are now increasingly used in commercial
settings, many of the developed process discovery algorithms were designed to
work in a static fashion, e.g. as provided by the ProM framework [
With the focus on addressing the latter two of these challenges, we propose
in this paper modi cations for the Constructs Competition Miner (CCM) [
The remainder of this paper provides essential background information (Section 2), a discussion of related work (Section 3), a summarized description of the original CCM (Section 4), the modi cations that were carried out on top of the CCM to enable Scalable Dynamic Process Discovery (Section 5), an evaluation of the behaviour of the resulting algorithm for event streams of dynamically changing processes (Section 6), and an outlook of future work (Section 7).
Business Processes are an integral part of modern organizations, describing the
set of activities that need to be performed, their order of execution, and the
entities that execute them. Prominent BP examples are Order-to-Cash or
Procureto-Pay. According to Ko et al. BPs are de ned as "...a series or network of
valueadded activities, performed by their relevant roles or collaborators, to purposefully
achieve the common business goal" [
For a block-structured BP model it is furthermore required that the process
is hierarchically organised [
When a business process is automatically or semi-automatically executed with a BP execution engine, e.g. with a Business Process Management System (BPMS), an event log is produced, i.e. a all occurred events are logged and stored. These logs and their contained events may capture di erent aspects of a process execution, e.g. a di erent granularity of events are logged. In this paper however, we only focus on a minimal set of event features: In order to allow the discovery of the control- ow, every event is required to have a reference (1) to the associated process instance and (2) to the corresponding activity. Furthermore, we assume that the log contains exactly one event for each activity execution, i.e. activity lifecycle events are not regarded. All events resulting from the execution of the same process instance are captured in one trace. A trace is assumed to be independent from other traces, i.e. the execution order of a process instance is not in any way dependent on the execution of a second instance. Accordingly, an event e is represented by a pair e = (t; a) where t 2 N is the unique identi er of the trace and a 2 A is a unique reference to the executed activity.
The research area of Process Discovery is concerned with the extraction of
a business process model from event logs without using any a-priori
information [
A large number of process discovery algorithms exist, e.g. Inductive Miner [
However, of little importance for conventional process discovery algorithms
is their practicality with regards to an application during run-time: as de ned
in De nition 2 process discovery is a static method that analyses an event log
in its entirety. An alternative to this approach is the immediate processing of
events when they occur to information of an higher abstraction level in order to
enable a real-time analysis. This approach is called Complex Event Processing
(CEP): a method that deals with the event-driven behaviour of large, distributed
enterprise systems [
In the context of process discovery, an often used term for discovering
processes from event streams is Streaming Process Discovery. In [
The CCM as described in [
Algorithm 1 shows the conceptual methodology of the CCM algorithm in pseudocode. The CCM applies the divide-and-conquer paradigm and is implemented in a recursive fashion (see lines 7, 16, and 17). At the beginning getFootprintAndBuildConstruct is initially called for all involved activities (Am = A) with the process bp consisting of only a start and end element. The recursive function is rst creating a footprint fp from the given log L only considering the activities speci ed in set Am (at the beginning all involved activities). In a next step it will be decided which is the best construct to represent the behaviour captured by fp: (1) if the activity set Am only consists of one element, 2 A concept drift in this context is a behavioural change in the monitored process (a)tSequence (c)tParallel Source Source
A First it will be decided which of the single activity constructs (see bottom of Figure 2) ts best - the process bp will then be enriched with the new single activity construct (see line 11); (2) If the activity set Am contains more than one element, the suitability for each of the di erent constructs is calculated for any two activities x; y 2 Am based on "soft" constraints and behaviour approximations, e.g. activities a and b are in a strong Sequence relationship. The result of this calculation (line 13) is a number of suitability matrices, one for each construct. In the subsequent competition algorithm it is determined what is the best combination of (A) the construct type c 2 fSequence ; Choice ; Loop; :::g, and (B) the two subsets A rst and Asecond of Am with A rst [ Asecond = Am, A rst \ Asecond = fg, and A rst ; Asecond 6= fg, that best accommodate all x; y-pair relations of the corresponding matrix of construct c (line 14). The construct is then created and added to the existing process model bp (line 15), e.g. XOR-split and -join if the winning construct c was Choice. At this stage the recursive method calls will be executed to analyse and construct the respective behaviour for the subsets A rst and Asecond . The split up of the set Am continues in a recursive fashion until it cannot be divided any more, i.e. the set consists of a single activity (see case (1)). The process is completely constructed when the top recursive call returns.
Of particular interest for the transformation of the CCM algorithm to a
solution for scalable dynamic process discovery is the composition of the footprint
and its calculation from the log. As opposed to many other process discovery
algorithms, e.g. alpha-miner [
As established in Section 1, increasingly dynamic processes and the need for
immediate insight require current research in the domain of process mining to be
driven by a set of additional challenges. To address these challenges the concept
of Scalable Dynamic Process Discovery (SDPD), an interdisciplinary concept
employing principles of CEP, Process Discovery, and EDBPM, has been
introduced in [
As described in Section 4, the CCM is a static mining algorithm and has to be modi ed in order to enable SDPD. The result of this modi cations is called Dynamic CCM (DCCM). However, two restrictions for the DCCM with regards to the previously mentioned requirements of SDPD apply: (1) instead of discovering change on the BP perspectives control- ow, resources, and performance perspective, the DCCM described in this paper only focuses on discovering change in the control- ow, and (2) only change on the abstraction level of Dynamism is detected, i.e. whether or not the control- ow of the process has changed - the detection of change on the abstraction level of Re ectivity will not be supported by the DCCM. Additionally to the requirements of SDPD the DCCM features the following important aspects: (1) robust : if con icting, exceptional, or not representable behaviour occurs in the event stream, the DCCM does not fail but always picks the BP construct that best accommodates the recorded behaviour; (2) deterministic: the DCCM yields the exact same output BP for the same input stream of events.
The following modi cations were applied to the default CCM to create the DCCM and are described in more detail in the remainder of this section: 1. Splitting up the algorithm in two separate parts: one for dynamically updating the current footprint(s) complying to the scalability requirement, and one for interpreting the footprint into a BP model which has less restrictions with regards to its execution-time. 2. In the CCM the footprint is calculated in relation to all occurring traces.
This is not applicable for SDPD since the number of traces should not have an in uence on the execution-time of any component of an SDPD solution. For this reason the footprint has to be calculated in a dynamic fashion, i.e. an event-wise footprint update independent from the previously occurred number of events or traces. 3. The original behaviour of the CCM to carry out a footprint calculation for every subset that has been created by the divide-and-conquer approach is not optimal as then the DCCM would have to extract up to 2 n + 1 di erent footprints if only one activity was split-up from the main set for each recursion.4 This has been improved for the DCCM: for the most common constructs Choice and Sequence the sub-footprints are automatically derived from the parent footprint. 4. In rare cases it can happen that for every appearing event the state of the process is alternating between a number of di erent control- ows. This is caused by "footprint equivalent" BP models, i.e. two models are footprint equivalent if they both express the behaviour captured by the footprint. We introduce a measure which favours the last control- ow state in order to prevent the described behaviour.
The original CCM algorithm had to be split up into two separate parts in order to comply to the scalability requirement of SDPD. A component triggered by the occurrence of a new event to update the dynamic footprint and a component decoupled from the event processing which interprets the footprint into a BP Model. The conceptual methodology of the DCCM is depicted in Figure 3. The components, models, and functionality of the DCCM are described in the following: Events from the monitored Enterprise System, in which the end-to-end process is deployed, are fed into an event stream. The Footprint Update component is the receiver of these events and processes them directly into changes on the overall Dynamic Footprint which represents the abstract state of the monitored business process. If additional footprints for subsets of activities are required as speci ed by the Sub-Footprint Con gurations, e.g. if a Loop or Parallel construct was identi ed, then these sub-footprints are also updated (or created if they were not existent before). The Dynamic Footprint(s) can then at any point in time be compiled to a human-centric representation of the business process by the Footprint Interpretation component, i.e. the abstract footprint representation is interpreted into knowledge conforming to a block-structured BP model. In the DCCM this interpretation is scheduled dependent on how many new completed traces appeared, e.g. the footprint interpretation is executed once every 10 terminated traces. If the interpretation frequency m 2 N of the DCCM is set to 1 a footprint interpretation is executed for every single trace that terminated. The Footprint Interpretation algorithm works similar to the CCM algorithm shown in Algorithm 1; but instead of extracting footprints from a log (line 8), the modi ed algorithm requests the readily available Dynamic Footprint(s). If a sub-footprint is not yet available (e.g. at the beginning or if the process changed) the Footprint Interpretation speci es the request for a subfootprint in the Sub-Footprint Con gurations in the fashion of a feedback loop. 4 e.g. for A = fa; b; c; dg : (a; b; c; d) ! ((a; b; c); (d)) ! (((a); (b; c)); (d)) ! (((a); ((b); (c))); (d)), seven di erent footprints for sets fa; b; c; dg; fa; b; cg; fb; cg; fag; b ; fcg; fdg need to be created - (; ) denote the nested blocks that emerge while f g splitting the sets recursively.
Run-Time
Event Processing Events
SubFootprint Configs.
Footprint Update Dynamic Footprint
Scheduled Process
Discovery
Footprint Interpretation Business Process
Model Thus, Sub-Footprint Con gurations and Dynamic Footprints act as interfaces between the two components, Footprint Update and Footprint Interpretation. The Footprint Interpretation cannot continue to analyse the subsets if no subfootprint for these exist yet. In this case, usually occurring in the warm-up or transition phase, an intermediate BP model is created with activities containing all elements of the unresolved sets as depicted in Figure 4.
The Footprint Update component processes events to changes in the Dynamic Footprint, i.e. updates the abstract representation of the process state. The original footprint extraction of the CCM algorithm calculates all values in relation to the number of occurred traces, i.e. every trace's in uence on the footprint is 1 equal: jtracesj . To comply to the scalability requirement of SDPD the footprint update calculation should only take a xed amount of time, independent from the total number of previously occurred events or traces. An increase of the total number of involved activities can cause, however, a linear increase of the execution-time due to the recalculation of the relations between the occurred activity and, in the worst case, all other activities. The independence from previous traces is the reason the footprint is calculated in a dynamic fashion, i.e. the dynamic footprint is incrementally updated in a way that older events "age" and thus have less in uence than more recent events.
The ageing approach that is utilized in the Footprint Update of the DCCM is the creation of an individual trace footprint 5 (TFP ) for each trace and add it multiplied by the trace in uence factor tif 2 R to the current dynamic overall footprint (DFP ) multiplied by 1 tif , e.g. for tif = 0:01: 5 the occurrence values for activities as well as the global relations (see end of Section 4) are represented in the trace footprint by absolute statements true 1 if it occurred and false 0 if not 1 DFP = 0:01 TFP + 0:99 DFP . That means, a trace footprint TFP i has at the beginning the in uence of 0:01, after another TFP i+1 has been added the in uence of TFP i decreases to 0:01 0:99, and after another 0:01 0:992 and so on. By applying this incremental method, older TFP are losing in uence in the overall dynamic footprint. Figure 5 shows how the in uence of a trace is dependent on its "age": If tif = 0:1, the in uence of a trace that appeared 60 traces ago became almost irrelevant. At the same time if tif = 0:01 the in uence of a trace of the same age is still a little more than half of its initial in uence when it rst appeared. Essentially, the purpose of the trace in uence factor tif is to con gure the "memory" and adaptation rate of the footprint update component.
Another important dynamism feature that had to be implemented was the possibility to add an activity that has not appeared before. A new activity is rst recorded in the respective trace footprint. When the trace is terminated it will be added to the overall footprint in which it is not contained yet. The factored summation of both footprints to build the new dynamic footprint is carried out by assuming that a not previously in the dynamic overall footprint contained relation value is 0. An exception of this behaviour is the "warm-up" phase of the Footprint Update, i.e. if the amount of occurred traces is < t1if then the in uence of the dynamic footprint is jtjrtarcaecsejs+j 1 and of the trace footprint jtjrtarcaecsejs+j 1 . For instance if tif = 0:01 and jtracesj = 9 then is a new dynamic footprint calculated with DFP 10 = 110 TFP + 190 DFP 9 and for the next trace DFP 11 = 111 TFP + 1101 DFP 9. Because of this implementation the "warm-up" phase of the Footprint Update could be drastically reduced, i.e. processes were already completely discovered a few traces after the start of the monitoring.
Furthermore, activities that do not appear any more during operation should be removed from the dynamic footprint. This was implemented in the DCCM in the following way: If the occurrence once value of an activity drops below a removal threshold tr 2 R; tr < tif it will be removed from the dynamic footprint, i.e. all values and relations to other activities are discarded.
The fact that especially many Choice and Sequence constructs are present in common business processes, motivates an automated sub-footprint creation in the Footprint Interpretation based on the parent footprint rather then creating the sub-footprint from the event stream. This step helps to decrease the execution-time of the Footprint Update and was achieved by introducing an extra relation to the footprint6 - the direct neighbours relation as used by other mining algorithms (see Section 3). In the Footprint Interpretation this relation is then used for creating the respective sub-footprints for Sequence and Choice constructs but not for identifying BP constructs since the direct neighbours relation does not represent a global relation between activities. 5.3 Modi cations in the Footprint Interpretation Component As analysed in the beginning of this section, the original behaviour of the CCM to retrieve a sub-footprint for each subset that has been created by the divideand-conquer approach is not optimal. This is why, in the Footprint Interpretation the DCCM calculates the sub-footprints for the most common constructs, Choice and Sequence, from the available parent footprint: (1) For the Choice construct the probability of the exclusive paths are calculated with p rst = Px2A rst Fel (x) and psecond = Px2Asecond Fel (x) with Fel (x) being the occurrences of x as rst element (see CCM footprint description in Section 4). Then the relevant values of the parent footprint are copied into their respective new sub-footprints and normalized, i.e. multiplied with p 1rst and pse1cond , respectively. (2) The sub-footprints for the Sequence construct are similarly built, but without the normalization. Instead, the direct neighbours relation, now also part of the dynamic footprint, is used to calculate the new overall probabilities of the sub-footprints.
If two or more BP constructs are almost identically suitable for one and the same footprint, a slight change of the dynamic footprint might result in a di erently discovered BP. This may cause an alternating behaviour for the footprint interpretation, i.e. with almost every footprint update the result of the interpretation changes. This is undesirable behaviour which is why the competition algorithm was additionally modi ed as follows: All combinations of BP construct and subsets are by default penalized by a very small value, e.g. t1i0f , with the exception of the combination corresponding to the previously discovered BP model, hence reducing the risk of discovering alternating BP models.
The static CCM algorithm has been tested for its accuracy in [
In the remainder of this section early evaluation results of the DCCM are presented with regards to its capability of detecting certain basic changes of a real-time monitored business process. The basis of this evaluation is the example model in Figure 1 which is simulated and the resulting event stream fed into the DCCM. The CCM core is again con gured with its default noise parameters. Figure 6 shows the di erent values we want to measure. In the gure BP1 and BP2 are the business processes deployed in the monitored system and BP10 to BPn0 are the discovered models by DCCM. Additionally, BP1 and BP m0 are equivalent (BP1 BP m0) as well as BP2 and BPn0 (BP2 BPn0 ). For this part of the evaluation the following measures are of interest: { Warm-up: tw 2 N the amount of completed traces the DCCM needs as input at the start until the resulting model equivalently represents the process in the system, i.e. until BP1 BP m0. { Change Detection: td 2 N the amount of completed traces it takes to detect a certain change in the monitored process - from the point at which the process changed in the system to the point at which a di erent process was detected. When the change is detected the newly discovered process is usually not equivalent to the new process in the system BP2 but instead represents parts of the behaviour of both processes, BP1 and BP2. { Change Transition Period: ttr 2 N the amount of completed traces it takes to re-detect a changed process - from the point at which the process change was detected to the point at which the correct process representation was identi ed, i.e. until BP2 BPn0 . In this period multiple di erent business processes may be detected, each best representing the dynamic footprint at the respective point in time.
The rst test will evaluate how the DCCM behaves at the beginning when rst exposed to the event stream, more particularly, we want to determine tw. Figure 7 shows a selection of the rst few bp models extracted with trace inuence factor tif = 0:01 (see Section 5.2) and interpretation frequency m = 10, i.e. an interpretation is executed every 10 completed traces: After the rst trace the discovered process is a sequence re ecting the single trace that de nes the process at that point in time. At trace 10, which is the next scheduled footprint interpretation, the the algorithm discovered a Loop construct but cannot further analyse the subsets since the corresponding sub-footprint was not requested yet. Because of that, the feedback mechanism via the Sub-Footprint Con gurations is utilized by the Footprint Interpretation algorithm to register the creation of BP in system: Observed BP’: BP’1 - BPm’-1
BP1 tw
BPm’ td
BP2 BPm’+1 - BPn’-1 ttr # of traces
BP’n
Fig. 6. Measures for Detection of BP Change in System the missing sub-footprints. In the next scheduled run of the footprint interpretation, the Parallel construct of a; b; c; and d is discovered but again the analysis can not advance since a sub-footprint for the individual activity subsets has not been created yet. Activities e; f; g; and h seem to have appeared only in exactly this sequence until trace 20. Skipping one of the interpretation steps, we can see that at trace 40 the complete process has been mined, i.e. tw = 40.
In Figure 8 the development of tw for di erent m 2 f1; 2; 3; 6; 10g and tif 2 f0:001; 0:005; 0:01; 0:03g is depicted. The warm-up phase seems generally very short and not strongly in uenced by tif . For m = 10 the warm-up phase cannot be any shorter because the example process consists of a block-depth of 3: Parallel-in-Parallel-in-Loop, i.e. 3 subsequent requests for sub-footprints have to be made. This is an indicator that the modi cation e ort to shorten the warm-up phase had a positive e ect. A small decrease of tw can be noticed when increasing the trace in uence factor tif for small m, e.g. m 2 f1; 2; 3g.
In a second test we applied a change to the business process in the monitored system and are interested in the behaviour of the DCCM as well as in the change detection td and the change transition period ttr . Figure 9 shows the evolution of the discovered BP model with trace in uence factor tif = 0:01 and interpretation frequency m = 10. The change applied is the move of activity a from the position before the inner Parallel construct to the position behind it (see traces 5750 and 6310). The change was applied after 5753 traces. The footprint interpretation Fig. 9. The Evolution of the Discovered BP Model During a Change (Move of A) detects at the rst chance to discover the change (trace 5760) a concept drift and nds via competition the best tting construct: Parallel of a; c and b; d. The change detection td seemed to be independent from m and tif and was in all cases immediately recognized7. In Figure 10 the development of ttr for di erent m 2 f1; 10g and tif 2 f0:001; 0:005; 0:01; 0:03g is shown. The change transition period ttr was strongly in uenced by tif . If the value was very small (tif = 0:001) a change took up to almost 5000 traces in order to be re ected correctly in the discovered BP model. On the other hand if the trace in uence factor is chosen too high, e.g. tif = 0:05, not all variations of the process are included in the dynamic footprint which results in frequently changing/alternating discovered BP models. This is more likely to occur in large business processes containing rarely executed but still relevant behaviour.
Additionally, rst performance tests have been carried out for large arti cially produced processes (without change). For a randomly created and strongly nested process consisting of 100 activities the throughput of the footprint update was close to 100; 000 events per second and the footprint interpretation successfully discovered the process in a matter of seconds. Although not tested yet in a 7 Note, that other changes like deletion of an activity will take longer to recognise, since their existence still "linger" in the footprints "memory" for some time. real-life setting, the shown results indicate that the DCCM is very suitable for discovering and monitoring large enterprise processes.
In this paper we suggested modi cations for the Constructs Competition Miner
to enable Scalable Dynamic Process Discovery as proposed in [
The presented approach of Dynamic CCM (DCCM) is driven by the
requirements of real life industrial use cases provided by business partners within the
EU funded project TIMBUS. During the evaluation in the context of the
usecases it became apparent that this concept still has a number of limitations which
are considered to be future work: (1) Changes in the state of the business
process are usually detected almost immediately but it may take a long time until
the new state of the system is re ected appropriately in the extracted business
process model. This behaviour originates from the fact that the footprint and
the interpreted business process are in a sort of intermediate state for a while
until the in uence of the old version of the business process has disappeared.
Furthermore, the trace in uence factor tif is a pre-speci ed value but in
reality it is dependent on how many traces we need to regard to represent all the
"behaviour" of the model8. This in turn is strongly dependent on the amount
of activities in the model, since more activities usually mean more control- ow
behaviour. A possible future modi cation could be to have the in uence factor
dynamically adapt, i.e. similar to the self-adapting ageing proposed in [
Project partially funded by the European Commission under the 7th Framework Programme for research and technological development and demonstration activities under grant agreement 269940, TIMBUS project (http://timbusproject.net/).