On the efficient application of Aho-Corasick algorithm in process mining
In this paper we present an approach for searching sub-traces in event logs, generated by information systems. Our technique is heavily based on the Aho-Corasick algorithm, and extends it with simultaneous search on several event log traces. The computational complexity of the proposed approach was estimated. Moreover, the approach was implemented and verified on real-life event logs. It was shown that it allows to reduce the search time for event logs with a high proportion of similar traces.
Information systems in different domains, such as healthcare, tourism, banking, government and others, record operational behavior in the form of event logs. The process mining discipline offers dozens of techniques to discover, analyze, and visualize processes running in information systems, based on their event logs. The representational bias (the language for processes representation) plays an important role in the process discovery. In this work BPMN (Business Process Model and Notation) language was chosen as a representational bias and as a starting point for the process discovery, analysis and enhancement. BPMN is a common process modeling language, widely used by consultants, managers, analysts, and software engineers in various application domains. This work aims to bridge the gap between process mining techniques and BPMN. Existing techniques are often limited to a single perspective, e.g., just the control flow, subprocesses, or just resources. The goal of this work is to fully support the BPMN specification in the context of process mining and suggest a unified and integrated approach allowing for the discovery, analysis and enhancement of hierarchical high-level BPMN models. The approach proposed in this thesis is supported by tools that enable users to analyze discovered processes in BPMN-compliant tools and even automate their executions, using existing BPMN engines.
In this paper, we consider an approach to reverse engineering of UML sequence diagrams from event logs of information systems with a service-oriented architecture (SOA). UML sequence diagrams are graphical models quite suitable for representing interactions in heterogeneous component systems; in particular, the latter include increasingly popular SOA- based information systems. The approach deals with execution traces of SOA systems, represented in the form of event logs. Event logs are created by almost all modern information systems primarily for debug purposes. In contrast with conventional reverse engineering techniques that require source code for analysis, our approach for inferring UML sequence diagrams deals only with available logs and some heuristic knowledge. Our method consists of several stages of building UML sequence diagrams according to different perspectives set by the analyst. They include mapping log attributes to diagram elements, thereby determining a level of abstraction, grouping several components of a diagram and building hierarchical diagrams. We propose to group some of diagram components (messages and lifelines) based on regular expressions and build hierarchical diagrams using nested fragments. The approach is evaluated in a software prototype implemented as a Microsoft Visio add-in. The add-in builds a UML sequence diagram from a given event log according to a set of customizable settings.
Event logs collected by modern information and technical systems usually contain enough data for automated process models discovery. A variety of algorithms was developed for process models discovery, conformance checking, log to model alignment, comparison of process models, etc., nevertheless a quick analysis of ad-hoc selected parts of a journal still have not get a full-fledged implementation. This paper describes an ROLAP-based method of multidimensional event logs storage for process mining. The result of the analysis of the journal is visualized as directed graph representing the union of all possible event sequences, ranked by their occurrence probability. Our implementation allows the analyst to discover process models for sublogs defined by ad-hoc selection of criteria and value of occurrence probability
Process mining is a new technology, that provides us a variety of methods to discover, monitor and improve real processes by extracting knowledge from event logs. The two most prominent process mining tasks are process discovery and conformance checking. Conformance checking deals with diagnosing and quantifying discrepancies between observed behavior, represented in event logs, and modeled behavior. We present a method for checking conformance of abstract models and low-level event logs.
Process mining is a relatively new field of computer science which deals with process discovery and analysis based on event logs. In this work we consider the problem of discovering workflow nets with cancellation regions from event logs. Cancellations occur in the majority of real-life event logs. In spite of huge amount of process mining techniques little has been done on cancellation regions discovery. We show that the state-based region algorithm gives labeled Petri nets with overcomplicated control flow structure for logs with cancellations. We propose a novel method to discover cancellation regions from the transition systems built on event logs and show the way to construct equivalent workflow net with reset arcs to simplify the control flow structure.
Process mining aims to discover and analyze processes by extracting information from event logs. Process mining discovery algorithms deal with large data sets to learn automatically process models. As more event data become available there is the desire to learn larger and more complex process models. To tackle problems related to the readability of the resulting model and to ensure tractability, various decomposition methods have been proposed. This paper presents a novel decomposition approach for discovering more readable models from event logs on the basis of a priori knowledge about the event log structure: regular and special cases of the process execution are treated separately. The transition system, corresponding to a given event log, is decomposed into a regular part and a specific part. Then one of the known discovery algorithms is applied to both parts, and finally these models are combined into a single process model. It is proven, that the structural and behavioral properties of submodels are inherited by the unified process model. The proposed discovery algorithm is illustrated using a running example.
The issue contains papers accepted for presentation at the 10th Spring/Summer Young Researchers’ Colloquium on Software Engineering (SYRCoSE 2016) held in Krasnovidovo, Mozhaysky District, Moscow Oblast, Russia on May 30-June 1, 2016. The paper selection was based on originality and contributions to the field. Each paper was peer-reviewed by at least three referees.
The colloquium’s topics include programming languages, software development tools, embedded and cyber-physical systems, software and hardware verification, formal methods, information security, and others.