Browsing by Author "Raun, Kristo"

Now showing 1 - 3 of 3
  • No Thumbnail Available
    Item
    C-3PA: Streaming Conformance, Confidence and Completeness in Prefix-Alignments
    (Springer, Cham, 2023) Raun, Kristo; Nielsen, Max; Burattin, Andrea; Awad, Ahmed
    The aim of streaming conformance checking is to find dis crepancies between process executions on streaming data and the refer ence process model. The state-of-the-art output from streaming confor mance checking is a prefix-alignment. However, current techniques that output a prefix-alignment are unable to handle warm-starting scenarios. Further, no indication is given of how close the trace is to termination—a highly relevant measure in a streaming setting. This paper introduces a novel approximate streaming conformance checking algorithm that enriches prefix-alignments with confidence and completeness measures. Empirical tests on synthetic and real-life datasets demonstrate that the new method outputs prefix-alignments that have a cost that is highly correlated with the output from the state of-the-art optimal prefix-alignments. Furthermore, the method is able to handle warm-starting scenarios and indicate the confidence level of the prefix-alignment. A stress test shows that the method is well-suited for fast-paced event streams.
  • No Thumbnail Available
    Item
    Efficient Approximate Conformance Checking Using Trie Data Structures
    (IEEE, 2021) Awad, Ahmed; Raun, Kristo; Weidlich, Matthias
    Conformance checking compares a process model and recorded executions of a process, i.e., a log of traces. To this end, state-of-the-art approaches compute an alignment between a trace and an execution sequence of the model. Since the construction of alignments is computationally expensive, approximation schemes have been developed to strike a balance between the efficiency and the accuracy of conformance checking. Specifically, conformance checking may rely only on so-called proxy behavior, a subset of the behavior of the model. However, the question how such proxy behavior shall be represented for efficient alignment computation has been largely neglected. In this paper, we contribute a new formulation of the proxy behavior derived from a model for approximate conformance checking. By encoding the proxy behavior using a trie data structure, we obtain a logarithmically reduced search space for alignment computation compared to a set-based representation. We show how our algorithm supports the definition of a budget for alignment computation and also augment it with strategies for meta-heuristic optimization and pruning of the search space. Evaluation experiments with five real-world event logs show that our approach reduces the runtime of alignment construction by two orders of magnitude with a modest estimation error.
  • No Thumbnail Available
    Item
    I Will Survive: An Event-driven Conformance Checking Approach Over Process Streams
    (ACM DIGITAL LIBRARY, 2023) Raun, Kristo; Tommassini, Riccardo; Awad, Ahmed
    Online conformance checking deals with finding discrepancies be tween real-life and modeled behavior on data streams. The current state-of-the-art output of online conformance checking is a prefix alignment, which is used for pinpointing the exact deviations in terms of the trace and the model while accommodating a trace’s unknown termination in an online setting. Current methods for producing prefix-alignments are computationally expensive and hinder the applicability in real-life settings. This paper introduces a new approximate algorithm – I Will Survive (IWS). The algorithm utilizes the trie data structure to improve the calculation speed, while remaining memory-efficient. Comparative analysis on real-life and synthetic datasets shows that the IWS algorithm can achieve an order of magnitude faster execution time while having a smaller error cost, compared to the current state of the art. In extreme cases, the IWS finds prefix alignments roughly three orders of magnitude faster than previous approximate methods. The IWS algorithm includes a discounted decay time setting for more efficient memory usage and a look ahead limit for improving computation time. Finally, the algorithm is stress tested for performance using a simulation of high-traffic event streams.