Search

Complex event processing (CEP) evaluates queries over streams of event data to detect situations of interest. If the event data are produced by geographically distributed sources, CEP may exploit in-network processing that distributes the evaluation of a query among the nodes of a network. To this end, a query is modularized and individual query operators are assigned to nodes, especially those that act as data sources. Existing solutions for such operator placement, however, are limited in that they assume all query results to be gathered at one designated node, commonly referred to as a sink. Hence, existing techniques postulate a hierarchical structure of the network that generates and processes the event data. This largely neglects the optimisation potential that stems from truly decentralised query evaluation with potentially many sinks. To address this gap, in this paper, we propose Multi-Sink Evaluation (MuSE) graphs as a formal computational model to evaluate common CEP queries in a decentralised manner. We further prove the completeness of query evaluation under this model. Striving for distributed CEP that can scale to large volumes of high-frequency event streams, we show how to reason on the network costs induced by distributed query evaluation and prune inefficient query execution plans. As such, our work lays the foundation for distributed CEP that is both, sound and efficient. [ABSTRACT FROM AUTHOR]

Analysing performance of business processes is an important vehicle to improve their operation. Specifically, an accurate assessment of sojourn times and remaining times enables bottleneck analysis and resource planning. Recently, methods to create respective performance models from event logs have been proposed. These works have several limitations, though: They either consider control-flow and performance information separately, or rely on an ad-hoc selection of temporal relations between events. In this paper, we introduce the Temporal Network Representation (TNR) of a log. It is based on Allen's interval algebra, comprises the pairwise temporal relations for activity executions, and potentially incorporates the context in which these relations have been observed. We demonstrate the usefulness of the TNR for detecting (unrecorded) delays and for probabilistic mining of variants when modelling the performance of a process. In order to compare different models from the performance perspective, we further develop a framework for measuring performance fitness. Under this framework, TNR-based process discovery is guaranteed to dominate existing techniques in measuring performance characteristics of a process. In addition, we show how contextual information in terms of the congestion levels of the process can be mined in order to further improve capabilities for performance analysis. To illustrate the practical value of the proposed models, we evaluate our approaches with three real-life datasets. Our experiments show that the TNR yields an improvement in performance fitness over state-of-the-art algorithms, while congestion learning is able to accurately reconstruct congestion levels from event data. [ABSTRACT FROM AUTHOR]

Data models capture the structure and characteristic properties of data entities, e.g., in terms of a database schema or an ontology. They are the backbone of diverse applications, reaching from information integration, through peer-to-peer systems and electronic commerce to social networking. Many of these applications involve models of diverse data sources. Effective utilisation and evolution of data models, therefore, calls for matching techniques that generate correspondences between their elements. Various such matching tools have been developed in the past. Yet, their results are often incomplete or erroneous, and thus need to be reconciled, i.e., validated by an expert. This paper analyses the reconciliation process in the presence of large collections of data models, where the network induced by generated correspondences shall meet consistency expectations in terms of integrity constraints. We specifically focus on how to handle data models that show some internal structure and potentially differ in terms of their assumed level of abstraction. We argue that such a setting calls for a probabilistic model of integrity constraints, for which satisfaction is preferred, but not required. In this work, we present a model for probabilistic constraints that enables reasoning on the correctness of individual correspondences within a network of data models, in order to guide an expert in the validation process. To support pay-as-you-go reconciliation, we also show how to construct a set of high-quality correspondences, even if an expert validates only a subset of all generated correspondences. We demonstrate the efficiency of our techniques for real-world datasets comprising database schemas and ontologies from various application domains. • A reconciliation process for a network of data models with integrity constraints. • A wide range of integrity constraints is handled for different data models. • The computation of proposed probabilistic model is scalable. • The proposed expert guidance saves about half of effort budgets. • The proposed instantiation technique increases quality up to 20%. [ABSTRACT FROM AUTHOR]

Service processes, for example in transportation, telecommunications or the health sector, are the backbone of today׳s economies. Conceptual models of service processes enable operational analysis that supports, e.g., resource provisioning or delay prediction. In the presence of event logs containing recorded traces of process execution, such operational models can be mined automatically. In this work, we target the analysis of resource-driven, scheduled processes based on event logs. We focus on processes for which there exists a pre-defined assignment of activity instances to resources that execute activities. Specifically, we approach the questions of conformance checking ( how to assess the conformance of the schedule and the actual process execution ) and performance improvement ( how to improve the operational process performance ). The first question is addressed based on a queueing network for both the schedule and the actual process execution. Based on these models, we detect operational deviations and then apply statistical inference and similarity measures to validate the scheduling assumptions, thereby identifying root-causes for these deviations. These results are the starting point for our technique to improve the operational performance. It suggests adaptations of the scheduling policy of the service process to decrease the tardiness (non-punctuality) and lower the flow time. We demonstrate the value of our approach based on a real-world dataset comprising clinical pathways of an outpatient clinic that have been recorded by a real-time location system (RTLS). Our results indicate that the presented technique enables localization of operational bottlenecks along with their root-causes, while our improvement technique yields a decrease in median tardiness and flow time by more than 20%. [ABSTRACT FROM AUTHOR]

Information systems have been widely adopted to support service processes in various domains, e.g., in the telecommunication, finance, and health sectors. Information recorded by systems during the operation of these processes provides an angle for operational process analysis, commonly referred to as process mining. In this work, we establish a queueing perspective in process mining to address the online delay prediction problem, which refers to the time that the execution of an activity for a running instance of a service process is delayed due to queueing effects. We present predictors that treat queues as first-class citizens and either enhance existing regression-based techniques for process mining or are directly grounded in queueing theory. In particular, our predictors target multi-class service processes, in which requests are classified by a type that influences their processing. Further, we introduce queue mining techniques that derive the predictors from event logs recorded by an information system during process execution. Our evaluation based on large real-world datasets, from the telecommunications and financial sectors, shows that our techniques yield accurate online predictions of case delay and drastically improve over predictors neglecting the queueing perspective. [ABSTRACT FROM AUTHOR]

A growing number of enterprises use complex event processing for monitoring and controlling their operations, while business process models are used to document working procedures. In this work, we propose a comprehensive method for complex event processing optimization using business process models. Our proposed method is based on the extraction of behaviorial constraints that are used, in turn, to rewrite patterns for event detection, and select and transform execution plans. We offer a set of rewriting rules that is shown to be complete with respect to the all, seq, and any patterns. The effectiveness of our method is demonstrated in an experimental evaluation with a large number of processes from an insurance company. We illustrate that the proposed optimization leads to significant savings in query processing. By integrating the optimization in state-of-the-art systems for event pattern matching, we demonstrate that these savings materialize in different technical infrastructures and can be combined with existing optimization techniques. [ABSTRACT FROM AUTHOR]

Abstract: Process-aware information systems typically involve various kinds of process stakeholders. That, in turn, leads to multiple process models that capture a common process from different perspectives and at different levels of abstraction. In order to guarantee a certain degree of uniformity, the consistency of such related process models is evaluated using formal criteria. However, it is unclear how modelling experts assess the consistency between process models, and which kind of notion they perceive to be appropriate. In this paper, we focus on control flow aspects and investigate the adequacy of consistency notions. In particular, we report findings from an online experiment, which allows us to compare in how far trace equivalence and two notions based on behavioural profiles approximate expert perceptions on consistency. Analysing 69 expert statements from process analysts, we conclude that trace equivalence is not suited to be applied as a consistency notion, whereas the notions based on behavioural profiles approximate the perceived consistency of our subjects significantly. Therefore, our contribution is an empirically founded answer to the correlation of behaviour consistency notions and the consistency perception by experts in the field of business process modelling. [Copyright &y& Elsevier]

Abstract: Process compliance measurement is getting increasing attention in companies due to stricter legal requirements and market pressure for operational excellence. In order to judge on compliance of the business processing, the degree of behavioural deviation of a case, i.e., an observed execution sequence, is quantified with respect to a process model (referred to as fitness, or recall). Recently, different compliance measures have been proposed. Still, nearly all of them are grounded on state-based techniques and the trace equivalence criterion, in particular. As a consequence, these approaches have to deal with the state explosion problem. In this paper, we argue that a behavioural abstraction may be leveraged to measure the compliance of a process log – a collection of cases. To this end, we utilise causal behavioural profiles that capture the behavioural characteristics of process models and cases, and can be computed efficiently. We propose different compliance measures based on these profiles, discuss the impact of noise in process logs on our measures, and show how diagnostic information on non-compliance is derived. As a validation, we report on findings of applying our approach in a case study with an international service provider. [Copyright &y& Elsevier]

Behavioral models capture operational principles of real-world or designed systems. Formally, each behavioral model defines the state space of a system, i.e., its states and the principles of state transitions. Such a model is the basis for analysis of the system's properties. In practice, state spaces of systems are immense, which results in huge computational complexity for their analysis. Behavioral models are typically described as executable graphs, whose execution semantics encodes a state space. The structure theory of behavioral models studies the relations between the structure of a model and the properties of its state space. In this article, we use the connectivity property of graphs to achieve an efficient and extensive discovery of the compositional structure of behavioral models; behavioral models get stepwise decomposed into components with clear structural characteristics and inter-component relations. At each decomposition step, the discovered compositional structure of a model is used for reasoning on properties of the whole state space of the system. The approach is exemplified by means of a concrete behavioral model and verification criterion. That is, we analyze workflow nets, a well-established tool for modeling behavior of distributed systems, with respect to the soundness property, a basic correctness property of workflow nets. Stepwise verification allows the detection of violations of the soundness property by inspecting small portions of a model, thereby considerably reducing the amount of work to be done to perform soundness checks. Besides formal results, we also report on findings from applying our approach to an industry model collection. [ABSTRACT FROM AUTHOR]

Event logs that are recorded by information systems provide a valuable starting point for the analysis of processes in various domains, reaching from healthcare, through logistics, to e-commerce. Specifically, behavioral patterns discovered from an event log enable operational insights, even in scenarios where process execution is rather unstructured and shows a large degree of variability. While such behavioral patterns capture frequently recurring episodes of a process’ behavior, they are not limited to sequential behavior but include notions of concurrency and exclusive choices. Existing algorithms to discover behavioral patterns are context-agnostic, though. They neglect the context in which patterns are observed, which severely limits the granularity at which behavioral regularities are identified. In this paper, we therefore present an approach to discover contextual behavioral patterns. Contextual patterns may be frequent solely in a certain partition of the event log, which enables fine-granular insights into the aspects that influence the conduct of a process. Moreover, we show how to analyze the discovered contextual behavioral patterns in terms of causal relations between context information and the patterns, as well as correlations between the patterns themselves. A complete analysis methodology leveraging all the tools presented in the paper and supplemented by interpretations guidelines is also provided. Finally, experiments with real-world event logs demonstrate the effectiveness of our techniques in obtaining fine-granular process insights. [ABSTRACT FROM AUTHOR]

Complex Event Processing (CEP) evaluates queries over event streams. However, once events are generated by nodes in a network, query evaluation requires the transmission of events between the nodes. Commonly, this is realized by sending events immediately upon their generation. Yet, to reduce network communication, query evaluation may incorporate pull-based communication, where events are buffered locally until they are requested by another node. Existing approaches for push–pull communication in distributed CEP, however, are limited in the expressiveness of pull requests and leverage solely the temporal constraints imposed by a query. In this paper, we propose a new evaluation model for distributed CEP, coined predicate-based push-pull (PrePP) plans. It includes pull requests that enable fine-granular filtering of events at their sources based on query predicates, thereby reducing event transmission. We formulate the problem of constructing PrePP plans with minimal transmission cost that also exploit opportunities for sharing of intermediate results among the queries of workload. However, the construction of optimal PrePP plans turns out to be NP-hard. We therefore propose algorithms to speed up the construction of PrePP plans, while producing near-optimal results. We illustrate the benefits of PrePP plans for distributed CEP in comprehensive experiments with synthetic as well as real-world data. Specifically, PrePP plans can reduce event transmission by up to three orders of magnitude over baseline techniques. • We propose a model for push–pull communication in distributed complex event processing (CEP) that leverages query predicates in pull requests. • Given a network of event sources and a query workload, we formulate the problem of constructing a predicate-based push–pull plan that minimizes transmission costs. • We present strategies to construct efficient evaluation plans under this model. • Experiments with synthetic and real-world data illustrate the benefits of the presented evaluation model for distributed CEP. [ABSTRACT FROM AUTHOR]

Highlights • A technique for performance-driven model reduction of GSPNs is proposed. • The technique relies on foldings that aggregate or eliminate performance information. • Foldings preserve model stability and have a bound for the introduced performance estimation error. • Given a budget for the estimation error, an optimal sequence of foldings can be found. Abstract Operational process models such as generalised stochastic Petri nets (GSPNs) are useful when answering performance questions about business processes (e.g. ‘how long will it take for a case to finish?’). Recently, methods for process mining have been developed to discover and enrich operational models based on a log of recorded executions of processes, which enables evidence-based process analysis. To avoid a bias due to infrequent execution paths, discovery algorithms strive for a balance between over-fitting and under-fitting regarding the originating log. However, state-of-the-art discovery algorithms address this balance solely for the control-flow dimension, neglecting the impact of their design choices in terms of performance measures. In this work, we thus offer a technique for controlled performance-driven model reduction of GSPNs, using structural simplification rules, namely foldings. We propose a set of foldings that aggregate or eliminate performance information. We further prove the soundness of these foldings in terms of stability preservation and provide bounds on the error that they introduce with respect to the original model. Furthermore, we show how to find an optimal sequence of simplification rules, such that their application yields a minimal model under a given error budget for performance estimation. We evaluate the approach with two real-world datasets from the healthcare and telecommunication domains, showing that model simplification indeed enables a controlled reduction of model size, while preserving performance metrics with respect to the original model. Moreover, we show that aggregation dominates elimination when abstracting performance models by preventing under-fitting due to information loss. [ABSTRACT FROM AUTHOR]

Event logs that originate from information systems enable comprehensive analysis of business processes. These logs serve as the starting point for the discovery of process models or the analysis of conformance of a log with a given specification. However, logs potentially contain personal information about individuals involved in process execution. In this paper, we therefore address the risk of privacy attacks on event logs. Specifically, we rely on group-based privacy guarantees instead of noise insertion in order to enable anonymization without adding new behaviour to the log. To this end, we propose two new algorithms for event log sanitization that provide privacy guarantees in terms of k-anonymity for the behavioural perspective of a process and t-closeness for sensitive information associated with events. The algorithms thereby avoid the disclosure of employee identities, prevent the identification of employee membership in the log, and preclude the characterization of employees based on sensitive attributes. Our algorithms overcome the limitations of an existing, greedy algorithm, providing users with a trade-off between computational complexity and the utility of the sanitized event log for downstream analysis. Our Experiments demonstrate that sanitization with our algorithms generates event logs of higher utility compared to the state of the art. [ABSTRACT FROM AUTHOR]

Event logs recorded during the execution of business processes provide a valuable starting point for operational monitoring, analysis, and improvement. Specifically, measures that quantify any deviation between the recorded operations and organizational goals enable the identification of operational issues. The data to compute such process-specific measures, commonly referred to as process performance indicators (PPIs), may contain personal data of individuals, though, which implies an inevitable risk of privacy intrusion that must be addressed. In this article, we target the privacy-aware computation of process performance indicators. To this end, we adopt tree-based definitions of PPIs according to the well-established PPINOT meta-model. For such a PPI, we design data release mechanisms for the functions in a PPI tree. Using a probabilistic formulation of the expected result of a privatized PPI, we further show how to determine the combination of release mechanisms that inflicts the least loss in utility. Moreover, given a set of PPIs, we provide an algorithmic framework to manage an inherent trade-off: Privatization may strive for maximal utility of each single PPI or for maximal reuse of privatized functions among all PPIs to use a privacy budget most effectively. Results from experiments with synthetic as well as real-world data indicate the general feasibility of privacy-aware PPIs and shed light on the trade-offs once a set of them is considered. • A framework for privatizing PPIs, and differentially private release mechanisms. • A method for automatically selecting the optimal instantiation of the framework. • An extension for forests of PPIs, optimizing privacy budget consumption. • Evaluations on synthetic and real data indicate the feasibility of the approaches. [ABSTRACT FROM AUTHOR]

The heterogeneity of today’s Web sources requires information retrieval (IR) systems to handle multi-modal queries. Such queries define a user’s information needs by different data modalities, such as keywords, hashtags, user profiles, and other media. Recent IR systems answer such a multi-modal query by considering it as a set of separate uni-modal queries. However, depending on the chosen operationalisation, such an approach is inefficient or ineffective. It either requires multiple passes over the data or leads to inaccuracies since the relations between data modalities are neglected in the relevance assessment. To mitigate these challenges, we present an IR system that has been designed to answer genuine multi-modal queries. It relies on a heterogeneous network embedding, so that features from diverse modalities can be incorporated when representing both, a query and the data over which it shall be evaluated. By embedding a query and the data in the same vector space, the relations across modalities are made explicit and exploited for more accurate query evaluation. At the same time, multi-modal queries are answered with a single pass over the data. An experimental evaluation using diverse real-world and synthetic datasets illustrates that our approach returns twice the amount of relevant information compared to baseline techniques, while scaling to large multi-modal databases. [ABSTRACT FROM AUTHOR]

Conformance checking enables organizations to automatically assess whether their business processes are executed according to their specification. State-of-the-art conformance checking algorithms perform this task by establishing alignments between behaviour recorded by IT systems to a process model capturing desired behaviour. While such alignments clearly highlight conformance issues, a major downside is that these algorithms scale exponentially in the size of both the event data, capturing recorded behaviour, and the process model used as input. At the same time, it is crucial to recognize that event data used for such analyses typically only relates to a specific interval of process execution rather than the entire history, meaning that the employed event data is inherently incomplete. Therefore, we argue that statistical methods allow one to obtain a proper understanding of the overall conformance of a process by considering only a fraction of the available data. In this paper, we therefore present a statistical approach to conformance checking that employs trace sampling and result approximation in order to derive conformance results in an efficient manner. The approach reduces the runtime significantly, while still providing guarantees on the accuracy of the estimated conformance result. We instantiate the general approach for different measures of the overall conformance of an event log and a process model, including fitness as a direct quantification of conformance as well as the distribution of deviations over activities and deviations related to contextual factors, such as the involved resources. Moreover, to increase the robustness of our approach, we elaborate on mechanisms to reveal biases in sampling procedures. Experiments with real-world and synthetic datasets show that our approach speeds up state-of-the-art conformance checking algorithms by up to three orders of magnitude, while largely maintaining the analysis accuracy. • We propose sample and approximation-based techniques for conformance checking. • Cover three types of conformance measures, fitness, deviations, and resources. • Experiments show that runtime efficiency is increased by orders of magnitude. [ABSTRACT FROM AUTHOR]

Crowdsourcing has been widely established as a means to enable human computation at large-scale, in particular for tasks that require manual labelling of large sets of data items. Answers obtained from heterogeneous crowd workers are aggregated to obtain a robust result. However, existing methods for answer aggregation are designed for discrete tasks, where answers are given as a single label per item. In this paper, we consider partial-agreement tasks that are common in many applications such as image tagging and document annotation, where items are assigned sets of labels. Common approaches for the aggregation of partial-agreement answers either (i) reduce the problem to several instances of an aggregation problem for discrete tasks or (ii) consider each label independently. Going beyond the state-of-the-art, we propose a novel Bayesian nonparametric model to aggregate the partial-agreement answers in a generic way. This model enables us to compute the consensus of partially-sound and partially-complete worker answers, while taking into account mutual relationships in labels and different answer sets. We also show how this model is instantiated for incremental learning, incorporating new answers from crowd workers as they arrive. An evaluation of our method using real-world datasets reveals that it consistently outperforms the state-of-the-art in terms of precision, recall, and robustness against faulty workers and data sparsity. [ABSTRACT FROM AUTHOR]

Urban mobility impacts urban life to a great extent. To enhance urban mobility, much research was invested in traveling time prediction: given an origin and destination, provide a passenger with an accurate estimation of how long a journey lasts. In this work, we investigate a novel combination of methods from Queueing Theory and Machine Learning in the prediction process. We propose a prediction engine that, given a scheduled bus journey (route) and a ‘source/destination’ pair, provides an estimate for the traveling time, while considering both historical data and real-time streams of information that are transmitted by buses. We propose a model that uses natural segmentation of the data according to bus stops and a set of predictors, some use learning while others are learning-free, to compute traveling time. Our empirical evaluation, using bus data that comes from the bus network in the city of Dublin, demonstrates that the snapshot principle, taken from Queueing Theory, works well yet suffers from outliers. To overcome the outliers problem, we use Machine Learning techniques as a regulator that assists in identifying outliers and propose prediction based on historical data. [ABSTRACT FROM AUTHOR]

Information systems support the execution of business processes. As part of that, data about process execution is recorded in event logs, which can be used to analyse the control-flow of the respective processes. However, such data may contain personal information on process stakeholders that is protected by privacy regulations. Process analysis based on event logs shall, therefore, employ anonymization techniques. In this paper, we introduce two approaches to anonymize the recorded control-flow of a process. Specifically, we present SaCoFa and SaPa as two techniques to anonymize the result of trace-variant queries over an event log. Unlike existing techniques that achieve differential privacy through randomized noise insertion, our techniques rely on noise insertion mechanisms that incorporate a process' semantics, thereby avoiding easily-recognizable noise. Both techniques take different design choices, though. SaCoFa anonymizes a trace-variant distribution directly, thereby focusing on utility preservation at the expense of potentially changing the number of a traces in the result considerably. SaPa, in turn, anonymizes a trace-variant distribution indirectly, through play-out of an anonymized directly-follows distribution. This way, the number of traces in the result is close to the original log, but the drop in utility may become larger due to using only local control-flow information. However, our experiments demonstrate that both approaches strike a better balance of preserving the utility of an event log compared to existing techniques. • We propose methods to anonymize the control-flow perspective of business processes. • The anonymized data is protected by differential privacy. • Our techniques provide better utility for process discovery than the state of the art. [ABSTRACT FROM AUTHOR]

Discovery plays a key role in data-driven analysis of business processes. The vast majority of contemporary discovery algorithms aims at the identification of control-flow constructs. The increase in data richness, however, enables discovery that incorporates the context of process execution beyond the control-flow perspective. A "control-flow first" approach, where context data serves for refinement and annotation, is limited and fails to detect fundamental changes in the control-flow that depend on context data. In this work, we thus propose a novel approach for combining the control-flow and data perspectives under a single roof by extending inductive process discovery. Our approach provides criteria under which context data, handled through unsupervised learning, take priority over control-flow in guiding process discovery. The resulting model is a process tree, in which some operators carry data semantics instead of control-flow semantics. We show that the proposed approach produces trees that are context consistent, deterministic, complete, and can be explainable without a major quality reduction. We evaluate the approach using synthetic and real-world datasets, showing that the resulting models are superior to state-of-the-art discovery methods in terms of measures based on multi-perspective alignments. • Context-aware process trees (CaT) are defined. • An inductive context-aware discovery algorithm (CaDi) is proposed. • CaDi produces trees that are context consistent, deterministic, and complete. • CaDi discovers models of higher quality than the state-of-the-art. • CaDi can be tuned to provide CaTs that are more explainable. [ABSTRACT FROM AUTHOR]

Abstract: Companies have to adhere to compliance requirements. The compliance analysis of business operations is typically a joint effort of business experts and compliance experts. Those experts need to create a common understanding of business processes to effectively conduct compliance management. In this paper, we present a technique that aims at supporting this process. We argue that process templates generated out of compliance requirements provide a basis for negotiation among business and compliance experts. We introduce a semi-automated and iterative approach to the synthesis of such process templates from compliance requirements expressed in Linear Temporal Logic (LTL). We show how generic constraints related to business process execution are incorporated and present criteria that point at underspecification. Further, we outline how such underspecification may be resolved to iteratively build up a complete specification. For the synthesis, we leverage existing work on process mining and process restructuring. However, our approach is not limited to the control-flow perspective, but also considers direct and indirect data-flow dependencies. Finally, we elaborate on the application of the derived process templates and present an implementation of our approach. [Copyright &y& Elsevier]