Publications

Unfair decision-making in business processes often remains unnoticed by organizations, yet it can have long-term consequences when process data are reused for predictive process monitoring (PPM). Existing work in PPM has proposed fairness-aware learning algorithms that construct predictive models from potentially biased event logs while maintaining predictive performance. They are in-processing approaches for mitigating bias and do not identify or fix the biases in the event logs. In this paper, we address this limitation by proposing a reweighting-based approach for the fair pre-processing of event logs that adjusts the contribution of individual traces to decision fairness within the process. Given a set of decisions, we apply reweighting by searching for a set of trace weights that minimizes unfairness across all decision points. Using this pre-processing approach promotes fairness in downstream analytical tasks. We evaluate the proposed approach on three event logs. The results show that fair pre-processing leads to an overall fairer event log. Additionally, we conducted a preliminary assessment of its impact on predictive performance. The results suggest that using the fair pre-processed event log in PPM task can lead to a predictive model with lower unfairness while preserving predictive accuracy.

The rise of data lakes has created complex and temporally rich repositories in which tabular data exists in multiple versions. Current data discovery methods fail to utilize this crucial temporal dimension, treating each version individually. This limits the effectiveness of data discovery and integration for downstream tasks, e.g., machine learning model training. To address this, we conduct an analytical study focusing on the Wikipedia table history data lake to characterize its temporal dimensions. Our work provides essential statistics on table evolution and revision types. This foundational understanding of table evolution can help guide the development of future data lake and data management systems capable of leveraging temporal table properties. Our exploratory analyses reveal distinct patterns in how table versions transform over time, identifying specific update frequencies, editor behaviors, and rollback prevalence that characterize the lake's lifecycle.

Regular expressions (RegEx) are an essential tool for pattern matching over streaming data, e.g., in network and security applications. The evaluation of RegEx queries becomes challenging, though, once subsequences are incorporated, i.e., characters in a sequence may be skipped during matching. Since the number of subsequence matches may grow exponentially in the input length, existing RegEx engines fall short in finding all subsequence matches, especially for queries including Kleene closure. In this paper, we argue that common applications for RegEx queries over streams do not require the enumeration of all distinct matches at any point in time. Rather, only an aggregate over the matches is typically fetched at specific, yet unknown time points. To cater for these scenarios, we present SuSe, a novel architecture for RegEx evaluation that is based on a query-specific summary of the stream. It employs a novel data structure, coined StateSummary, to capture aggregated information about subsequence matches. This structure is maintained by a summary selector, which aims at choosing the stream projections that minimize the loss in the aggregation result over time. Experiments on real-world and synthetic data demonstrate that SuSe is both effective and efficient, with the aggregates being based on several orders of magnitude more matches compared to baseline techniques.

Complex Event Processing (CEP) continuously evaluates queries over event streams to detect patterns that yield actionable insights. In monitoring applications, however, not all patterns are relevant at any point in time. Especially for queries with permissive evaluation semantics yielding a large number of matches, it is often sufficient to compute only aggregated, summary results upon request, e.g., upon refreshing a dashboard. The optimization potential of on-demand aggregations over detected patterns has, so far, been mostly considered for centralized evaluation scenarios. For the setting of distributed event processors, it is not yet clear how to efficiently compute and distribute local aggregates. To fill this gap, we propose DIPSUM, a framework for the efficient on-demand evaluation of CEP aggregate queries in distributed environments. DIPSUM combines the efficient aggregation over computationally expensive operators (Kleene closure, negation), with fine-grained routing of partial aggregates. It relies on a summary data structure that compactly captures match information and can be decomposed for distributed query evaluation. Experiments with real-world and synthetic data show that DIPSUM improves transmission costs, detection latencies, and throughput by several orders of magnitude compared to baseline strategies.

Systems for Complex Event Processing (CEP) enable the detection of predefined patterns in event streams. While the evaluation of CEP queries is computationally hard, scalability may be achieved by parallelization. Yet, existing approaches for parallel CEP are driven by static query properties, such as partitioning keys and states of the evaluation model. They largely neglect the rates with which processing units may ingest and compare events for query evaluation. In this paper, we present an approach for parallel CEP that is based on a flexible decomposition of CEP queries. Our idea is to guide the decomposition by the sustainable throughput of each processing unit, in order to maximize the overall performance. To this end, we introduce DecoPa plans for parallel CEP, provide a cost model for them, elaborate on their correctness and optimality, and present an algorithm for their construction. Experiments using a DecoPa implementation in Flink illustrate throughput gains of up to 12 orders of magnitude compared to state-of-the-art approaches.

Complex Event Processing (CEP) detects patterns in event streams based on predefined queries. However, CEP applications often do not require the enumeration of all detected patterns, but the computation of an aggregate over them, which enables more efficient processing. Yet, existing optimizations for the computation of aggregates over the matches of pattern queries are limited to centralized settings that assume that events are processed at a single location. In this paper, we present Pattern Aggregation (PA) plans as a model for on-demand computation of aggregates over patterns that are detected in networks of event sources. The model combines the distributed evaluation of pattern queries with a distributed computation of an aggregate over them. We introduce PA plans along with a cost model for the induced communication overhead and an algorithm for the construction of efficient plans. We demonstrate the feasibility and efficiency of our approach in a series of experiments.

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 a 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.

Complex event processing (CEP) detects situations of interest by evaluating queries over event streams. Once CEP is used in networked applications, the distribution of query evaluation among the event sources enables performance optimization. Instead of collecting all events at one location for query evaluation, sub-queries are placed at network nodes to reduce the data transmission overhead. Yet, existing techniques either place such sub-queries at exactly one node, which neglects the benefits of truly distributed evaluation, or are agnostic to the network structure, which ignores transmission costs due to the absence of direct network links. To overcome the above limitations, we propose INEv graphs for in-network evaluation of CEP queries with rich semantics, including Kleene closure and negation. Our idea is to introduce fine-granular routing of partial results of sub-queries as an additional degree of freedom in query evaluation: We exploit events already disseminated in the network as part of one sub-query, when evaluating another one. We show how to instantiate INEv graphs by splitting a query workload into sub-queries, placing them at network nodes, and forwarding of their results to other nodes. Also, we characterize INEv graphs that guarantee correct and complete query evaluation, and discuss their construction based on a cost model that unifies transmission and processing latency. Our experimental results indicate that INEv graphs can reduce transmission costs for distributed CEP by up to eight orders of magnitude compared to baseline strategies.

Complex event processing (CEP) enables the detection of situations of interest by evaluating queries over event streams. When applied in a networked application, events generated by distributed nodes are sent over the network to evaluate CEP queries. To reduce the transmission of events, push-based communication that sends each event immediately upon generation may be complemented with a pull-based model that buffers events locally until they are requested for query evaluation. Existing approaches that leverage push-pull communication to reduce transmission costs for distributed CEP, however, exploit solely temporal constraints imposed by a query. As such, they are not applicable in scenarios, in which relevant events may occur in each time window defined by a query. In this paper, we propose predicate-based push-pull (PrePP) plans for CEP queries to overcome the above limitations. Our idea is to construct pull requests that enable fine-granular filtering at event sources based on query predicates, thereby reducing event transmission. Since the construction of optimal PrePP plans is NP-hard, we introduce a set of algorithms to speed up the plan construction by up to five orders of magnitude compared to a brute-force approach, while producing near-optimal results. In extensive experiments, we demonstrate that PrePP plans reduce event transmission by up to three orders of magnitude over baseline techniques.