arXiv CSopen access

Pattern-level Differential Privacy for High-utility Complex Event Processing

· arxiv_cs

arXiv CS · Papers · License: Open Access

cryptography cybersecurity privacy security

cryptography, security, privacy, cybersecurity

<Society logo(s) and publication title will appear here.> Received XX Month, XXXX; revised XX Month, XXXX; accepted XX Month, XXXX; Date of publication XX Month, XXXX; date of current version XX Month, XXXX. Digital Object Identifier 10.1109/XXXX.2022.1234567

Pattern-level Differential Privacy for High-utility Complex Event Processing He Gu1 , Thomas Plagemann1 , Vera Goebel1 , Maik Benndorf 1 , and Boris Koldehofe2 1

Department of Informatics, University of Oslo, Oslo, 0316 Norway 2 Technische Universität Ilmenau, Ilmenau, Germany

arXiv:2609.23827v1 [cs.CR] 20 Sep 2026

Corresponding author: He Gu (emailco: [email protected]). This work was funded by the Parrot Project (Research Council of Norway, project number 311197).

ABSTRACT Current privacy-preserving mechanisms (PPMs) in Complex Event Processing (CEP) systems

are unnecessarily restrictive, reducing the utility of data received by data consumers. This article presents a novel approach to preserve privacy in CEP systems, improving the utility of detected event patterns by dynamically adapting the noise added to an unprotected data stream. We introduce a new guarantee named pattern-level differential privacy (DP), which enables us to apply and compare the strength of PPMs at the pattern level. We propose new pattern-level PPMs yielding pattern-level DP and analyze different trust settings of these PPMs and their requirements for context knowledge in the CEP system, e.g., the deployed queries. Our evaluation is based on three datasets (two real-world, one synthetic) and shows that the proposed PPMs increase data utility while preserving the same privacy level as the state-of-the-art PPMs. We use simulations to study the performance of our proposed PPMs in various practical scenarios. Furthermore, we demonstrate that computational complexity is not an obstacle to deployment. INDEX TERMS differential privacy, complex event processing, data stream processing

I. INTRODUCTION

OMPLEX Event Processing (CEP) systems are a very prominent big data processing paradigm that helps in detecting patterns, called complex events, in conceptually infinite data streams. The patterns of interest are typically specified in queries with syntax and operators similar to SQL, and specialized operators for complex events, such as the sequence operator. These queries utilize windowing techniques to partition conceptually infinite data streams into finite windows. Incoming data tuples or events are processed immediately, facilitating instant decision-making. CEP systems are applied in various fields, including maritime monitoring, smart building operations [1], credit card fraud detection, cybersecurity [2], and the Internet of Things (IoT) [3]. The demand for real-time data stream analysis is increasing due to the growing number of data sources and the valuable and timely insights they can provide [4]. Consequently, “virtually all cloud vendors offer first-class support for deploying managed stream processing pipelines” [5]. The data streams processed by CEP often contain sensitive information related to individuals, thereby posing potential

privacy risks. Therefore, it is crucial to develop privacypreserving mechanisms (PPMs) that achieve two seemingly conflicting objectives: ensuring robust privacy protection and maintaining sufficient data utility for applications in use. Traditional PPMs designed for static datasets cannot be directly used for CEP systems. Multiple studies have proposed PPMs for data streams, regarding all data tuples in a data stream equally important for privacy protection [6]– [8]. However, not all events for CEP systems are of the same importance for both privacy protection and analysis, as certain events can be part of a complex event that reveals more critical information. We argue that particular privacy protections of these key events can lead to better performance of a privacy-aware CEP system in terms of both privacy protection and data utility compared to state-of-the-art PPMs. Consider the example of an application that serves taxi drivers and passengers. A continuous data stream of taxi GPS locations is analyzed by a CEP query to find nearby passengers and warn potential traffic jams. The passengers on taxis prefer not to reveal their paths, as they may travel to sensitive locations, e.g., hospitals. In such cases, a common

This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see https://creativecommons.org/licenses/by/4.0/ VOLUME ,

Author et al.:

strategy for existing PPMs is to attach sufficient noise to the entire data stream during a trip to conceal the presence at sensitive locations. However, passengers only want to hide their proximity to sensitive locations, i.e., the pattern consisting of a sequence of GPS locations outside and inside sensitive areas within a temporal constrained window. Protecting such patterns instead of all events in a data stream improves data utility by reducing the noise added to the data stream while maintaining equally strong privacy protection. We denote PPMs that protect only particular patterns rather than all events in a data stream as pattern-level PPMs [9]. In addition to the patterns that contain data producers private information, pattern-level PPMs can also be enhanced by utilizing the patterns of data consumers interests. When these patterns are known, PPMs can be tailored accordingly by adding less noise to the relevant events, thereby improving data utility. We call the analysis conducted by data consumers in such cases transparent data stream analysis, since their analysis based on patterns is transparent to PPMs. In the context of the taxi example, if queries to traffic jam alerts are public, we can identify the events that are more critical for alerts and add less noise to these key events, leading to a higher precision of alerts. However, the patterns of data consumers interests can be confidential. For example, a data consumer that maintains a video-hosting platform might not want to reveal the patterns used by the recommender system of the platform. We call this type of analysis opaque data stream analysis. Currently, only a few pattern-level PPMs are proposed [10], [11]. Although they deliver better performance than non-pattern-level PPMs for CEP systems, they are not yet applicable to support most CEP functionalities and limit the performance for privacy-aware CEP systems. To address the shortcomings in existing solutions, we investigate the following research questions in this article: • How to propose a novel privacy guarantee that is valid for multidimensional data and common CEP operators. • How to design PPMs that, for a guaranteed level of privacy protection, minimize redundant noise added to the data and maximize data utility for given private and target patterns. • How to maintain a high-level of data utility when data consumers do not want to reveal their target patterns.

Differential privacy (DP) is a state-of-the-art framework for privacy protection with rigorous mathematical proof. Among DP-based models, local differential privacy (LDP) assumes that PPMs are executed before data is released from data producers, leading to a better generalization [12]. Therefore, we propose a novel pattern-level DP that provides patternlevel privacy guarantees and multiple pattern-level PPMs based on LDP for both transparent and opaque data stream analysis. We evaluate the performance of the proposed PPMs and analyze their advantages over the related works. This article makes the following contributions: 2

• We establish a theoretical foundation of pattern-level PPMs and propose a novel pattern-level DP, which enriches both the theories for pattern-level PPMs and DP regarding data streams and supports most CEP operators. It helps to reduce the redundancy for privacy protection in data streams and enables superior performance for PPMs under equally strong privacy guarantee, compared to non-pattern-level PPMs. • We propose four pattern-level PPMs that satisfy patternlevel DP, regarding different context knowledge and trust relationships, i.e., transparent and opaque data stream analysis. • We evaluate and illustrate the advantages of our proposed PPMs, compared to non-pattern-level state-ofthe-art PPMs and analyze their computational complexity.

The rest of the article is organized as follows: We introduce related works in Section II. The preliminaries including DP basics and the definition of events and patterns are presented in Section III. We explain the system model, the details of transparent and opaque data stream analysis, and their trust settings in Section IV. In Section V, we propose a novel pattern-level DP guarantee. We present pattern-level PPMs for transparent and opaque data stream analyses in Section VI and VII. We evaluate the proposed approaches in Section VIII and conclude this article in Section IX. II. RELATED WORKS

It is not surprising that most existing PPMs designed for data stream processing (without the ability to detect complex events) are also applicable to CEP systems, as the input of a CEP system is at least one event stream [13]. Therefore, we discuss first the most relevant PPMs for data stream processing. Among them, the solutions based on DP are generally considered reliable [12], [14], and three types of DP are most widely discussed, i.e., user-level, event-level, and w-event DP [7], [8], [14]–[16]. They guarantee privacy by achieving indistinguishability between private and nonprivate information w.r.t. individual users, individual events, or events in each window for a data stream processing system, respectively [7], [14]–[16]. They usually transform or snapshot the infinite data stream to a static dataset and utilize DP in that pseudo-dataset [8]. In addition to DP, some other studies based on, e.g., k-anonymity, are also proposed [17], [18]. They can provide satisfactory data utility under guaranteed privacy protection. However, PPMs for data stream processing cannot leverage the potential of transforming the knowledge of complex events into tailored PPMs. The key advantage of PPMs for CEP over those for data stream processing is that the knowledge of private and non-private patterns can be used to avoid redundant privacy protection and unnecessary obfuscation of events which form these patterns. This in turn results in appropriate privacy protection and higher data utility. VOLUME ,

Some studies have not fully leveraged the patterns of CEP systems but perform better compared to pure data stream processing PPMs [19]–[21]. They emphasize the practical representations of different data tuples and assign different privacy protections to them accordingly. Among them, Landmark privacy [19] assumes that some data tuples may contain significantly more valuable or more private information than others. Therefore, it adjusts the privacy budgets assigned to these tuples to improve its PPMs. However, for a CEP system, there are opportunities for further improvements because the patterns detected by a CEP system are usually much more complex than individual data tuples. Palanisamy et. al. [20] considered privacy protections based on patterns instead of data tuples by reordering detected events. However, it either fully blocks access to a pattern or publishes the pattern without any privacy protection. Therefore, it provides much weaker granularity than Landmark and other DP-based studies, and thus much weaker support for CEP operators. Unlike pattern-level PPMs for data stream processing systems, there are also pattern-aware approaches that focus on statistically significant sequences of data tuples [21]–[23]. These sequences are referred to as patterns in the related works, which are, however, distinct from the patterns defined for CEP systems and in this article. Two pattern-aware approaches based on DP are presented for data collection (PatternLDP) [21] and pattern extraction (PrivShape) [22]. They usually process one-dimensional time series that are of the same data type, which is untypical for CEP systems that usually take multidimensional data streams of different attributes as input. Furthermore, patterns for CEP systems are constructed based on concrete applications and practical representations, which are not necessarily statistically significant. In conclusion, patterns as defined in the context of CEP systems do not correspond to the notion of patterns presented in these pattern-aware approaches. Another pattern-aware approach (RetraSyn) presents real-Time trajectory synthesis which focuses on preserving spatial-temporal patterns under LDP [23]. Although it outperforms other state-of-the-art pattern-aware solutions on trajectory data, it is affected by the same disadvantages as focusing on statistically significant patterns and cannot be adapted to CEP systems. Our previous work presented a pattern-based solution with DP guarantees for CEP systems [9]. It increases data utility by adaptively assigning privacy budgets over events related to private patterns. However, this solution is limited because (1) it can only be applied to patterns formed by the sequence operator and (2) it assumes that all queries from data consumers are public, which may not be practical, since the queries can be confidential considering the business model of consumers. To the best of our knowledge, there is no solution that optimizes data utility and (1) provides DPbased privacy protection for private patterns, (2) supports all common operators of CEP systems, and (3) allows data consumers to keep their patterns of interest confidential.

VOLUME ,

III. PRELIMINARIES

In this section, we introduce the basics of DP for databases and data streams as the fundamentals of developing patternlevel DP. We also clarify the definitions of events and patterns needed to present the pattern-level DP and its PPMs. A. DIFFERENTIAL PRIVACY

A mechanism that complies with DP ensures that an adversary cannot distinguish two similar groups of information based on the responses of queries to them. DP formulates a bound on the information that an adversary with arbitrary side-information and computational power can reveal. Definition 1 (ϵ-differential privacy): A privacy mechanism M: I → O, where I is an arbitrary input dataset endowed with a neighboring relation N, is said to be ϵ-differentially private if for any Oi ⊆ O, Pr[M(Ii ) ∈ Oi ] ≤ eϵ · Pr[M(Ii′ ) ∈ Oi ],

∀Ii N Ii′ ,

where ϵ is called privacy budget. The neighboring relation between Ii and Ii′ indicates that Ii′ can be generated from Ii by replacing, adding, or removing only one record from Ii . This ordinary DP based on static datasets can be modified to handle dynamically updated datasets, i.e., data streams [14]. The neighboring relation is then modified to be the adjacency of data streams. It means that for two infinite data streams S D = (d1 , d2 , ...) ′ and S D = (d′1 , d′2 , ...) of data tuples d, there exists one and only one unique i such that di ̸= d′i , leading to the following definition of the ϵ-differential privacy for data streams [7]. Definition 2 (ϵ-differential privacy for data streams): For an arbitrary infinite data stream S D and its neighboring ′ stream S D , a privacy mechanism M that takes a data stream as the input and outputs Oi ⊆ O is ϵ-differentially private if for any Oi ⊆ O, it holds that ′

Pr[M(S D ) ∈ Oi ] ≤ eϵ · Pr[M(S D ) ∈ Oi ].

DP for data streams guarantees indistinguishability between outputs when taking neighboring data streams as inputs. By modifying the definition of the neighboring relation, one may propose diverse DP guarantees with different granularities of privacy protections, different practical representations, and different application scenarios. B. EVENTS AND PATTERNS

It is a common understanding that events comprise timestamps and a set of attribute-value pairs. For better comprehensibility, this article uses a rudimentary case in which each event contains one attribute-value pair with one timestamp. It does not restrict the generalization of our approach, because any arbitrary event with n attribute-value pairs can be regarded as n events with one attribute-value pair. The 3

Author et al.:

(a) Privacy model for transparent data stream analysis

(b) Privacy model for opaque data stream analysis

FIGURE 1: Workflow of transparent and opaque data stream analysis. - - ->: the setup phase; —>: the service provision phase; Rectangles in dashed lines: trust domains; CQ: continuous queries; req.: requirements; info.: information. values of events can be numerical or categorical. Extracting all events from a data stream forms an event stream S E = (e1 , e2 , ...), where ei denotes the ith produced event. Multiple data streams from different sources can be merged into one event stream, where ei is the ith extracted event. Within an event stream, an ordered sequence of events may contain valuable information that we denote as a pattern Q Q P = Q(eQ 1 , e2 , ..., em ), where Q is a query formed by data stream operators that can reveal the information contained in these events. A pattern stream S P = (P1 , P2 , ...) can then be formed by extracting all patterns from an event stream, where Pi is the ith detected pattern. Some detected patterns may contain private information of data producers and are classified as private patterns, while all others are public patterns. Furthermore, for a data consumer, the patterns that are of their interest are their target patterns. In the context of the Taxi example, data streams contain GPS records of all taxis with passengers. We collect the records of interest and merge them into an event stream. The sequence of several events forms a pattern, e.g., a taxi drives to a hospital. Different combinations of events may form the same type of patterns. For example, both when a taxi approaches a hospital from north and south are the same type of patterns that the taxi drives to the hospital. Therefore, we see a demand to distinguish specific patterns from the type of patterns. We formally clarify that a pattern Q Q P = Q(eQ 1 , e2 , ..., em ) referred to in this article is a specific combination of events eQ i that can be retrieved by query Q in a given event stream. Meanwhile, a pattern type P is a group of patterns specified by a query QP . A pattern Pi is an element of P , i.e., Pi ∈ P , if and only if it can be retrieved by QP . Since pattern-level PPMs focus on patterns instead of basic events, their performance metric w.r.t. data utility can be a combination of both recall and precision of detecting target patterns in data streams. Inspired by statistical classification methods, we introduce F1 -score as the performance metric of PPMs w.r.t. data utility [24]: U = F1 = 2

precision · recall . precision + recall

(1)

IV. SYSTEM MODEL AND TRUST SETTINGS

This work is based on the concept of LDP and a system model consisting of four basic components (see Figure 1): 4

• Data producers share their data, specify their private patterns, and demand that they be protected. • The PPM component deploys PPMs to protect private patterns and maintain sufficient data utility. • The CEP engine continuously analyzes privacyprotected data streams received from the PPM component and forwards the detected target patterns to data consumers. • Data consumers submit queries that describe the target patterns to the CEP engine and declare their requirements for data utility needs. Data consumers are potential privacy adversaries, following the honest-butcurious threat model.

In Figure 1, the rounded rectangles in dashed lines denote the trust domains where the original information within is by default not accessible by components outside the domain. The system operates in two distinct phases: the set-up phase and the service provision phase. During the setup phase (illustrated by dashed arrows in Figure 1) data producers specify their privacy requirements, i.e., private patterns while data consumers specify queries for their target patterns and their data utility requirements. This information enables the PPM component to configure a tailored PPM that meets the specified requirements. Additionally, the data consumer registers the queries for the target patterns in the CEP component. In the service provision phase (illustrated by solid arrows in Figure 1), original data from the data producer is streamed to the PPM, which protects the private patterns while preserving the required utility of data elements forming the target patterns. Subsequently, the output of the PPM is streamed to the CEP component, which continuously processes the consumers’ queries against the incoming data stream to detect the specified target patterns. All detected target patterns are then forwarded to the data consumer. Given that this work builds on the principals of LDP, the PPM component is consistently deployed in the trust domain of the data producer. Since the output of the PPM is privacy protected, the data producer does not need to establish any trust relation with the CEP component. However, the relationship with the data consumer can vary, leading to two distinct scenarios: (1) the data consumer is unconcerned sharing the target pattern queries with the PPM component and an untrusted CEP engine or, (2) the VOLUME ,

data consumer prefers to conceal target pattern queries to untrusted entities. For instance, in a video hosting platform utilizing a machine learning based recommendation system, confidentiality is vital for its business model. In such cases, the data consumer does not provide the target patterns to the PPM components and requires a trusted CEP component to register and process the target pattern queries. When target pattern queries are visible to the PPM component, this is called transparent data stream analysis (Figure 1a); conversely, if target pattern queries are hidden, it is referred to as opaque data stream analysis (Figure 1b). In case of transparent data stream analysis the PPM component leverages the knowledge of private and target patterns to optimally tailor the PPM. In opaque data stream analysis, however, the PPM lacks access to target patterns, limiting its capacity for optimization. Nonetheless, rather than entirely forgoing the insights obtainable from data consumers, we propose a federated approach between the PPM component and data consumers that does not require disclosing target patterns. In the simplest case, the data consumers provide the number of events that have to be analyzed to detect a target pattern, called the observation span of a target pattern. With this limited information, our pattern-level PPMs can still significantly enhance data utility performance compared to other PPMs, providing a compelling incentive for data consumers to collaborate with the PPM component.

most similar patterns to each other in P . Given Definition 3, we can define the neighboring relation for pattern streams. Definition 4 (pattern-level neighbors): Given a pattern type P , and two infinite pattern streams ′ ′ S P = (P1 , P2 , ...) and S P = (P1′ , P2′ , ...), S P and S P are pattern-level neighbors w.r.t. P if and only if there exists a unique integer i such that (1) Pi and Pi′ are in-pattern neighbors of P , and (2) for all j ̸= i, Pj = Pj′ holds. The pattern-level neighboring relation clarifies the granularity of the indistinguishability guaranteed by the patternlevel DP. In practice, this neighboring relation describes two distinguishable yet least different pattern streams for a typical CEP system because two pattern-level neighboring streams only differ by the neighboring patterns, which differ by one basic event. The pattern-level DP is then proposed as follows. Definition 5 (pattern-level DP): Assume that M is a privacy mechanism that takes a pattern stream as input and outputs a response R that belongs to the group of all possible responses R. Then M satisfies patternlevel ϵ-DP of a given pattern type P (pattern-level DP of P ) ′ if and only if for any pattern-level neighbors S P and S P of P and any sets of response Ri ⊆ R, ′

Pr[M(S P ) ∈ Ri ] ≤ eϵ · Pr[M(S P ) ∈ Ri ]. V. PATTERN-LEVEL DIFFERENTIAL PRIVACY

In this section, we propose a novel DP guarantee, which achieves ϵ-DP w.r.t. patterns and is hence named patternlevel DP. Its design consists of three steps: • We define the neighboring relation between individual patterns, i.e., in-pattern neighbors (Definition 3), because it forms the fundamental of the neighboring relation between pattern streams. • We define the neighboring relation between pattern streams, i.e., pattern-level neighbors (Definition 4), because it affects the characteristics and granularity of the privacy protection guaranteed by pattern-level DP. • We propose the pattern-level DP (Definition 5) in pattern streams for a given pattern type P , based on the defined neighboring relations.

Definition 3 (in-pattern neighbors): Q Q ′ = Two patterns P = Q(eQ 1 , e2 , ..., em ), and P ′ ′ ′ Q Q ), of the same pattern type P and the Q′ (e1 , e2 , ..., eQ m same length are in-pattern neighbors of P if ′ and only if Q there exists a unique i such that (1) eQ i and ei only differ Q′ by their attribute-value pairs and (2) for all j ̸= i, eQ j = ej . In-pattern neighboring relation clarifies the least possible difference between two most similar patterns. This means that two neighboring patterns of the same pattern type P can only differ by one single event, which makes them one of the VOLUME ,

Pattern-level DP of P guarantees privacy for Pi ∈ P . In practice, P are usually private pattern types of data producers. Mechanisms that fulfill pattern-level DP output similar query results regardless of the existence of private patterns. Pattern-level DP provides a more customized privacy protection compared to non-pattern-level DPs, which allows PPMs to reduce the privacy budgets ϵ assigned to less important events and utilize the budgets more efficiently, leading to better privacy-utility trade-off and overall superior performance. Although a precise definition of target patterns is helpful in improving data utility, the overall privacy budgets assigned to private patterns are fixed. This indicates that even if the data utility is impaired by imprecise target patterns, the privacy protection is not weakened. For target patterns, there is no limitation for the CEP operators used to form these patterns. However, for private patterns, the used operators must be able to catch the difference between patterns caused by their different belonging events. In other words, private patterns must have in-pattern neighbors and must be able to form pattern-level neighbors. Most CEP operators, e.g., Max/Min operators, average operators, and followed by operators, satisfy this requirement. VI. PATTERN-LEVEL PPMS FOR TRANSPARENT DATA STREAM ANALYSIS

In Section III.B, we classify all events into two categories, i.e., categorical events and numerical events. To achieve DP, 5

Author et al.:

we usually attach noise to individual events. However, the noise that is appropriate for numerical events, e.g., age, is usually improper for categorical events, e.g., nationality. Therefore, for different types of events, we attach different types of noise to protect their contained private information. In detail, we present the randomized response for categorical events, which provides a random selection among all possible categories with a set of assigned probabilities. For numerical events, we apply the Laplace mechanism, which adds Laplace noise to events based on a Laplace distribution. The randomized response and Laplace mechanism are proven to be differentially private [25]. However, this article presents a novel DP guarantee, i.e., pattern-level DP, which is distinct from the ordinary DP. Therefore, in order to utilize the randomized response and Laplace mechanism to achieve pattern-level DP, their pattern-level DP characteristics must also be verified, apart from their ordinary DP characteristics. In such cases, they are also required to be modified to match pattern-level privacy protection measures. We first propose the randomized response for pattern streams and verify its pattern-level DP characteristics, followed by the definition, verification, and proofs for the Laplace mechanism. Definition 6 (Randomized response (pattern streams)): Given a pattern stream S P = (P1 , P2 , ...) that consists of Q Q patterns P = Q(eQ 1 , e2 , ..., em ), then a privacy mechanism M offers a randomized response if it takes the existence i of events I(eQ i ) ∈ {0, 1} as input and outputs responses Ri ∈ {0, 1} for each event with probability where j ̸= k : ( Pr(Ri = j|I(ei ) = j) = 1 − pi Pr(Ri = j|I(ei ) = k) = pi , To verify the pattern-level DP characteristics of the randomized response, we start with the DP characteristics w.r.t. the events of a given pattern in a pattern stream. Subsequently, we derive the result to an entire pattern stream. Lemma 1: Given a pattern stream S P = (P1 , P2 , ...) consisting of Q Q patterns P = Q(eQ 1 , e2 , ..., em ), for a privacy mechanism M1 that (1) offers a randomized response for ei with pi ≤ 12 , (2) takes I(e) = (I(e1 ), I(e2 ), ..., I(en )) as inputs, and (3) outputs responses R = (R1 , R2 , ..., Rn ), it guarantees i ln 1−p pi -pattern-level DP w.r.t. a given type of pattern P . Proof: For two pattern-level neighbors S P = (P1 , P2 , ...) and ′ S P = (P1′ , P2′ , ...) of pattern type P , if given any randomized response mechanism M1 as described above, then Pr[M1 (S P ) ∈ R] Pr[M1 (I(ei )) = Ri ] 1 − pi = ≤ . Pr[M1 (S P ′ ) ∈ R] Pr[M1 (I(e′i )) = Ri ] pi

i It proves that M1 guarantees ln 1−p pi -pattern-level DP for the above settings. We subsequently study the pattern-level DP for any pattern in a pattern stream.

Theorem 1: Given a pattern stream S P = (P1 , P2 , ...) consisting of patterns, a privacy mechanism M that offers a randomized Q Q response for P = Q(eQ 1 , e2 , ..., en ) that belongs to a given pattern type P with p1 , p2 , ..., pn ≤ 12 . If it takes I(e) = (I(e1 ), I(e2 ), ..., I(en )) as inputs and outputs responses P 1−pj R = (R1 , R2 , ..., Rn ), M guarantees i:ei ∈P ln pj pattern-level DP with respect to a given type of pattern P . Proof: For two pattern-level neighbors S P = (P1 , P2 , ...) and ′ S P = (P1′ , P2′ , ...) of pattern type P , if given any randomized response mechanism M as described above, then Y Pr[M(I(ei )) = Ri ] Pr[M(S P ) ∈ R] = ′ P Pr[M(S ) ∈ R] Pr[M(I(e′i )) = Ri ] i:ei ̸∈P

Y Pr[M(I(ei )) = Ri ] Pr[M(I(e′i )) = Ri ] i:ei ∈P Y 1 − pi . ≤ pi ·

j:ei ∈P

Q 1−p It proves that M guarantees ln j:ej ∈P pj j -pattern-level P 1−p DP, i.e., j:ej ∈P ln pj j -pattern-level DP. Therefore, applying randomized response to related events leads to patternlevel differentially private outputs. We then present the Laplace mechanism and verify that it satisfies pattern-level DP. We first introduce an important concept of Laplace mechanisms, i.e., the sensitivity of a privacy mechanism [25] and define Laplace mechanisms. Definition 7 (Sensitivity of a privacy mechanism): Given a privacy mechanism M that takes ei as inputs and outputs responses Ri . The sensitivity of M is then defined as S(M) ≜ sup |Ri − Rj |, where ei and ej are neighboring. Definition 8 (Laplace mechanisms (pattern streams)): Given a pattern stream S P = (P1 , P2 , ...) that consists Q Q of patterns P = Q(eQ 1 , e2 , ..., en ), a privacy mechanism ML is a Laplace mechanism, if it takes I(e) = (I(e1 ), I(e2 ), ..., I(en )) as inputs and outputs responses R = (R1 , R2 , ..., Rn ), where Ri = I(ei )+ωi , and ωi ∼ Laplace i . We study the pattern-level DP characteristics of the Laplace mechanism following the same procedure of the randomized response mechanism. Theorem 2: For two pattern-level neighbors S P = (P1 , P2 , ...) and ′ S P = (P1′ , P2′ , ...) of a pattern type P , a Laplace mechanism VOLUME ,

ML applied Pto any pattern P ∈ P with sensitivity S(M) guarantees i:ei ∈P S(M)/λj pattern-level DP.

Proof: For two pattern-level neighbors S P = (P1 , P2 , ...) and ′ S P = (P1′ , P2′ , ...) of a pattern type P , if given any randomized response mechanism M as described above, then we see that Y Pr[ML (I(ej )) = Rj ] Pr[ML (S P ) ∈ R] = ′ P Pr[ML (S ) ∈ R] Pr[ML (I(e′j )) = Rj ] j:ej ̸∈P

Y Pr[ML (I(ei )) = Ri ] Pr[ML (I(e′i )) = Ri ] i:ei ∈P P Y ≤ eS(M)/λi = e i:ei ∈P S(M)/λi . ·

i:ei ∈P

P It is proven that M guarantees i:ei ∈P S(M)/λi -patternlevel DP, and hence, both the randomized response and Laplace mechanism satisfy pattern-level DP. Based on them, we subsequently present two pattern-level PPMs for transparent and opaque data stream analysis, i.e., a uniform approach and a bidirectional step-wise approach. A. THE UNIFORM APPROACH

The previous sections show that the privacy budgets assigned to each event, i.e., ϵ of pattern-level DP, eventually accumulate in the pattern stream. Therefore, with a given total privacy budget ϵ, we can distribute it to all relevant events which belong to private patterns and can be revealed by data consumers when querying target patterns. This leads to the most critical difference in the budget distribution between pattern-level DP and the DPs proposed by the related works. In the related works, the privacy budgets are usually assigned among a sequence of events listed with temporal orders. For example, regarding the w-event DP with a window of size w [12], the privacy budgets are distributed among the events from timestamp t to timestamp t + w − 1. The specific distribution can be improved to reach a better data utility, e.g., by dividing all data producers into groups and arranging the timestamp of releasing the data of each data producer to enhance the privacy-utility trade-off [12]. Unlike the related works, the pattern-level DP assigns privacy budgets only to those events that are relevant to private and target patterns, which enables a more flexible and adaptive privacy budget distribution than, e.g., w-event privacy. An intuitive approach is to uniformly distribute ϵ, which is named the uniform approach. Given a private pattern P = Q Q Q(eQ 1 , e2 , ..., en ), we denote the privacy budget assigned to Q ei as ϵi . For a randomized response, we have proven that i ϵi = ln 1−p pi , while for a Laplace mechanism, ϵi = S(M)/λi holds. Therefore, the probabilities pi for the randomized response and λi for the Laplace mechanism are the only parameters relevant to the privacy budget distribution, when the sensitivity S(M) is constant for each event. In practice, the sensitivity is determined by the boundary values of the VOLUME ,

attributes in the given data stream, which are usually fixed. We can therefore regard the sensitivity as a constant, and the problem of assigning privacy budgets is then equivalent to determining pi and λi . Here, pi controls the probability of obtaining correct responses when querying target patterns, while λi controls the amount of noise attached to an event. Therefore, they are also the only parameters that affect the data utility, in terms of MRE U . Optimizing pi and λi is then the only problem in optimizing the performance of PPMs. Furthermore, since both λi and pi are independent of ϵj if i ̸= j , the privacy budget distributions for numerical events and categorical events are also independent from each other, if we do not employ both types of mechanism on the same event. It indicates that one combination of privacy budgets corresponds to one combination of λi and pi . We can therefore employ the Laplace mechanisms for numerical events and meanwhile the randomized response for categorical events, without considering the overlapping effects between them. In conclusion, for a given trust relationship, the optimal ϵi will lead to optimal sets of λi and pi and hence to the optimal performance of PPMs. In such cases, although multiple independent private patterns overlap each other, i.e., share certain events, their privacy budget distributions are still independent. In other words, their shared events are assigned different and independent privacy budgets multiple times for each private pattern to which the events belong. B. THE BIDIRECTIONAL STEP-WISE APPROACH

The uniform approach considers all relevant events equally important. However, some private events may be critical for detecting target patterns, while containing little private information. It is more beneficial to assign more privacy budgets to these events, leading to weaker privacy protection but higher data utility. Inspired by statistical learning, we propose a bidirectional step-wise algorithm, i.e., the stepwise approach, that utilizes historical data to optimize ϵi , as demonstrated in Algorithm 1. Algorithm 1 is executed only before starting a data stream. This indicates that the privacy budgets assigned to the events of the same type remain unchanged for a run-time data stream. The data utility can be improved by executing Algorithm 1 before streaming the data, because (1) the schema, (2) the compositions of privacy patterns, and (3) the compositions of target patterns in a flowing data stream are always fixed. We first evenly distribute the privacy budget to all relevant events that belong to private patterns and can be revealed by data consumers while querying target patterns. After creating an ordered list for these events, we increase the privacy budget assigned to the first event while equally reducing the budgets for other events. If the data utility increases, we maintain this change and otherwise abandon it. We iterate this procedure for each event in the list for multiple times, until the available computation time runs out or the data utility reaches a predefined expectation. In ideal cases, Algorithm 1 is capable of finding the optimal ϵi , as 7

Author et al.:

well as the optimal pi and λi , and provides significantly superior performance than the uniform approach. In practice, Algorithm 1 may not reach the theoretical optimum, but its performance can converge to the optimum by consuming more up-to-date field data. There are two critical assumptions for Algorithm 1: (1) The expected statistical distribution of the collected historical data also applies to the coming data in the pattern stream. (2) The schema of historical data and the future pattern streams strictly match each other. Infractions to them can degrade performance. Algorithm 1 Bidirectional step-wise privacy budget distribution for transparent data stream analysis 1. Distribute the total privacy budget ϵ evenly to all the ϵ m events that are relevant to private patterns ϵi = m . 2. Select the size of each step based on field experience. ϵ A suggestion is δϵ = 100m . 3. Calculate data utility U ; Set U1 = U2 = ... = Um = U . while ϵ1 , ϵ2 , ..., ϵm ∈ [0, ϵ] and Ui:Ui =max Ui ≥ U do 4.1. Set i = 1. Set U = Ui:Ui =max Ui . while i ≤ m do 4.2.1. Set ϵi = ϵi + δϵ , and set all other privacy δϵ budgets ϵj:j̸=i = ϵj − m−1 . 4.2.2. Calculate data utility metric Ui . 4.2.3. Set ϵi = ϵi − δϵ , and set all other privacy δϵ budgets ϵj:j̸=i = ϵj + m−1 . Set i = i + 1. if Ui:Ui =max Ui ≥ U then 4.3. Set ϵi:Ui =max Ui = ϵi + δϵ . Set all other privacy δϵ budgets ϵj:j̸=i = ϵj − m−1 . if computation time runs out then 4.4. break.

VII. PATTERN-LEVEL PPMS FOR OPAQUE DATA STREAM ANALYSIS

For opaque data stream analysis, the PPM component is not informed about queries to target patterns. Therefore, additional measures are required to compensate for the missing information. In this section, we adapt the proposed PPMs for transparent data stream analysis so that they can be constructed with limited information about target patterns. The adaptation fulfills the requirements presented in Section IV, i.e., the adapted PPMs do not reveal the queries that retrieve target patterns. A. THE UNIFORM APPROACH

Although the structures of target patterns are unknown to the PPM component, the uniform approach is not severely affected, since it requires only the observation span of target patterns, as defined in Section III.B. Once the actual observation span is longer than the estimated value, redundant privacy protections are applied, leading to unnecessarily lower data utility. In practice, we may assume that the actual observation span is fixed as l, while the observation span provided by consumers is ˆl. When ˆl < l, we would 8

apply privacy protection more frequently than we should, leading to redundant privacy protection and overall fewer privacy budgets. For a given theoretical privacy budget ϵ̂, the actual privacy budget applied for privacy protection is ϵ = ϵ̂ll̂ . Assuming that data consumers follow the honest-butcurious model and provide an accurate ˆl, we can then assign the privacy budgets uniformly. Since only an approximate observation span of a target pattern is provided to the PPM component, it is impossible to infer the concrete structure of the target pattern. Therefore, the target pattern and its queries are protected for the adapted uniform approach. B. THE BIDIRECTIONAL STEP-WISE APPROACH

In addition to the observation spans, the step-wise approach only requires data utilities from data consumers, since the F1 -scores can only be provided by consumers once the target patterns are unknown. An intuitive approach is to provide both the original data and protected data to data consumers to calculate the decrease in data utility. If the collected historical data are provided by data consumers, there are no privacy question marks. However, if the historical data are not owned by data consumers, they can still be private against the consumers. An obfuscation procedure is then employed for privacy protection. When processing historical data, real-time detection of target patterns is not required. Therefore, for each historical dataset, we generate n obfuscation datasets with distinct yet sufficient noise attached. All obfuscation datasets are delivered to data consumers with the original dataset, expecting data utilities in return. In such cases, the privacy protection of the historical data can reach any predefined intensity, since as n tends to infinity, the privacy protection tends to be infinity strong. We conclude the step-wise approach for opaque data stream analysis in Algorithm 2. Note that the approach will not reveal target patterns, as neither of its required information can be a threat. VIII. EVALUATION

To evaluate the proposed PPMs, we perform three studies. Study (1): A comparative study to compare our PPMs with the most relevant related works, i.e., budget distribution (BD) [14] and Landmark privacy [19], as well as two recent proposals based on statistical definitions of patterns, i.e., PrivShape in classification task mode1 [22] and RetraSyn with population division (RetraSynp ) [23]. We use two realworld datasets (Taxi [26]–[28] and Ads [29], [30]) and a synthetic dataset2 . The Synthetic dataset is generated by a generator proposed in our previous work [9]. The introduced pattern-level PPMs [10], [11] are not evaluated because they only support the sequence operator of CEP systems. Study (2): A synthetic study to analyze how our PPMs impact the data utility in a wide range of simulated practical scenarios 1 Multidimensional data are flattened for PrivShape. 2 As conducted by most related works, these datasets are streamed to the

evaluated approaches to simulate the behavior of data streams.

VOLUME ,

Algorithm 2 Bidirectional step-wise privacy budget distribution for opaque data stream analysis 1. For m events that are relevant to private patterns, and a given total privacy budget ϵ = ϵ̂ll̂ , distribute evenly the ϵ budget ϵi = m . 2. Select the size of each step based on field experience. ϵ A suggestion is δϵ = 100m . 3. Calculate data utility U ; Set U1 = U2 = ... = Um = U . while ϵ1 , ϵ2 , ..., ϵm ∈ [0, ϵ] and Ui:Ui =max Ui ≥ U do 4.1. Set i = 1. Set U = Ui:Ui =max Ui . while i ≤ m do 4.2.1. Set ϵi = ϵi + δϵ , and set all other privacy δϵ budgets ϵj:j̸=i = ϵj − m−1 . 4.2.2. Deliver datasets with n obfuscation datasets to data consumers to calculate data utility Ui . 4.2.3. Set ϵi = ϵi − δϵ , and set all other privacy δϵ budgets ϵj:j̸=i = ϵj + m−1 . Set i = i + 1. if Ui:Ui =max Ui ≥ U then 4.3. Set ϵi:Ui =max Ui = ϵi + δϵ , and set all other δϵ . privacy budgets ϵj:j̸=i = ϵj − m−1 if computation time runs out then 4.4. break.

and workloads with a sequence of synthetic datasets. Study (3): A study to evaluate the computational complexity of the proposed approaches. A. EXPERIMENTS

We conduct experiments in the comparative and synthetic studies with Python on Windows 11 with an Intel 5.0GHz CPU and 32GB RAM. The study of computational complexity is conducted on a Raspberry Pi 4. The Taxi dataset contains GPS records of 10,357 taxis within Beijing (GPS locations were collected every 623 meters). Taxi has a relatively low complexity that enables an evaluation with varying ratios of private and target patterns. Ads consists of 26 million records of users of an online store, including the clicks of users on advertisements and their profiles, e.g., their IDs and genders. It contains more than 20 dimensions of data, which enables an investigation for relatively more complex use cases. Both Taxi and Ads are of sufficient quality and are used by multiple related works, including Landmark and RetraSyn. Synthetic datasets are generated by the generator [9] for more flexible analysis. Although the datasets comprise real-world data, we need to complement them with semantically meaningful patterns to evaluate pattern-level PPMs. These patterns are related in the Taxi dataset to areas in Beijing that are determined as private areas, e.g., homes of passengers, and target areas. The Taxi service monitors any taxi that enters target areas while attempting to hide the proximity to private areas. The Beijing area is partitioned into 10,000 squared blocks of equal sizes with initially 40% as private areas and 50% of as target areas. Twenty-five percent of the private areas are then selected VOLUME ,

as additional target areas to ensure a sufficient overlap of private and target patterns. We conduct another experiment by exchanging target and private areas to evaluate a scenario with more private patterns than target patterns. For the Ads dataset, we construct more complex patterns to enhance the generalization of our evaluation, including four types of private patterns that combine users IDs with (1) the values of goods of interests, (2) genders, (3) resident cities, or (4) clicked advertisements, and three types of target patterns that for each user combine (1) its resident city with the goods of interests, (2) gender with clicked advertisements, and (3) age with the viewed goods. For the Synthetic dataset, patterns are constructed by the generator [9]. By default, each pattern is constructed with six events, based on related studies and field experience, e.g., [20]. Each target pattern shares 25% events with at least one private pattern. For the step-wise approaches, 25% data are randomly selected as historical data. For opaque data stream analysis, we simulate a scenario in which target patterns are confidential. The proposed PPMs are evaluated based on varying privacy budgets ϵ ranging from 0.1 to 4 for transparent and opaque data stream analysis. The performance of PPMs are evaluated by the decrease in data utility caused by employing a PPM. A smaller decrease corresponds to a better performance. The Mean Relative Error (MRE) is applied to measure the decrease: Uord − UPPM MRE U = , (2) Uord where UPPM and Uord are the data utilities with and without applying PPMs, measured by F1 -scores. The investigated related works in the comparative study, i.e., BD, Landmark, PrivShape, and RetraSyn, are based on different DP guarantees and different definitions of privacy budgets. For evaluation, their privacy budgets are converted to the scale of pattern-level DP. BD and PrivShape are based on w-event DP and are considered as a scenario where target patterns consist of all events contained in a sliding window, and private patterns are individual events. Landmark privacy has the same private patterns, while the target patterns are its Landmark events [19]. RetraSyn regards the transition of data producers as private patterns [23] and has the same target patterns as our PPMs. B. COMPARATIVE STUDY RESULTS

The comparative study with BD, Landmark, PrivShape, and RetraSyn consists of four experiments with (1) the Taxi dataset with more private patterns than target patterns, (2) the Taxi dataset with more target patterns, (3) the Ads dataset, and (4) the Synthetic dataset. RetraSyn is not evaluated in Experiments 3 and 4, because it is designed for trajectory data. Figure 2 illustrates the results of Experiments 1, 3, and 4. The results of Experiment 2 are not illustrated, as it produces a significantly similar plot to Experiment 1. The overall evaluation agrees that our pattern-level PPMs significantly outperform other state-of-the-art solutions. 9

Author et al.:

(a) Taxi with more target patterns

(b) Advertisement

FIGURE 2: MRE with respect to privacy budget ϵ. Higher ϵ corresponds to weaker privacy protection.

We notice that the performance of PrivShape and RetraSyn is distinct from the other approaches. Therefore, we first collectively analyze their results and subsequently discuss the performance of BD and Landmark. Compared to their related works, PrivShape and RetraSyn are notably affected by the settings of CEP systems, as illustrated in Figure 2. PrivShape extracts patterns with classification methods instead of employing a CEP system. Theoretically, CEP systems can extract all patterns with 100% accuracy, while the classification methods used by PrivShape have significantly lower accuracy [22]. This leads to an unfair comparison in terms of data utility and a relatively less stable trend in MRE. Furthermore, PrivShape aims to extract statistically significant patterns, while the patterns for CEP systems are usually of little statistical significance, which reduces the effectiveness of PrivShape. The relatively low performance of RetraSyn is due to a similar cause. RetraSyn uses a Markov chain-based probabilistic model to generate synthetic trajectories [23]. However, the mobility transitions based on the Taxi dataset and a CEP system are randomized, which neutralizes the usefulness of the Markov-based model. In addition, the regions labeled as private or target patterns are approximately only 70% of all regions recorded by the Taxi dataset, while RetraSyn regards all regions as target patterns. This increases the redundancy in privacy protection for RetraSyn and reduces data utility. The results of Experiment 1 (Figure 2a) illustrate that the transparent and opaque step-wise approaches outperform BD and Landmark. The transparent step-wise approach surpasses the performance of BD and Landmark by approximately 30% and that of the uniform approach by 10%, when privacy budgets are higher than 0.5. The approaches for transparent data stream analysis perform better than those for opaque data stream analysis because knowing target patterns allows PPMs to reduce the noise added to events belonging to these patterns, and thus reduces the loss of data utility. The results of Experiment 3 (Figure 2b) illustrate more significantly the advantages of pattern-level PPMs. BD and Landmark are penalized more for more complex patterns, as the detection

of target patterns is more affected after applying these PPMs. Opaque data stream analysis reduces the performance of our PPMs in this experiment more than in Experiment 1, since the loss of information of target patterns in such cases has more negative impacts. However, for the step-wise approach, the information on target patterns can be partially retained by training on historical data, leading to a smaller decrease in data utility compared to the uniform approach. Experiment 4 evaluates the PPMs for a more complex use case. Both private and target patterns for Experiment 4 consist of six events, which are significantly more than those for other experiments. The private and target patterns for this experiment are more likely to overlap each other than in other experiments. This experiment shows for all PPMs a similar trend in Figure 2c as the other experiments, i.e., a higher privacy budget leads to a lower MRE. Furthermore, the graphs imply that the performance advantage of our PPMs over BD and Landmark increases with more complex patterns, as it leads to an approximately 60% lower MRE in Experiment 4. Given the results of this study, we conclude that (1) our proposed approaches outperform the related works in all cases and (2) the performance advantages of our approaches increase with the complexity of the scenarios. Non-patternlevel PPMs are not designed to provide dedicated solutions for protecting private patterns, and their privacy budgets are therefore largely squandered. When privacy can be clarified and protected at the pattern level, the application of our proposed PPMs leads to significant improvements. C. SYNTHETIC STUDY RESULTS

The comparative study shows that our PPMs outperform the selected works for the scenarios that have been widely used for evaluation in related studies. Since many use cases might still diverge from them, we further investigate a wider range of workloads based on a sequence of synthetic datasets (each comprising 150, 000 events) [9]. The study is conducted in three dimensions related to private and target patterns, i.e., the occurrence rates, the complexity, and the overlapping rates. The occurrence rate is the percentage of data belonging VOLUME ,

(a) MRE w.r.t. occurrence of patterns

(b) MRE w.r.t. complexity

FIGURE 3: MREs in diverse scenarios. The privacy budget ϵ is fixed as 1.

to a given pattern type w.r.t. the total amount of data. The complexity is the number of events contained in each pattern. The overlapping rates are the percentage of shared events between a target pattern and at least one private pattern. While one of the three characteristics changes, the others are fixed to default values. The default occurrence rates for private patterns are 40%, while 50% for target patterns, because lower occurrence rates lead to unnecessarily more experiments to collect sufficient results. The occurrence rates of private patterns are lower than those of target patterns based on field experience. The complexity is by default six events to ensure that private and target patterns share sufficient numbers of common events. In other words, the private and target patterns cannot be independent from each other. The evaluations would otherwise become meaningless. The default overlapping rates are 25%. Figure 3a illustrates that the MRE increases as the occurrence of privacy patterns increases, and when the occurrence of target patterns increases, the MRE is approximately constant. Higher occurrence of private patterns leads to overlapping privacy protections and redundant noises added to the same events, leading to larger MREs that eventually reach the maximum 1. However, when the occurrence of target patterns increases, the privacy protections are not affected, and hence the decrease in data utility is insignificant. The increasing complexity leads to an increasing MRE as illustrated in Figure 3b. For more complex patterns, it is more challenging to maintain the completeness of target patterns from the noised data. Figure 3c indicates that when the overlapping rate between private and target patterns grows, the data utility is degraded. Higher overlapping rates result in higher difficulty in maintaining the data utility of target patterns, as they are more impaired by the privacy protection employed on the shared events between private and target patterns. D. COMPUTATIONAL COMPLEXITY

We investigate the computational complexity of the stepwise approach for opaque data stream analysis, as it puts the heaviest workload on data producers and consumers devices. 25% of each dataset is randomly selected as the historical VOLUME ,

dataset required by step-wise. We conduct the evaluation by measuring (1) the delay introduced on data producers devices (2) and the computational time on data consumers devices w.r.t. the number of data producers. We assume that the computing power of data producers and consumers devices, e.g., smartphones and servers, exceeds that of a Raspberry Pi. Therefore, a satisfactory computational complexity on the Raspberry Pi must be practical for data producers and consumers. To measure latency, we execute the step-wise approach with a streamed Ads dataset in 20 events per second and measure the processing time for each event. The step-wise approach introduces for each event an average 19ms delay (standard deviation 3.7ms, min 11ms, and max 33ms). Since it is not a performance-optimized Python implementation, we conclude that data producers devices can execute the PPM without introducing latency issues for typical applications. To measure the computational time, we evaluate the worst case in which one data consumer serves multiple distinct data producers. In detail, the computation on data consumers devices is mainly introduced in the setup phase when calculating data utilities for the step-wise approach. In the worst case, each data producer requires a new data utility calculation based on its unique data stream schema and target patterns, while in practice, multiple data producers usually have the same data schema and target patterns so that the calculated data utilities can be cached, which significantly reduces the computational time. The evaluation shows that the computational time increases by 0.664 seconds per new producer, following a linear relationship. The amount of computational time and its linearly increasing behavior indicate a satisfactory computational complexity of our PPM in the worst case. IX. CONCLUSION

State-of-the-art PPMs in CEP systems often result in redundant privacy safeguards, compromising the data utility. To reduce this redundancy, we introduced in this article novel pattern-level solutions that lead to superior performance w.r.t. data utility under equally strong privacy protection as existing solutions. The core idea is to (1) guarantee DP for 11

Author et al.:

private patterns and (2) leverage knowledge about private and target patterns to fine-tune the distribution of privacy budgets to maximize data utility. In transparent data stream analysis, private and target patterns are available to craft a PPM, while in opaque data stream analysis, data consumers do not reveal their target patterns. This challenge is addressed by giving data consumers the incentive of higher data utility when contributing to the implementation of a tailored PPM. All the assistance that data consumers need to provide is observation spans of the target patterns and evaluations of data utility. With this assistance, we have designed two PPMs for opaque data stream analysis that achieve patternlevel DP and are superior to existing solutions w.r.t. data utility. The core contributions of this work are: (1) A new solid theoretical foundation for privacy protections at the pattern level. (2) Four novel PPMs for transparent and opaque data stream analysis that provide pattern-level DP and superior data utility compared to existing works. (3) Experiments for a comparative study with three datasets demonstrating the improvements of the pattern-level PPMs compared to existing works. (4) A simulation-based study to systematically evaluate the performance and behaviors of our PPMs for a wide range of potential scenarios. This work is based on the common assumption for most related studies that all private information is well-defined by data producers. However, in future work, we see the potential to modify this assumption so that data producers with little privacy expertise can be automatically assisted to identify and define their privacy requirements. REFERENCES [1] S. S. Kumar, R. Chandra, and S. Agarwal, “A real-time approach for smart building operations prediction using rule-based complex event processing and sparql query,” The Journal of Supercomputing, vol. 80, no. 15, pp. 21 569–21 591, 2024. [2] K. A. Alaghbari, M. H. M. Saad, A. Hussain, and M. R. Alam, “Complex event processing for physical and cyber security in datacentresrecent progress, challenges and recommendations,” Journal of Cloud Computing, vol. 11, no. 1, p. 65, 2022. [3] S. S. Kumar and S. Agarwal, “Rule based complex event processing for iot applications: Review, classification and challenges,” Expert Systems, vol. 41, no. 9, p. e13597, 2024. [4] A. Grez, C. Riveros, M. Ugarte, and S. Vansummeren, “A formal framework for complex event recognition,” ACM Transactions on Database Systems (TODS), vol. 46, no. 4, pp. 1–49, 2021. [5] M. Fragkoulis, P. Carbone, V. Kalavri, and A. Katsifodimos, “A survey on the evolution of stream processing systems,” The VLDB Journal, vol. 33, no. 2, pp. 507–541, 2024. [6] H. Fichtenberger, M. Henzinger, and W. Ost, “Differentially private algorithms for graphs under continual observation,” arXiv preprint arXiv:2106.14756, 2021. [7] C. Dwork, M. Naor, T. Pitassi, and G. N. Rothblum, “Differential privacy under continual observation,” in Proceedings of the fortysecond ACM symposium on Theory of computing, 2010, pp. 715–724. [8] Y. Chen, A. Machanavajjhala, M. Hay, and G. Miklau, “Pegasus: Dataadaptive differentially private stream processing,” in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017, pp. 1375–1388. [9] H. Gu, T. Plagemann, M. Benndorf, V. Goebel, and B. Koldehofe, “Differential privacy for protecting private patterns in data streams,” 2023. [10] S. M. Palanisamy, “Towards multiple pattern type privacy protection in complex event processing through event obfuscation strategies,” in

Data Privacy Management, Cryptocurrencies and Blockchain Technology: ESORICS 2020 International Workshops, DPM 2020 and CBT 2020, Guildford, UK, September 17–18, 2020, Revised Selected Papers 15. Springer, 2020, pp. 178–194. [11] M. L. Delouee, V. Degeler, P. Amthor, and B. Koldehofe, “App-cep: Adaptive pattern-level privacy protection in complex event processing systems,” in International Conference on Information Systems Security and Privacy (ICISSP’24). SCITEPRESS–Science and Technology Publications, 2023. [12] X. Ren, L. Shi, W. Yu, S. Yang, C. Zhao, and Z. Xu, “Ldp-ids: Local differential privacy for infinite data streams,” in Proceedings of the 2022 International Conference on Management of Data, 2022, pp. 1064–1077. [13] A. Grez, C. Riveros, and M. Ugarte, “Foundations of complex event processing,” CoRR, vol. abs/1709.05369, 2017. [14] G. Kellaris, S. Papadopoulos, X. Xiao, and D. Papadias, “Differentially private event sequences over infinite streams,” Proceedings of the VLDB Endowment, vol. 7, no. 12, pp. 1155–1166, 2014. [15] C. Dwork, “Differential privacy in new settings,” in Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 2010, pp. 174–183. [16] R. Chen, Y. Shen, and H. Jin, “Private analysis of infinite data streams via retroactive grouping,” in Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, 2015, pp. 1061–1070. [17] U. Sopaoglu and O. Abul, “Classification utility aware data stream anonymization,” Applied Soft Computing, vol. 110, p. 107743, 2021. [18] B. Zhou, Y. Han, J. Pei, B. Jiang, Y. Tao, and Y. Jia, “Continuous privacy preserving publishing of data streams,” in Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, 2009, pp. 648–659. [19] M. Katsomallos, K. Tzompanaki, and D. Kotzinos, “Landmark privacy: Configurable differential privacy protection for time series,” in Proceedings of the Twelfth ACM Conference on Data and Application Security and Privacy, 2022, pp. 179–190. [20] S. M. Palanisamy, F. Dürr, M. A. Tariq, and K. Rothermel, “Preserving privacy and quality of service in complex event processing through event reordering,” in Proceedings of the 12th ACM International Conference on Distributed and Event-based Systems, 2018, pp. 40– 51. [21] Z. Wang, W. Liu, X. Pang, J. Ren, Z. Liu, and Y. Chen, “Towards pattern-aware privacy-preserving real-time data collection,” in IEEE INFOCOM 2020-IEEE Conference on Computer Communications. IEEE, 2020, pp. 109–118. [22] Y. Mao, Q. Ye, H. Hu, Q. Wang, and K. Huang, “Privshape: Extracting shapes in time series under user-level local differential privacy,” in 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 2024, pp. 1739–1751. [23] Y. Hu, Y. Du, Z. Zhang, Z. Fang, L. Chen, K. Zheng, and Y. Gao, “Real-time trajectory synthesis with local differential privacy,” in 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 2024, pp. 1685–1698. [24] Y. Sasaki et al., “The truth of the f-measure,” Teach tutor mater, vol. 1, no. 5, pp. 1–5, 2007. [25] C. Dwork, A. Roth et al., “The algorithmic foundations of differential privacy,” Foundations and Trends® in Theoretical Computer Science, vol. 9, no. 3–4, pp. 211–407, 2014. [26] Y. Zheng. (2011) T-drive trajectory data sample. [Online]. Available: https://www.microsoft.com/en-us/research/ publication/t-drive-trajectory-data-sample/ [27] J. Yuan, Y. Zheng, C. Zhang, W. Xie, X. Xie, G. Sun, and Y. Huang, “T-drive: driving directions based on taxi trajectories,” in Proceedings of the 18th SIGSPATIAL International conference on advances in geographic information systems, 2010, pp. 99–108. [28] J. Yuan, Y. Zheng, X. Xie, and G. Sun, “Driving with knowledge from the physical world,” in Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, 2011, pp. 316–324. [29] Tianchixiaomiaomeng. (2018) Ad display/click data on taobao.com. [Online]. Available: https://tianchi.aliyun.com/dataset/56 [30] Tianchi, “Taobao dataset for click-through rate prediction,” 2018. [Online]. Available: https://tianchi.aliyun.com/dataset/dataDetail? dataId=56

VOLUME ,

Record · ID 1028608 · SHA-256 d4facdd22693e72c
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.