Search

Comparing business process variants using event logs is a common use case in process mining. Existing techniques for process variant analysis detect statistically-significant differences between variants at the level of individual entities (such as process activities) and their relationships (e.g. directly-follows relations between activities). This may lead to a proliferation of differences due to the low level of granularity in which such differences are captured. This paper presents a novel approach to detect statistically-significant differences between variants at the level of entire process traces (i.e. sequences of directly-follows relations). The cornerstone of this approach is a technique to learn a directly-follows graph called mutual fingerprint from the event logs of the two variants. A mutual fingerprint is a lossless encoding of a set of traces and their duration using discrete wavelet transformation. This structure facilitates the understanding of statistical differences along the control-flow and performance dimensions. The approach has been evaluated using real-life event logs against two baselines. The results show that at a trace level, the baselines cannot always reveal the differences discovered by our approach, or can detect spurious differences., This research is partly funded by the Australian Research Council (DP180102839) and Spanish funds MINECO and FEDER (TIN2017-86727-C2-1-R)., Peer Reviewed, Postprint (author's final draft)

The alignment of observed and modeled behavior is an essential element for organizations, since it opens the door for conformance checking and enhancement of processes. The state-of-the-art technique for computing alignments has exponential time and space complexity, hindering its applicability for medium and large instances. In this article, a novel approach is presented to tackle the challenge of computing an alignment for large-problem instances that correspond to well-formed process models. Given an observed trace, first it uses a novel replay technique to find an initial candidate trace in the model. Then a local search framework is applied to try to improve the alignment until no further improvement is possible. The implementation of the presented technique reveals a magnificent reduction both in computation time and in memory usage. Moreover, although the proposed technique does not guarantee the derivation of an alignment with minimal cost, the experiments show that in practice the quality of the obtained solutions is close to optimal., This work has been supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R., Peer Reviewed, Postprint (author's final draft)

Relating event data and process models is becoming an important element for organizations. This paper presents a novel approach for aligning traces and process models. The approach is based on the structural theory of Petri nets (the marking equation), applied over an unfolding of the initial process model. Given an observed trace, the approach adopts an iterative optimization mechanism on top of the unfolding, computing at each iteration part of the resulting alignment. In contrast to the previous work that is primarily grounded in the marking equation, this approach is guaranteed to provide real solutions, and tries to mimic as much as possible the events observed in the trace. Experiments witness the significance of this approach both in quality and execution time perspectives., Peer Reviewed, Postprint (author's final draft)

The alignment of observed and modeled behavior is an essential aid for organizations, since it opens the door for root-cause analysis and enhancement of processes. The state-of-the-art technique for computing alignments has exponential time and space complexity, hindering its applicability for medium and large instances. Moreover, the fact that there may be multiple optimal alignments is perceived as a negative situation, while in reality it may provide a more comprehensive picture of the model’s explanation of observed behavior, from which other techniques may benefit. This paper presents a novel evolutionary technique for approximating multiple optimal alignments. Remarkably, the memory footprint of the proposed technique is bounded, representing an unprecedented guarantee with respect to the state-of-the-art methods for the same task. The technique is implemented into a tool, and experiments on several benchmarks are provided., Peer Reviewed, Postprint (author's final draft)

Conformance Checking is a new research discipline devoted to identify deviations between business process models and their real executions. Identifying deviations boils down to the notion of alignment conceptually. An alignment quantifies to what degree a process model can imitate what happened in its observed behavior, i.e., an event log. Accordingly, an optimal alignment is the best combination by which the process model can imitate the corresponding observed behavior. The state of the art technique for alignment computation has exponential time and space complexity, hindering its applicability for medium and large instances. The main aim of this thesis is to propose light and efficient methods for alignment computation. By finding a suitable trade-off between computation time, memory consumption and optimality, a familly of techniques is proposed such that depending on the input assumptions and required guarantees, a user can select the right technique for her particular problem. Generally speaking, the methods presented in this thesis can be categorized as: - Classical approaches: These techniques exploit Integer Linear Programming (ILP), as well as structural theory of Petri nets, to formulate alignment computation as an optimization of a set of linear equations. A modification to this strategy which trades-off between complexity and quality is to integrate it with state of the art approach. - Heuristic approaches: These techniques take advantages of heuristic functions to explore the search space of alignments, to find the optimal one(s). This can be done by obtaining an initial solution, and iteratively improving it until saturation or reaching a certain criterion. Another contribution is by adopting a Genetic Algorithm with well specific designed operators, by which exploration of the corresponding search space can be speed up toward the best solution(s). - Model reduction: An alternative way to boost the effectiveness of alignment computation is by reducing, Conformance checking és una nova disciplina dedicada a identificar desviacions entre els models de processos de negoci i les seves execucions reals. Identificar les desviacions porta directament al concepte d'alineament. Un alineament quantifica el grau en que un model de procés pot imitar el que va passar en el seu comportament observat, és a dir, un registre d'esdeveniments. En conseqüència, una alineament òptim és la millor combinació per la qual el model de procés pot imitar el comportament observat. La tècnica de referència per a la computació d'alineaments té una complexitat exponencial, el que dificulta la seva aplicabilitat per a casos mitjans o grans. L'objectiu principal d'aquesta tesi és proposar mètodes eficients per a la computació d'alineaments. En trobar un punt raonable entre el temps d'execució, el consum de memòria i la optimalitat, es proposa una família de tècniques de manera que, segons els supòsits d'entrada i les garanties requerides, un usuari pot seleccionar la tècnica adequada per al seu problema. En termes generals, els mètodes presentats en aquesta tesi es poden classificar com: Enfocaments clàssics: aquestes tècniques utilitzen la Programació Lineal Entera (anglès, ILP), així com la teoria estructural de les xarxes Petri, per realitzar la computació d'alineaments com una optimització d'un conjunt d'equacions lineals. Una modificació d'aquesta estratègia, que pondera la complexitat i la qualitat, és la d'integrar-la amb l'enfocament de referència. Aproximacions heurístiques: aquestes tècniques aprofiten funcions heurístiques per explorar l'espai de cerca d'alineaments, per trobar les solucions properes a l'òptim. Això es pot fer obtenint una solució inicial, que es millorarà iterativament fins a la saturació, o bé assolint un criteri determinat de convergència. Una altra contribució és l'adopció d'un algoritme evolutiu amb operadors específics, que permeten guiar l'exploració de l'espai de cerca corresponent cap a les millors solucions. R, Postprint (published version)

Certifying that a process model is aligned with the real process executions is perhaps the most desired feature a process model may have: aligned process models are crucial for organizations, since strategic decisions can be made easier on models instead of on plain data. In spite of its importance, the current algorithmic support for computing alignments is limited: either techniques that explicitly explore the model behavior (which may be worst-case exponential with respect to the model size), or heuristic approaches that cannot guarantee a solution, are the only alternatives. In this paper we propose a solution that sits right in the middle in the complexity spectrum of alignment techniques; it can always guarantee a solution, whose quality depends on the exploration depth used and local decisions taken at each step. We use linear algebraic techniques in combination with an iterative search which focuses on progressing towards a solution. The experiments show a clear reduction in the time required for reaching a solution, without sacrificing significantly the quality of the alignment obtained., Peer Reviewed, Postprint (author's final draft)

The alignment of observed and modeled behavior is a crucial problem in process mining, since it opens the door for conformance checking and enhancement of process models. The state of the art techniques for the computation of alignments rely on a full exploration of the combination of the model state space and the observed behavior (an event log), which hampers their applicability for large instances. This paper presents a fresh view to the alignment problem: the computation of alignments is casted as the resolution of Integer Linear Programming models, where the user can decide the granularity of the alignment steps. Moreover, a novel recursive strategy is used to split the problem into small pieces, exponentially reducing the complexity of the ILP models to be solved. The contributions of this paper represent a promising alternative to fight the inherent complexity of computing alignments for large instances., Peer Reviewed, Postprint (author's final draft)