# Differentially Private Web Browsing Trajectory over Infinite Streams

Authors: Xiang Liu; Yuchun Guo; Xiaoying Tan; Yishuai Chen
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Nowadays, a lot of data mining applications, such as web traffic analysis and content popularity prediction, leverage users’ web browsing trajectories to improve their performance. However, the disclosure of web browsing trajectory is the most prominent issue. A novel privacy model, named Differential Privacy, is used to rigorously protect user’s privacy. Some works have applied this privacy model to spatial-temporal streams. However, these works either protect the users’ activities in different places separately or protect their activities in all places jointly. The former one cannot protect trajectories that traverse multiple places; while the latter ignores the differences among places and suffers the degradation of data utility (i.e., data accuracy). In this paper, we propose aw,n-differential privacy to protect any spatial-temporal sequence occurring in w successive timestamps and n-range places. To achieve better data utility, we propose two implementation algorithms, named Spatial-Temporal Budget Distribution (STBD) and Spatial-Temporal RescueDP (STR). Theoretical analysis and experimental results show that these two algorithms can achieve a balance between data utility and trajectory privacy guarantee.


---

## Body

## 1. Introduction

Service providers collect users’ web browsing activities and share them with many data mining applications, such as web traffic analysis and content popularity prediction. Figure1 shows a typical data publishing system. A trusted curator aggregates users’ visiting activities (a.k.a “events”) and publishes the number of visits to each page periodically. The published data is a spatial-temporal stream. A user’s web browsing trajectory is a sequence of timestamped visiting activities. Web browsing trajectories can reveal users’ sensitive information, such as user preference. Therefore, the published stream should be protected to prevent the leakage of trajectory privacy.Figure 1
Data publishing system. (a) Event-level, user-level, place-level, and whole-level privacy and (b) a spatial-temporal window coversw timestamps and n-range places.
(a)(b)A lot of excellent works [1–5] have been conducted to protect users’ privacy in statistic data. Among all these works, the state-of-the-art privacy model is differential privacy [5], which can provide rigorous privacy guarantees. A differential privacy model takes a dataset as the input and outputs sanitized statistic data that remain roughly the same even if any single record in the dataset is absent. Given the output, people cannot tell whether a record is included in the original dataset or not.Some recent works have studied the problem of releasing the spatial-temporal stream with differential privacy. According to their protection range on the time dimension, privacy models are divided into two categories: event-level privacy and user-level privacy, which are represented in Figure1(a). Event-level privacy [6–8] protects the events on different timestamps independently. In contrast, user-level privacy [9, 10] protects users’ events on all timestamps jointly. The former cannot protect the trajectories that have multiple events. The latter cannot be applied to infinite streams. The reason is that the length of a user’s event sequence is infinite, which requires an infinite amount of perturbation noise. To bridge the gap between event-level privacy and user-level privacy, Kellaris et al. [11] propose the w-event differential privacy, which protects any event sequence occurring in successive w timestamps.According to the protection range on the spatial dimension, we further categorize privacy models into two new types: place-level privacy and whole-level privacy, as shown in Figure1(a). Place-level privacy protects the events on different places (i.e., pages) separately [10, 12, 13], whereas whole-level privacy protects the events on all places jointly [11, 14]. Since a trajectory can traverse multiple places, the place-level privacy fails to protect the trajectory privacy. However, whole-level privacy ignores the characteristics of data among different places, resulting in lower data utility (i.e., data accuracy). Specifically, the data series on different pages always have different characteristics. But whole-level privacy perturbs the data on different places with the same random noise and publishes the data on different places with the same publication cycle.To bridge the gap between place-level privacy and whole-level privacy, it is necessary to design a new privacy model that can protect event sequences occurring in multiple places, e.g.,n places.Since the webspace is a high-dimensional space, we cannot simply arrange all pages in different rows as in Figure1(a). Researchers usually describe the webspace as a page graph, which is shown in Figure 1(b). Intuitively, the web pages that a user browses during a short period, e.g., w successive timestamps, are related or similar. In other words, web browsing trajectories are located around a center node (e.g., topic). Therefore, in this page graph, we define that an n-range spatial window covers a center node with its n−1-hop neighbors. Given this definition, we can propose a novel privacy model, w,n-differential privacy, to protect any spatial-temporal sequence occurring in any spatial-temporal window of w successive timestamps and n-range paces. When n=1 or N, where an N-range window covers all places, it is equivalent to place-level privacy or whole-level privacy. To provide a strong trajectory privacy guarantee, we can choose a spatial-temporal window that can cover most trajectories. Furthermore, w,n-differential privacy allows the data on different pages to have different perturbation noises and different publication cycles. Therefore, we can design effective implementation algorithms, which can adaptively allocate the privacy budget that controls the scale of perturbation noise and dynamically publish data according to data change. In addition to protecting web browsing trajectories, this work is also suitable for other privacy protection scenarios [15], especially non-Euclidean spaces. For example, we can use it to protect user transaction data between banks, the information flow in social networks, etc. Our contributions are summarized as follows:(1)
We demonstrate the way to construct the spatial window. Generally, the pages visited by a user within a short period, i.e.,w successive timestamps, are similar or related. Therefore, we use a deep learning model to obtain the page similarity, and then we construct a page graph G, where two similar pages are connected by an edge. In G, we define that a spatial window of size n covers a page with its n−1-hop neighbor pages.(2)
We formulatew,n-differential privacy and design two implementation algorithms, Spatial-Temporal Budget Distribution (STBD) and Spatial-temporal RescueDP (STR). These two algorithms detect the data change and publish data when data change significantly. They also efficiently allocate the privacy budget for each publication to ensure that they can achieve better data utility and satisfy w,n-differential privacy.(3)
We compare our algorithms with two baseline algorithms, BD and RescueDP. These two algorithms belong tow,1-differential privacy and w,N-differential privacy, respectively. Experimental results on a real-world dataset show that the proposed two algorithms can achieve a balance between data utility and trajectory privacy guarantee.(4)
This work can be further applied to other privacy protection scenarios, especially non-Euclidean spaces, such as protecting user transaction data between banks and information flow in social networks.The remainder of this paper is organized as follows. Section2 surveys the related work and provides the preliminaries on differential privacy. Section 3 proposes our privacy model. Section 4 presents the STBD and STR algorithm, as well as their technical details. Section 5 presents a set of empirical studies and results. Section 6 concludes this paper.


## 2. Related Work and Preliminaries

### 2.1. Related Work

(1) Differential Privacy. Dwork et al. [5] firstly propose the differential privacy to rigorously protect individual privacy. Then, many works [16–20] apply it to the static dataset, which will not be updated in the future.For streaming data, Dwork et al. [6] give the definitions of event-level privacy and user-level privacy and propose a “counter” algorithm to achieve event-level privacy. RTP-DMM algorithm [8] uses a Fenwick tree to reorganize data items in the stream and uses a matrix mechanism to reduce the global sensitivity. Compared with the “counter” algorithm, RTP-DMM achieves better data utility. Sun et al. [7] propose the PriStream algorithm to protect the thresholded percentile statistics under event-level privacy. Chen et al. [21] propose an event-level privacy model, PeGaSus, to simultaneously support a variety of tasks, such as counts, sliding windows, and event monitoring. To achieve user-level privacy on finite streams, Acs and Castelluccia [10] use Fourier Perturbation Algorithm [22] to perturb the data streams, and Fan and Xiong [9] propose the FAST algorithm. To bridge the gap between event-level privacy and user-level privacy, Kellaris et al. [11] propose the w-event differential privacy and its implementation algorithm, BD algorithm. Ren et al. [23] propose the average w-event differential privacy to relax the requirement of privacy budget consumed in w timestamps.The algorithm in [10] protects the finite data series on each place separately. RescueDP [12] and AdaPub [13] independently protect the infinite data series on each place under w-event differential privacy. All these algorithms belong to the place-level privacy, which cannot rigorously protect trajectory privacy. Works [11, 14] perturb the data on different places with the same noise and publish data with the same publication cycle. Thus, they belong to whole-level privacy. Since whole-level privacy considers all places as a whole, it ignores the differences among places and achieves lower data utility. To reduce the impact of data sparsity on the spatial dimension, work [24] uses a Quadtree to group similar places together. Our previous work [25] proposes a w,n-differential privacy algorithm for protecting users’ GPS trajectories. Because the GPS points are located in the 2D Euclidean plane, the n-range spatial window is a square area of size n×n. This algorithm cannot be applied to the non-Euclidean webspace. Works [26, 27] perturb the activities within a trajectory and publish the sanitized trajectory. However, this paper aims to protect aggregated statistic data from the leakage of trajectory privacy. DADP [28] and DPCrowd [29] consider a different scenario, where the system contains multiple servers aggregating partial crowd-sourced data.(2) Page Graph. Works [30–32] build a page graph, where the nodes are pages and the directed edges are hyperlinks. Since the hyperlinks are added by the authors, this kind of page graph cannot reflect the page relationship in users’ minds. Considering users’ click behaviors, Yu and Iwaihara [33] construct a click graph, where the directed and weighted edges represent click counts on each hyperlink. However, click counts often exhibit a power-law distribution [34], which makes the click graph sparse and unconnected. Inspired by recent researches on representational learning for natural language processing (NLP), Bing et al. [35] propose the session2vec algorithm extended from word2vec [36] to obtain the feature representations of pages. Their experimental results show that the cosine similarity of features can represent the relationship between any two pages.


### 2.2. Differential Privacy

Differential privacy is a rigorous privacy model proposed by Dwork et al. [5]. Intuitively, given a randomized mechanism K, differential privacy requires that the output of K is insensitive to the change of a single record in the input of K. The formal definition of differential privacy is given as follows.Definition 1.
ε-differential privacy [5].
A randomized mechanismK satisfies ε-differential privacy, if for any two datasets D and D′ differing on at most one record, and for any possible output O∈RangeK,(1)PrKD=O≤eε×PrKD′=O,where the probability is taken over the randomness of K.
The parameterε controls the degree of privacy protection. A lower value of ε offers a stronger privacy guarantee. Two datasets D and D′ that differ on at most one record are called neighboring datasets.
Laplace mechanism is the most commonly used mechanism that satisfiesε-differential privacy. Its main idea is to add Laplace random noise to the statistic data.Definition 2.
Sensitivity [5].
For any functionq:D⟶ℝd, the sensitivity of q is Δq=maxD,D′qD−qD′1 for any two neighboring datasets D and D′.
The sensitivity of functionq is the maximum L1 distance between function outputs of any two neighboring datasets D and D′.Theorem 1.
Laplace mechanism [5].
For any functionq:D⟶ℝd, the mechanism K(2)KD=qD+<ℒ10,△qε,…,ℒd0,△qε>,satisfies ε-differential privacy, if ℒi0,△q/ε are i.i.d zero-mean Laplace noises with scale △q/ε.A smaller value ofε offers a larger scale of Laplace noise and a stronger privacy guarantee. Differential privacy maintains two composition properties, which are given as follows.Theorem 2.
Sequential Composition [37].
Let {K1,K2,…,KT} be a set of mechanisms, and each Kt provides εt-differential privacy, where t∈1,T. Let K be another mechanism that executes K1D, K2D, …, KTD independently and returns the outputs of these mechanisms. Then, K satisfies ∑t=1Tεt-differential privacy.Theorem 2 allows us to distributeε among T independent mechanisms. Therefore, ε is called the privacy budget.Theorem 3.
Parallel Composition [37].
Let {D1,D2,…,DM} be a set of disjoint subsets of dataset D. Let {K1, K2, …, KM} be a set of mechanisms, and each Km provides εm-differential privacy, where m∈1,M. Let K be another mechanism that executes K1D1, K2D2, …, KMDM independently and returns the outputs of these mechanisms. Then, K satisfies max1≤m≤Mεm-differential privacy.If a dataset is partitioned into disjoint subsets, and each part is protected under differential privacy, then the ultimate privacy guarantee depends on the worst of the guarantees.


### 2.3.w-Event Differential Privacy

w-event differential privacy [11] (short for w-event ε-differential privacy) is used to protect any event sequence occurring in w timestamps. An infinite stream is denoted by S=D1,D2,…,Dt,…, where Dt denotes the dataset on timestamp t. A prefix of stream S of length T is denoted by ST=D1,D2,…,DT. The definition of two w-neighboring prefixes is given as follows.Definition 3.
w-neighboring [11].
Letw be a positive integer. Two stream prefixes ST and ST′ are w-neighboring if(1)
for eachDt,Dt′ such that t∈1,T and Dt≠Dt′, it holds that Dt,Dt′ are neighboring, and(2)
for eachDt,Dt′,Dτ,Dτ′ with 1≤t<τ≤T, Dt≠Dt′ and Dτ≠Dτ′, it holds that τ−t+1≤w.
Concretely, ifST,ST′ are w-neighboring prefixes, then (1) their pairwise elements Dt and Dt′, where t∈1,T, are the same or neighboring, and (2) all neighboring element pairs can fit in a window of w timestamps.Definition 4.
w-event ε-differential privacy [11].
A mechanismK satisfies w-event ε-differential privacy, if, for any two w-neighboring stream prefixes ST, ST′, any possible output O∈RangeK, and any T>0,(3)PrKST=O≤eε×PrKST′=O.
According to Theorem2, to satisfy w-event differential privacy, a privacy mechanism can distribute the privacy budget ε to several mechanisms that protect the data on different timestamps independently.Theorem 4.
Implementation ofw-event differential privacy [11].
LetK be a mechanism that takes a stream prefix ST=D1,D2,…,DT as the input and outputs OT=o1,o2,…,oT∈RangeK. Suppose that we can decompose K into T mechanisms K1,K2,…,KT, such that ot=KtDt, where t∈1,T, and each Kt satisfies εt-differential privacy independently. Then, K satisfies w-event ε-differential privacy if(4)∑t=τ−w+1τεt≤ε,∀τ∈1,T.


### 2.4. Dataset

In this paper, we use a real-world dataset, the WorldCup98 dataset [38]. This dataset contains 1.3 billion logs of the requests to the FIFA 1998 website from 2.76 million clients from April 30, 1998, to July 26, 1998. Each log contains client ID, URL, and timestamp. We choose 10000 most popular URLs from June 15, 1998, to June 30, 1998, and publish the number of visits every 30 minutes.


## 2.1. Related Work

(1) Differential Privacy. Dwork et al. [5] firstly propose the differential privacy to rigorously protect individual privacy. Then, many works [16–20] apply it to the static dataset, which will not be updated in the future.For streaming data, Dwork et al. [6] give the definitions of event-level privacy and user-level privacy and propose a “counter” algorithm to achieve event-level privacy. RTP-DMM algorithm [8] uses a Fenwick tree to reorganize data items in the stream and uses a matrix mechanism to reduce the global sensitivity. Compared with the “counter” algorithm, RTP-DMM achieves better data utility. Sun et al. [7] propose the PriStream algorithm to protect the thresholded percentile statistics under event-level privacy. Chen et al. [21] propose an event-level privacy model, PeGaSus, to simultaneously support a variety of tasks, such as counts, sliding windows, and event monitoring. To achieve user-level privacy on finite streams, Acs and Castelluccia [10] use Fourier Perturbation Algorithm [22] to perturb the data streams, and Fan and Xiong [9] propose the FAST algorithm. To bridge the gap between event-level privacy and user-level privacy, Kellaris et al. [11] propose the w-event differential privacy and its implementation algorithm, BD algorithm. Ren et al. [23] propose the average w-event differential privacy to relax the requirement of privacy budget consumed in w timestamps.The algorithm in [10] protects the finite data series on each place separately. RescueDP [12] and AdaPub [13] independently protect the infinite data series on each place under w-event differential privacy. All these algorithms belong to the place-level privacy, which cannot rigorously protect trajectory privacy. Works [11, 14] perturb the data on different places with the same noise and publish data with the same publication cycle. Thus, they belong to whole-level privacy. Since whole-level privacy considers all places as a whole, it ignores the differences among places and achieves lower data utility. To reduce the impact of data sparsity on the spatial dimension, work [24] uses a Quadtree to group similar places together. Our previous work [25] proposes a w,n-differential privacy algorithm for protecting users’ GPS trajectories. Because the GPS points are located in the 2D Euclidean plane, the n-range spatial window is a square area of size n×n. This algorithm cannot be applied to the non-Euclidean webspace. Works [26, 27] perturb the activities within a trajectory and publish the sanitized trajectory. However, this paper aims to protect aggregated statistic data from the leakage of trajectory privacy. DADP [28] and DPCrowd [29] consider a different scenario, where the system contains multiple servers aggregating partial crowd-sourced data.(2) Page Graph. Works [30–32] build a page graph, where the nodes are pages and the directed edges are hyperlinks. Since the hyperlinks are added by the authors, this kind of page graph cannot reflect the page relationship in users’ minds. Considering users’ click behaviors, Yu and Iwaihara [33] construct a click graph, where the directed and weighted edges represent click counts on each hyperlink. However, click counts often exhibit a power-law distribution [34], which makes the click graph sparse and unconnected. Inspired by recent researches on representational learning for natural language processing (NLP), Bing et al. [35] propose the session2vec algorithm extended from word2vec [36] to obtain the feature representations of pages. Their experimental results show that the cosine similarity of features can represent the relationship between any two pages.


## 2.2. Differential Privacy

Differential privacy is a rigorous privacy model proposed by Dwork et al. [5]. Intuitively, given a randomized mechanism K, differential privacy requires that the output of K is insensitive to the change of a single record in the input of K. The formal definition of differential privacy is given as follows.Definition 1.
ε-differential privacy [5].
A randomized mechanismK satisfies ε-differential privacy, if for any two datasets D and D′ differing on at most one record, and for any possible output O∈RangeK,(1)PrKD=O≤eε×PrKD′=O,where the probability is taken over the randomness of K.
The parameterε controls the degree of privacy protection. A lower value of ε offers a stronger privacy guarantee. Two datasets D and D′ that differ on at most one record are called neighboring datasets.
Laplace mechanism is the most commonly used mechanism that satisfiesε-differential privacy. Its main idea is to add Laplace random noise to the statistic data.Definition 2.
Sensitivity [5].
For any functionq:D⟶ℝd, the sensitivity of q is Δq=maxD,D′qD−qD′1 for any two neighboring datasets D and D′.
The sensitivity of functionq is the maximum L1 distance between function outputs of any two neighboring datasets D and D′.Theorem 1.
Laplace mechanism [5].
For any functionq:D⟶ℝd, the mechanism K(2)KD=qD+<ℒ10,△qε,…,ℒd0,△qε>,satisfies ε-differential privacy, if ℒi0,△q/ε are i.i.d zero-mean Laplace noises with scale △q/ε.A smaller value ofε offers a larger scale of Laplace noise and a stronger privacy guarantee. Differential privacy maintains two composition properties, which are given as follows.Theorem 2.
Sequential Composition [37].
Let {K1,K2,…,KT} be a set of mechanisms, and each Kt provides εt-differential privacy, where t∈1,T. Let K be another mechanism that executes K1D, K2D, …, KTD independently and returns the outputs of these mechanisms. Then, K satisfies ∑t=1Tεt-differential privacy.Theorem 2 allows us to distributeε among T independent mechanisms. Therefore, ε is called the privacy budget.Theorem 3.
Parallel Composition [37].
Let {D1,D2,…,DM} be a set of disjoint subsets of dataset D. Let {K1, K2, …, KM} be a set of mechanisms, and each Km provides εm-differential privacy, where m∈1,M. Let K be another mechanism that executes K1D1, K2D2, …, KMDM independently and returns the outputs of these mechanisms. Then, K satisfies max1≤m≤Mεm-differential privacy.If a dataset is partitioned into disjoint subsets, and each part is protected under differential privacy, then the ultimate privacy guarantee depends on the worst of the guarantees.


## 2.3.w-Event Differential Privacy

w-event differential privacy [11] (short for w-event ε-differential privacy) is used to protect any event sequence occurring in w timestamps. An infinite stream is denoted by S=D1,D2,…,Dt,…, where Dt denotes the dataset on timestamp t. A prefix of stream S of length T is denoted by ST=D1,D2,…,DT. The definition of two w-neighboring prefixes is given as follows.Definition 3.
w-neighboring [11].
Letw be a positive integer. Two stream prefixes ST and ST′ are w-neighboring if(1)
for eachDt,Dt′ such that t∈1,T and Dt≠Dt′, it holds that Dt,Dt′ are neighboring, and(2)
for eachDt,Dt′,Dτ,Dτ′ with 1≤t<τ≤T, Dt≠Dt′ and Dτ≠Dτ′, it holds that τ−t+1≤w.
Concretely, ifST,ST′ are w-neighboring prefixes, then (1) their pairwise elements Dt and Dt′, where t∈1,T, are the same or neighboring, and (2) all neighboring element pairs can fit in a window of w timestamps.Definition 4.
w-event ε-differential privacy [11].
A mechanismK satisfies w-event ε-differential privacy, if, for any two w-neighboring stream prefixes ST, ST′, any possible output O∈RangeK, and any T>0,(3)PrKST=O≤eε×PrKST′=O.
According to Theorem2, to satisfy w-event differential privacy, a privacy mechanism can distribute the privacy budget ε to several mechanisms that protect the data on different timestamps independently.Theorem 4.
Implementation ofw-event differential privacy [11].
LetK be a mechanism that takes a stream prefix ST=D1,D2,…,DT as the input and outputs OT=o1,o2,…,oT∈RangeK. Suppose that we can decompose K into T mechanisms K1,K2,…,KT, such that ot=KtDt, where t∈1,T, and each Kt satisfies εt-differential privacy independently. Then, K satisfies w-event ε-differential privacy if(4)∑t=τ−w+1τεt≤ε,∀τ∈1,T.


## 2.4. Dataset

In this paper, we use a real-world dataset, the WorldCup98 dataset [38]. This dataset contains 1.3 billion logs of the requests to the FIFA 1998 website from 2.76 million clients from April 30, 1998, to July 26, 1998. Each log contains client ID, URL, and timestamp. We choose 10000 most popular URLs from June 15, 1998, to June 30, 1998, and publish the number of visits every 30 minutes.


## 3. Privacy Model

We study the problem of how to publish the number of visits to each web page while protecting user browsing trajectories. A web browsing trajectory is defined as a sequence of web pages visited by a user with timestamps. Generally, the pages visited by a user during a short period are most likely to be similar or related. In other words, users’ trajectories can fit into a spatial-temporal window that covers a group of similar pages and several successive timestamps. Therefore, to provide a strong trajectory privacy guarantee, we propose a privacy model that can protect any possible spatial-temporal sequence within a spatial-temporal window. In this section, we first construct a page graph and introduce the idea of the spatial-temporal window. Then, we formulate our privacy model.


### 3.1. Page Graph

Inspired by [35, 36], we use the word2vec algorithm to obtain the similarity between pages. The source code is available at [39]. We use the logs on June 15, 1998, as the training data. The embedding size, context window, and learning rate are set to 128, 3, and 0.001, respectively. After training 100000 steps with Adam optimizer [40], we obtain the feature vectors of pages. If the cosine similarity of two pages is higher than ρ, we connect them with an unweighted and undirected edge. We also connect each page to the other two pages, which are the top 2 similar pages among all pages to ensure that we can obtain a connected graph.Ifρ is too large, the generated graph will become very sparse. On the contrary, if ρ becomes too small, pages will directly connect to each other and the graph will become very dense. We test ρ from 0.1 to 0.8 and find that when ρ=0.4, pages will have a proper distance to other pages.We useG to denote this page graph, which contains 10000 nodes and 28594 edges. The maximum and minimum node degree are 96 and 2, respectively. Figure 2 shows the degree distribution in the log-log plot. We can observe that the distribution approximately follows the power-law [41], and the exponent of the power-law is 2.46.Figure 2
Degree distribution.The distance between two connected pages is 1, and the distance between two unconnected pages is the length of the shortest path inG. As shown in Figure 3, the distance between page 1 and page 2 is 1. Since the shorted path from page 1 to page 4 is 1⟶2⟶3⟶4, the distance between page 1 and page 4 is 3. We also call page 1 as a 1-hop neighborhood of page 2 and a 3-hop neighborhood of page 4. Note that a user can visit the pages that are not directly connected to each other, and then the trajectory will not be a continuous path in G. Given the distance between pages, we define the spatial range of a trajectory as follows.Figure 3
Example of the page graph.Definition 5.
The spatial range of a web browsing trajectory.
Given a graphG and a web browsing trajectory, the center of this trajectory is a page, whose greatest distance to all pages in the trajectory is as small as possible. This distance is the spatial range of the trajectory.
Trajectory center can be regarded as the “topic” of this trajectory, and the spatial range represents the “topic scope.” The trajectory center is not necessarily included in the trajectory. For example, in Figure3, the greatest distance from page 1 to pages 8, 2, and 6 is 1, while the greatest distance from other pages to pages 8, 2, and 6 is larger than 1. Therefore, the center of trajectory A is page 1, and its spatial range is 1. Similarly, the center of trajectory B is page 2, and its spatial range is 2.
Given a page, we define that a spatial window of sizen (n-range spatial window) covers the page with its n−1-hop neighborhoods. As shown in Figure 3, the spatial window 1 takes page 8 as the center and covers page 8 and page 1. Similarly, the spatial window 2 takes page 1 as the center and covers page 1, page 2, page 6, and page 8. If the spatial range of a trajectory is n, this trajectory can be covered by a spatial window of size n+1. In G, a spatial window of size 9 can cover all pages. A temporal window of size w covers w successive timestamps. We use w,n to denote the size of a spatial-temporal window, where the first element is the temporal size, and the second element is the spatial size.
We randomly select 50,000 users and analyze the spatial range of their trajectories duringw timestamps. The interval between two consecutive timestamps is 30 minutes. The results are shown in Table 1. When w=120, the spatial range of 88.7% of the trajectories is less than 5. Thus, a spatial-temporal window of 120 successive timestamps and 6-range places can cover most trajectories.Table 1
Spatial range of trajectories duringw timestamps.
%nw408012016020003.373.072.852.672.56114.0512.8711.9611.2710.74226.4924.4822.7821.4620.47348.1144.4641.6139.4137.81484.1378.5774.5771.1468.75596.1692.0388.785.5383.4699.2197.2695.1993.5792.41710010099.9999.9899.938100100100100100


### 3.2.w,n-Differential Privacy

Without loss of generality, we assume that there areM pages hosted on a server. A user can visit at most l≪M pages per timestamp. A trusted curator collects users’ visiting activities and creates a dataset Dt at each timestamp t. This infinite stream is denoted by S=D1,D2,…. We define a stream prefix of S as ST=D1,D2,…,DT. Dataset Dt can be partitioned into M disjoint subsets Dt1,Dt2,…,DtM, where Dtm contains users’ visiting activities to page m at timestamp t. A query function q asks for the number of visits on each page. Then, qDt=qDt1,qDt2,…,qDtM=rt=rt1,rt2,…,rtM, where rtm denotes the number of visits on page m at timestamp t. w,n-differential privacy protects any spatial-temporal sequence occurring in any spatial-temporal window of w timestamps and n-range places. The formal definition is given as follows.Definition 6.
w,n-neighboring.
Letw and n be two positive integers. Two spatial-temporal stream prefixes ST and ST′ are w,n-neighboring if(1)
each pair ofDtm, D′tm is neighboring or the same and(2)
all neighboring pairsDtm, D′tm can fit into a spatial-temporal window of size w,n.
The above definition means that twow,n-neighboring stream prefixes differ on a single spatial-temporal sequence that can fit in a spatial-temporal window of size w,n. w,n-differential privacy ensures that the output results of any two w,n-neighboring stream prefixes are indistinguishable.Definition 7.
w-event n-range ε-differential privacy.
A mechanismK satisfies w-event n-range ε-differential privacy (short for w,n-differential privacy), if for any two w,n-neighboring prefixes ST and ST′, any possible output O∈RangeK, and any T>0,(5)PrKST=O≤eε×PrKST′=O.
This model can be widely used in various scenarios, where trajectories need to be protected. To implement this privacy model, we can decompose mechanismK into submechanisms Ktm, and each Ktm protects dataset Dtm under εtm-differential privacy independently. Then, we ensure that the total privacy budget inside any spatial-temporal window of size w,n is less than ε. Figure 4 gives an example. A spatial-temporal window of size 3,2 covers the data on page 1, page 2, page 6, and page 8 from t1 to t3. Since rt1,rt2,rt6,rt8 belong to disjoint datasets, the ultimate privacy guarantee is maxεt1,εt2,εt6,εt8-differential privacy based on Theorem 3. According to Theorem 2, the privacy guarantee inside this window is ∑t=13maxεt1,εt2,εt6,εt8-differential privacy. If ∑t=τ−2τmaxm∈winεtm<=ε for any τ∈1,T, and any 2-range spatial window win, mechanism K satisfies (3,2)-differential privacy.Figure 4
Example of the spatial-temporal window and privacy budget. (a) The spatial-temporal window, (b) number of visits, and (c) privacy budget.
(a)(b)(c)Theorem 5.
Implementation ofw,n-differential privacy.
LetK be a mechanism that takes a spatial-temporal stream prefix ST=D1,D2,…,DT as the input and outputs OT=o1,o2,…,oT∈RangeK, where Dt=Dt1,Dt2,…,DtM and ot=ot1,ot2,…,otM. Suppose that we can decompose K into T×M mechanisms Ktm, where t∈1,T,m∈1,M , such that otm=KtmDtm, and each Ktm satisfies εtm-differential privacy independently. Then, K satisfies w,n-differential privacy if(6)∑t=τ−w+1τmaxm∈winεtm≤ε,∀τ∈1,T,∀win∈n-range  spatial  windows.


## 3.1. Page Graph

Inspired by [35, 36], we use the word2vec algorithm to obtain the similarity between pages. The source code is available at [39]. We use the logs on June 15, 1998, as the training data. The embedding size, context window, and learning rate are set to 128, 3, and 0.001, respectively. After training 100000 steps with Adam optimizer [40], we obtain the feature vectors of pages. If the cosine similarity of two pages is higher than ρ, we connect them with an unweighted and undirected edge. We also connect each page to the other two pages, which are the top 2 similar pages among all pages to ensure that we can obtain a connected graph.Ifρ is too large, the generated graph will become very sparse. On the contrary, if ρ becomes too small, pages will directly connect to each other and the graph will become very dense. We test ρ from 0.1 to 0.8 and find that when ρ=0.4, pages will have a proper distance to other pages.We useG to denote this page graph, which contains 10000 nodes and 28594 edges. The maximum and minimum node degree are 96 and 2, respectively. Figure 2 shows the degree distribution in the log-log plot. We can observe that the distribution approximately follows the power-law [41], and the exponent of the power-law is 2.46.Figure 2
Degree distribution.The distance between two connected pages is 1, and the distance between two unconnected pages is the length of the shortest path inG. As shown in Figure 3, the distance between page 1 and page 2 is 1. Since the shorted path from page 1 to page 4 is 1⟶2⟶3⟶4, the distance between page 1 and page 4 is 3. We also call page 1 as a 1-hop neighborhood of page 2 and a 3-hop neighborhood of page 4. Note that a user can visit the pages that are not directly connected to each other, and then the trajectory will not be a continuous path in G. Given the distance between pages, we define the spatial range of a trajectory as follows.Figure 3
Example of the page graph.Definition 5.
The spatial range of a web browsing trajectory.
Given a graphG and a web browsing trajectory, the center of this trajectory is a page, whose greatest distance to all pages in the trajectory is as small as possible. This distance is the spatial range of the trajectory.
Trajectory center can be regarded as the “topic” of this trajectory, and the spatial range represents the “topic scope.” The trajectory center is not necessarily included in the trajectory. For example, in Figure3, the greatest distance from page 1 to pages 8, 2, and 6 is 1, while the greatest distance from other pages to pages 8, 2, and 6 is larger than 1. Therefore, the center of trajectory A is page 1, and its spatial range is 1. Similarly, the center of trajectory B is page 2, and its spatial range is 2.
Given a page, we define that a spatial window of sizen (n-range spatial window) covers the page with its n−1-hop neighborhoods. As shown in Figure 3, the spatial window 1 takes page 8 as the center and covers page 8 and page 1. Similarly, the spatial window 2 takes page 1 as the center and covers page 1, page 2, page 6, and page 8. If the spatial range of a trajectory is n, this trajectory can be covered by a spatial window of size n+1. In G, a spatial window of size 9 can cover all pages. A temporal window of size w covers w successive timestamps. We use w,n to denote the size of a spatial-temporal window, where the first element is the temporal size, and the second element is the spatial size.
We randomly select 50,000 users and analyze the spatial range of their trajectories duringw timestamps. The interval between two consecutive timestamps is 30 minutes. The results are shown in Table 1. When w=120, the spatial range of 88.7% of the trajectories is less than 5. Thus, a spatial-temporal window of 120 successive timestamps and 6-range places can cover most trajectories.Table 1
Spatial range of trajectories duringw timestamps.
%nw408012016020003.373.072.852.672.56114.0512.8711.9611.2710.74226.4924.4822.7821.4620.47348.1144.4641.6139.4137.81484.1378.5774.5771.1468.75596.1692.0388.785.5383.4699.2197.2695.1993.5792.41710010099.9999.9899.938100100100100100


## 3.2.w,n-Differential Privacy

Without loss of generality, we assume that there areM pages hosted on a server. A user can visit at most l≪M pages per timestamp. A trusted curator collects users’ visiting activities and creates a dataset Dt at each timestamp t. This infinite stream is denoted by S=D1,D2,…. We define a stream prefix of S as ST=D1,D2,…,DT. Dataset Dt can be partitioned into M disjoint subsets Dt1,Dt2,…,DtM, where Dtm contains users’ visiting activities to page m at timestamp t. A query function q asks for the number of visits on each page. Then, qDt=qDt1,qDt2,…,qDtM=rt=rt1,rt2,…,rtM, where rtm denotes the number of visits on page m at timestamp t. w,n-differential privacy protects any spatial-temporal sequence occurring in any spatial-temporal window of w timestamps and n-range places. The formal definition is given as follows.Definition 6.
w,n-neighboring.
Letw and n be two positive integers. Two spatial-temporal stream prefixes ST and ST′ are w,n-neighboring if(1)
each pair ofDtm, D′tm is neighboring or the same and(2)
all neighboring pairsDtm, D′tm can fit into a spatial-temporal window of size w,n.
The above definition means that twow,n-neighboring stream prefixes differ on a single spatial-temporal sequence that can fit in a spatial-temporal window of size w,n. w,n-differential privacy ensures that the output results of any two w,n-neighboring stream prefixes are indistinguishable.Definition 7.
w-event n-range ε-differential privacy.
A mechanismK satisfies w-event n-range ε-differential privacy (short for w,n-differential privacy), if for any two w,n-neighboring prefixes ST and ST′, any possible output O∈RangeK, and any T>0,(5)PrKST=O≤eε×PrKST′=O.
This model can be widely used in various scenarios, where trajectories need to be protected. To implement this privacy model, we can decompose mechanismK into submechanisms Ktm, and each Ktm protects dataset Dtm under εtm-differential privacy independently. Then, we ensure that the total privacy budget inside any spatial-temporal window of size w,n is less than ε. Figure 4 gives an example. A spatial-temporal window of size 3,2 covers the data on page 1, page 2, page 6, and page 8 from t1 to t3. Since rt1,rt2,rt6,rt8 belong to disjoint datasets, the ultimate privacy guarantee is maxεt1,εt2,εt6,εt8-differential privacy based on Theorem 3. According to Theorem 2, the privacy guarantee inside this window is ∑t=13maxεt1,εt2,εt6,εt8-differential privacy. If ∑t=τ−2τmaxm∈winεtm<=ε for any τ∈1,T, and any 2-range spatial window win, mechanism K satisfies (3,2)-differential privacy.Figure 4
Example of the spatial-temporal window and privacy budget. (a) The spatial-temporal window, (b) number of visits, and (c) privacy budget.
(a)(b)(c)Theorem 5.
Implementation ofw,n-differential privacy.
LetK be a mechanism that takes a spatial-temporal stream prefix ST=D1,D2,…,DT as the input and outputs OT=o1,o2,…,oT∈RangeK, where Dt=Dt1,Dt2,…,DtM and ot=ot1,ot2,…,otM. Suppose that we can decompose K into T×M mechanisms Ktm, where t∈1,T,m∈1,M , such that otm=KtmDtm, and each Ktm satisfies εtm-differential privacy independently. Then, K satisfies w,n-differential privacy if(6)∑t=τ−w+1τmaxm∈winεtm≤ε,∀τ∈1,T,∀win∈n-range  spatial  windows.


## 4. Algorithms

### 4.1. Spatial-Temporal Budget Distribution

The structure of the Spatial-Temporal Budget Distribution (STBD) algorithm is shown in Figure5. STBD consists of three components: evaluation, perturbation, and budget allocation. The evaluation component evaluates the data change and decides whether to publish new data at each timestamp. The perturbation component perturbs the data with Laplace noise and publishes the sanitized data. The budget allocation component distributes the privacy budget to each component. Our STBD algorithm is extended from the Budget Distribution (BD) algorithm [11]. STBD uses a new evaluation component to capture the data change on small page groups and uses a new budget allocation component to satisfy w,n-differential privacy. Algorithm 1 shows the pseudocode of the STBD algorithm.Algorithm 1: STBD algorithm.
Input:rτ,oτ−1Output:oτ,βτ1,…,βτM(1)
ατx,βτm← Budget Allocation//Evaluation(2)
for groupx do(3)
a_errτx¯=1/sizex∑m∈xrτm−oτ−1m+ℒ0,l/sizex/ατx(4)
for pagem∈x do(5)
a_errτm=a_errτx¯(6)
end for(7)
end for(8)
for pagem do(9)
p_errτm=l/βτm(10)
end for//Perturbation(11)
for pagem do(12)
ifa_errτm>p_errτm then(13)
oτm=rτm+ℒ0,l/βτm(14)
else(15)
oτm=oτ−1m(16)
βτm=0(17)
end if(18)
end for(19)
returnoτ,βτ1,…,βτMFigure 5
The structure of the STBD algorithm.


#### 4.1.1. Evaluation and Perturbation

Publishing data consumes the privacy budget, while the total privacy budget inside the spatial-temporal window is constant. If we publish data on every timestamp, the privacy budget for each publication becomes small, which results in significant perturbation noise. Conversely, if we skip some publications and approximate current data to previously published data, the perturbation noise decreases, while the approximation error increases. The approximation error is calculated as follows:(7)a_errtm=rtm−ot−1m+ℒ0,lαtm,rtm denotes the number of visits to page m at timestamp t. ot−1m denotes the previously published data on page m at timestamp t−1. Because the approximation error contains the sensitive data rtm, we should add Laplace noise to it. Since one user can visit at most l pages per timestamp, the sensitivity of the approximation error is l. αtm is the privacy budget for evaluation. ℒ0,l/αtm is called the evaluation noise.The perturbation component adds perturbation noise to datartm. The sanitized output data is given as follows:(8)otm=rtm+ℒ0,lβtm,βtm is the privacy budget for perturbation. Because the perturbation noise is a random variable, we define the perturbation error as the expectation of the absolute error between rtm and otm. The perturbation error is calculated as follows:(9)p_errtm=Ertm−otm=Eℒ0,lβtm=lβtm.The evaluation component compares these two errors and decides whether to publish new data. If the data change dramatically, the approximation error becomes larger than the perturbation error. Then, the perturbation component consumes the perturbation budget and publishes new data. Otherwise, it skips this publication and saves the perturbation budget.Unfortunately, the evaluation noise can easily cause the evaluation component to make the bad decisions. To reduce the evaluation noise, we cluster all pages intoX groups and calculate the mean approximate error in each group instead of the approximate error on each page. The mean approximate error is calculated as follows:(10)a_errtx¯=1sizex∑m∈xrtm−ot−1m+ℒ0,l/sizexαtx,where sizex stands for the number of pages in group x∈1,X. The sensitivity of the mean approximate error is l/sizex, and αtx is the evaluation budget for each group.We can see that the evaluation noise in equation (10) has a smaller variance compared to equation (7). However, the mean approximate error also has a shortcoming that the data change on a single page could be ignored. BD algorithm calculates the mean approximate error on all pages, which ignores many small changes among pages and results in a lower data utility. STBD clusters pages into several groups to strike a balance between reducing evaluation noise and capturing data change. The pseudocode of the evaluation and the perturbation are shown in Lines 2–18, Algorithm 1. The evaluation component first calculates the approximation error (Lines 2–7). Then, it calculates the perturbation error (Lines 8–10). If the perturbation error is less than the approximation error, the perturbation component adds perturbation noise to rτm and publishes it (Lines 11–13). Otherwise, the perturbation component repeats the previously published data oτ−1m and saves the perturbation budget (Lines 14–17).


#### 4.1.2. Budget Allocation in STBD

The budget allocation component distributes half of the privacy budgetε to the evaluation component, and the other half to the perturbation component. The evaluation budget is evenly distributed to w timestamps. Therefore, the evaluation budget αtx=ε/2/w for any timestamp t and any page group x. The perturbation budget for each publication is allocated by an exponential decay method, which allocates half of the remaining budget to each publication. Algorithm 2 presents the pseudocode of budget allocation.Algorithm 2: Budget Allocation in STBD.
Input:β11,…,βτ−1M,ε,w,nOutput:ατx,βτm(1)
for groupx do(2)
ατx=ε/2/w(3)
end for(4)
forn-range window win do(5)
ϕtwin=maxm∈winβtm(6)
ψτwin=ε/2−∑t=τ−w+1τ−1ϕtwin(7)
end for(8)
for nodem do(9)
ητm=minwin∈mψτwin(10)
βτm=ητm/2(11)
end for(12)
returnατx,βτmWe use Figure6 as an example to illustrate Algorithm 2. Windows 1 and 2 are two 2-range spatial windows that cover page 8. Windows 1 and 2 take pages 8 and 1 as the center, respectively. The temporal length of windows 1 and 2 is w. Considering window 1, the perturbation budget consumed at timestamp t is calculated as follows:(11)ϕtwin1=maxm∈win1βtm.Figure 6
Illustration of exponential decay method.The remaining budget of window 1 at timestampτ is(12)ψτwin1=ε2−∑t=τ−w+1τ−1ϕtwin1.Similarly, the remaining budget of window 2 at timestampτ is(13)ψτwin2=ε2−∑t=τ−w+1τ−1ϕtwin2.To ensure that the perturbation budget inside windows 1 and 2 is no more thanε/2, the remaining budget for page 8 at timestamp τ is(14)ητ8=minwin∍8ψτwin.We allocate half of the remaining budget for the perturbation budget, while reserving the other half for future publications. The perturbation budget is described as follows:(15)βτ8=12ητ8.


#### 4.1.3. Privacy Analysis

Theorem 6.
STBD algorithm satisfies thew,n-differential privacy.Proof.
Given a pagem belonging to group x, the evaluation component calculates the mean approximate error on group x and the perturbation error on page m. The perturbation error does not contain sensitive information. The sensitivity of the mean approximate error on group x is l/sizex. Based on Theorem 1, evaluation component adds ℒ0,l/sizex/αtx to the mean approximate error, so it satisfies αtx-differential privacy.
The perturbation component addsℒ0,l/βtm to the data rtm and the sensitivity of rtm is l. According to Theorem 1, the perturbation component satisfies βtm-differential privacy.
The evaluation and perturbation protect the datartm independently. Therefore, rtm is protected under αtx+βtm-differential privacy based on Theorem 2. Budget allocation guarantees that ∑t=τ−w+1τmaxm∈winαtx+βtm≤ε for any n-range window win and any τ, so STBD algorithm satisfies w,n-differential privacy. □


### 4.2. Spatial-Temporal RescueDP

Spatial-Temporal RescueDP (STR) extends the RescueDP [12] to implement w,n-differential privacy. The structure of the STR algorithm is shown in Figure 7. It contains four components: sampling, perturbation, filtering, and budget allocation. The sampling component adaptively selects the timestamps to publish new data according to the data change and the remaining budget. The perturbation component adds Laplace noise to the statistic data at sampling timestamps. The filtering component uses the Kalman Filter [9, 12] to improve data utility. The budget allocation component allocates the privacy budget for each publication. The difference between STR and RescueDP is that STR uses a new budget allocation component to achieve w,n-differential privacy. Algorithm 3 outlines the steps in STR.Algorithm 3: STR algorithm.
Input:rτOutput:oτ(1)
Find the set of sampling pages(2)
Budget Allocation component allocates privacy budget to each page(3)
Perturbation component adds Laplace noise torτm(4)
Filtering component uses Kalman filter to reduce the noise(5)
Sampling component calculates the next sampling intervalFigure 7
The structure of the STR algorithm.


#### 4.2.1. Sampling

The sampling component uses the PID control algorithm [12] to predict the data change. The PID error is defined as follows:(16)Etnm=otnm−otn−1m,δtnm=KpEtnm+Kg∑u=n−π−1nEtumπ+KdEtnmtn−tn−1.The subscripttn indicates the n-th sampling timestamp. Etnm is the feedback error [12], which calculates the absolute error between the published data at the current sampling timestamp and the last sampling timestamp. PID error δtnm contains three parts: (1) KpEtnm is the proportional error standing for the current error; (2) Kg∑u=n−π−1nEtum/π is the integral error standing for the sum of past π feedback errors; (3) KdEtnm/tn−tn−1 is the derivative error standing for the future error.When the data change rapidly, the PID error becomes larger. To reduce approximation error, the sampling interval should become smaller. Meanwhile, if the remaining budget is small, the sampling interval should become larger to reduce the perturbation noise. Therefore, the sampling interval is calculated as follows:(17)Itnm=max1,Itn−1+θ1−δtnm·ηtnm2,Itnm is the sampling interval of page m at timestamp tn. ηtnm is the remaining budget for page m at timestamp tn. The parameter θ controls the changing rate of the sampling interval.


#### 4.2.2. Perturbation and Filtering

The perturbation component adds the Laplace random noise into datartm. The perturbation budget is denoted by εtm. The sanitized output data is calculated as follows:(18)otm=rtm+ℒ0,lεtm.The filtering component uses the Kalman Filter to reduce the perturbation noise. Since it only accesses the sanitized output data, it does not leak sensitive information. More details of Kalman Filter can be found in [9, 12].


#### 4.2.3. Budget Allocation in STR

Budget allocation in STR allocates the perturbation budget based on the sampling interval. If the sampling interval is small, the number of sampling timestamps could be more. Therefore, we should allocate a small portion of the remaining budget to the current timestamp and leave more budget to the future. The pseudocode is shown in Algorithm4. It first calculates the remaining budget for each page (Lines 1–6). Then, it calculates the proportion p of the remaining budget allocated to the perturbation component (Line 7). The pmax and εmax are used to avoid consuming too much budget at a single publication (Lines 7-8).Algorithm 4: Budget allocation in STR.
Input:ε11,…,ετ−1M,ε,w,nOutput:ετm(1)
forn-range window win do(2)
ϕtwin=maxm∈winεtm(3)
ψτwin=ε−∑t=τ−w+1τ−1ϕtwin(4)
end for(5)
for nodem do(6)
ητm=minwin∈mψτwin(7)
pτm=mins·lnIτm+1,pmax(8)
ετm=minpτm·ητm,εmax(9)
end for(10)
returnετm


#### 4.2.4. Privacy Analysis

Theorem 7.
STR algorithm satisfies thew,n-differential privacyProof.
The perturbation component accesses the sensitive datartm, while the other three components do not. The perturbation component adds ℒ0,l/εtm to the data rtm and the sensitivity of rtm is l. According to Theorem 1, the perturbation component satisfies εtm-differential privacy. The budget allocation component guarantees that ∑t=τ−w+1τmaxm∈winεtm<ε for any n-range window win and any τ. Therefore, STR algorithm satisfies w,n-differential privacy. □


## 4.1. Spatial-Temporal Budget Distribution

The structure of the Spatial-Temporal Budget Distribution (STBD) algorithm is shown in Figure5. STBD consists of three components: evaluation, perturbation, and budget allocation. The evaluation component evaluates the data change and decides whether to publish new data at each timestamp. The perturbation component perturbs the data with Laplace noise and publishes the sanitized data. The budget allocation component distributes the privacy budget to each component. Our STBD algorithm is extended from the Budget Distribution (BD) algorithm [11]. STBD uses a new evaluation component to capture the data change on small page groups and uses a new budget allocation component to satisfy w,n-differential privacy. Algorithm 1 shows the pseudocode of the STBD algorithm.Algorithm 1: STBD algorithm.
Input:rτ,oτ−1Output:oτ,βτ1,…,βτM(1)
ατx,βτm← Budget Allocation//Evaluation(2)
for groupx do(3)
a_errτx¯=1/sizex∑m∈xrτm−oτ−1m+ℒ0,l/sizex/ατx(4)
for pagem∈x do(5)
a_errτm=a_errτx¯(6)
end for(7)
end for(8)
for pagem do(9)
p_errτm=l/βτm(10)
end for//Perturbation(11)
for pagem do(12)
ifa_errτm>p_errτm then(13)
oτm=rτm+ℒ0,l/βτm(14)
else(15)
oτm=oτ−1m(16)
βτm=0(17)
end if(18)
end for(19)
returnoτ,βτ1,…,βτMFigure 5
The structure of the STBD algorithm.


### 4.1.1. Evaluation and Perturbation

Publishing data consumes the privacy budget, while the total privacy budget inside the spatial-temporal window is constant. If we publish data on every timestamp, the privacy budget for each publication becomes small, which results in significant perturbation noise. Conversely, if we skip some publications and approximate current data to previously published data, the perturbation noise decreases, while the approximation error increases. The approximation error is calculated as follows:(7)a_errtm=rtm−ot−1m+ℒ0,lαtm,rtm denotes the number of visits to page m at timestamp t. ot−1m denotes the previously published data on page m at timestamp t−1. Because the approximation error contains the sensitive data rtm, we should add Laplace noise to it. Since one user can visit at most l pages per timestamp, the sensitivity of the approximation error is l. αtm is the privacy budget for evaluation. ℒ0,l/αtm is called the evaluation noise.The perturbation component adds perturbation noise to datartm. The sanitized output data is given as follows:(8)otm=rtm+ℒ0,lβtm,βtm is the privacy budget for perturbation. Because the perturbation noise is a random variable, we define the perturbation error as the expectation of the absolute error between rtm and otm. The perturbation error is calculated as follows:(9)p_errtm=Ertm−otm=Eℒ0,lβtm=lβtm.The evaluation component compares these two errors and decides whether to publish new data. If the data change dramatically, the approximation error becomes larger than the perturbation error. Then, the perturbation component consumes the perturbation budget and publishes new data. Otherwise, it skips this publication and saves the perturbation budget.Unfortunately, the evaluation noise can easily cause the evaluation component to make the bad decisions. To reduce the evaluation noise, we cluster all pages intoX groups and calculate the mean approximate error in each group instead of the approximate error on each page. The mean approximate error is calculated as follows:(10)a_errtx¯=1sizex∑m∈xrtm−ot−1m+ℒ0,l/sizexαtx,where sizex stands for the number of pages in group x∈1,X. The sensitivity of the mean approximate error is l/sizex, and αtx is the evaluation budget for each group.We can see that the evaluation noise in equation (10) has a smaller variance compared to equation (7). However, the mean approximate error also has a shortcoming that the data change on a single page could be ignored. BD algorithm calculates the mean approximate error on all pages, which ignores many small changes among pages and results in a lower data utility. STBD clusters pages into several groups to strike a balance between reducing evaluation noise and capturing data change. The pseudocode of the evaluation and the perturbation are shown in Lines 2–18, Algorithm 1. The evaluation component first calculates the approximation error (Lines 2–7). Then, it calculates the perturbation error (Lines 8–10). If the perturbation error is less than the approximation error, the perturbation component adds perturbation noise to rτm and publishes it (Lines 11–13). Otherwise, the perturbation component repeats the previously published data oτ−1m and saves the perturbation budget (Lines 14–17).


### 4.1.2. Budget Allocation in STBD

The budget allocation component distributes half of the privacy budgetε to the evaluation component, and the other half to the perturbation component. The evaluation budget is evenly distributed to w timestamps. Therefore, the evaluation budget αtx=ε/2/w for any timestamp t and any page group x. The perturbation budget for each publication is allocated by an exponential decay method, which allocates half of the remaining budget to each publication. Algorithm 2 presents the pseudocode of budget allocation.Algorithm 2: Budget Allocation in STBD.
Input:β11,…,βτ−1M,ε,w,nOutput:ατx,βτm(1)
for groupx do(2)
ατx=ε/2/w(3)
end for(4)
forn-range window win do(5)
ϕtwin=maxm∈winβtm(6)
ψτwin=ε/2−∑t=τ−w+1τ−1ϕtwin(7)
end for(8)
for nodem do(9)
ητm=minwin∈mψτwin(10)
βτm=ητm/2(11)
end for(12)
returnατx,βτmWe use Figure6 as an example to illustrate Algorithm 2. Windows 1 and 2 are two 2-range spatial windows that cover page 8. Windows 1 and 2 take pages 8 and 1 as the center, respectively. The temporal length of windows 1 and 2 is w. Considering window 1, the perturbation budget consumed at timestamp t is calculated as follows:(11)ϕtwin1=maxm∈win1βtm.Figure 6
Illustration of exponential decay method.The remaining budget of window 1 at timestampτ is(12)ψτwin1=ε2−∑t=τ−w+1τ−1ϕtwin1.Similarly, the remaining budget of window 2 at timestampτ is(13)ψτwin2=ε2−∑t=τ−w+1τ−1ϕtwin2.To ensure that the perturbation budget inside windows 1 and 2 is no more thanε/2, the remaining budget for page 8 at timestamp τ is(14)ητ8=minwin∍8ψτwin.We allocate half of the remaining budget for the perturbation budget, while reserving the other half for future publications. The perturbation budget is described as follows:(15)βτ8=12ητ8.


### 4.1.3. Privacy Analysis

Theorem 6.
STBD algorithm satisfies thew,n-differential privacy.Proof.
Given a pagem belonging to group x, the evaluation component calculates the mean approximate error on group x and the perturbation error on page m. The perturbation error does not contain sensitive information. The sensitivity of the mean approximate error on group x is l/sizex. Based on Theorem 1, evaluation component adds ℒ0,l/sizex/αtx to the mean approximate error, so it satisfies αtx-differential privacy.
The perturbation component addsℒ0,l/βtm to the data rtm and the sensitivity of rtm is l. According to Theorem 1, the perturbation component satisfies βtm-differential privacy.
The evaluation and perturbation protect the datartm independently. Therefore, rtm is protected under αtx+βtm-differential privacy based on Theorem 2. Budget allocation guarantees that ∑t=τ−w+1τmaxm∈winαtx+βtm≤ε for any n-range window win and any τ, so STBD algorithm satisfies w,n-differential privacy. □


## 4.1.1. Evaluation and Perturbation

Publishing data consumes the privacy budget, while the total privacy budget inside the spatial-temporal window is constant. If we publish data on every timestamp, the privacy budget for each publication becomes small, which results in significant perturbation noise. Conversely, if we skip some publications and approximate current data to previously published data, the perturbation noise decreases, while the approximation error increases. The approximation error is calculated as follows:(7)a_errtm=rtm−ot−1m+ℒ0,lαtm,rtm denotes the number of visits to page m at timestamp t. ot−1m denotes the previously published data on page m at timestamp t−1. Because the approximation error contains the sensitive data rtm, we should add Laplace noise to it. Since one user can visit at most l pages per timestamp, the sensitivity of the approximation error is l. αtm is the privacy budget for evaluation. ℒ0,l/αtm is called the evaluation noise.The perturbation component adds perturbation noise to datartm. The sanitized output data is given as follows:(8)otm=rtm+ℒ0,lβtm,βtm is the privacy budget for perturbation. Because the perturbation noise is a random variable, we define the perturbation error as the expectation of the absolute error between rtm and otm. The perturbation error is calculated as follows:(9)p_errtm=Ertm−otm=Eℒ0,lβtm=lβtm.The evaluation component compares these two errors and decides whether to publish new data. If the data change dramatically, the approximation error becomes larger than the perturbation error. Then, the perturbation component consumes the perturbation budget and publishes new data. Otherwise, it skips this publication and saves the perturbation budget.Unfortunately, the evaluation noise can easily cause the evaluation component to make the bad decisions. To reduce the evaluation noise, we cluster all pages intoX groups and calculate the mean approximate error in each group instead of the approximate error on each page. The mean approximate error is calculated as follows:(10)a_errtx¯=1sizex∑m∈xrtm−ot−1m+ℒ0,l/sizexαtx,where sizex stands for the number of pages in group x∈1,X. The sensitivity of the mean approximate error is l/sizex, and αtx is the evaluation budget for each group.We can see that the evaluation noise in equation (10) has a smaller variance compared to equation (7). However, the mean approximate error also has a shortcoming that the data change on a single page could be ignored. BD algorithm calculates the mean approximate error on all pages, which ignores many small changes among pages and results in a lower data utility. STBD clusters pages into several groups to strike a balance between reducing evaluation noise and capturing data change. The pseudocode of the evaluation and the perturbation are shown in Lines 2–18, Algorithm 1. The evaluation component first calculates the approximation error (Lines 2–7). Then, it calculates the perturbation error (Lines 8–10). If the perturbation error is less than the approximation error, the perturbation component adds perturbation noise to rτm and publishes it (Lines 11–13). Otherwise, the perturbation component repeats the previously published data oτ−1m and saves the perturbation budget (Lines 14–17).


## 4.1.2. Budget Allocation in STBD

The budget allocation component distributes half of the privacy budgetε to the evaluation component, and the other half to the perturbation component. The evaluation budget is evenly distributed to w timestamps. Therefore, the evaluation budget αtx=ε/2/w for any timestamp t and any page group x. The perturbation budget for each publication is allocated by an exponential decay method, which allocates half of the remaining budget to each publication. Algorithm 2 presents the pseudocode of budget allocation.Algorithm 2: Budget Allocation in STBD.
Input:β11,…,βτ−1M,ε,w,nOutput:ατx,βτm(1)
for groupx do(2)
ατx=ε/2/w(3)
end for(4)
forn-range window win do(5)
ϕtwin=maxm∈winβtm(6)
ψτwin=ε/2−∑t=τ−w+1τ−1ϕtwin(7)
end for(8)
for nodem do(9)
ητm=minwin∈mψτwin(10)
βτm=ητm/2(11)
end for(12)
returnατx,βτmWe use Figure6 as an example to illustrate Algorithm 2. Windows 1 and 2 are two 2-range spatial windows that cover page 8. Windows 1 and 2 take pages 8 and 1 as the center, respectively. The temporal length of windows 1 and 2 is w. Considering window 1, the perturbation budget consumed at timestamp t is calculated as follows:(11)ϕtwin1=maxm∈win1βtm.Figure 6
Illustration of exponential decay method.The remaining budget of window 1 at timestampτ is(12)ψτwin1=ε2−∑t=τ−w+1τ−1ϕtwin1.Similarly, the remaining budget of window 2 at timestampτ is(13)ψτwin2=ε2−∑t=τ−w+1τ−1ϕtwin2.To ensure that the perturbation budget inside windows 1 and 2 is no more thanε/2, the remaining budget for page 8 at timestamp τ is(14)ητ8=minwin∍8ψτwin.We allocate half of the remaining budget for the perturbation budget, while reserving the other half for future publications. The perturbation budget is described as follows:(15)βτ8=12ητ8.


## 4.1.3. Privacy Analysis

Theorem 6.
STBD algorithm satisfies thew,n-differential privacy.Proof.
Given a pagem belonging to group x, the evaluation component calculates the mean approximate error on group x and the perturbation error on page m. The perturbation error does not contain sensitive information. The sensitivity of the mean approximate error on group x is l/sizex. Based on Theorem 1, evaluation component adds ℒ0,l/sizex/αtx to the mean approximate error, so it satisfies αtx-differential privacy.
The perturbation component addsℒ0,l/βtm to the data rtm and the sensitivity of rtm is l. According to Theorem 1, the perturbation component satisfies βtm-differential privacy.
The evaluation and perturbation protect the datartm independently. Therefore, rtm is protected under αtx+βtm-differential privacy based on Theorem 2. Budget allocation guarantees that ∑t=τ−w+1τmaxm∈winαtx+βtm≤ε for any n-range window win and any τ, so STBD algorithm satisfies w,n-differential privacy. □


## 4.2. Spatial-Temporal RescueDP

Spatial-Temporal RescueDP (STR) extends the RescueDP [12] to implement w,n-differential privacy. The structure of the STR algorithm is shown in Figure 7. It contains four components: sampling, perturbation, filtering, and budget allocation. The sampling component adaptively selects the timestamps to publish new data according to the data change and the remaining budget. The perturbation component adds Laplace noise to the statistic data at sampling timestamps. The filtering component uses the Kalman Filter [9, 12] to improve data utility. The budget allocation component allocates the privacy budget for each publication. The difference between STR and RescueDP is that STR uses a new budget allocation component to achieve w,n-differential privacy. Algorithm 3 outlines the steps in STR.Algorithm 3: STR algorithm.
Input:rτOutput:oτ(1)
Find the set of sampling pages(2)
Budget Allocation component allocates privacy budget to each page(3)
Perturbation component adds Laplace noise torτm(4)
Filtering component uses Kalman filter to reduce the noise(5)
Sampling component calculates the next sampling intervalFigure 7
The structure of the STR algorithm.


### 4.2.1. Sampling

The sampling component uses the PID control algorithm [12] to predict the data change. The PID error is defined as follows:(16)Etnm=otnm−otn−1m,δtnm=KpEtnm+Kg∑u=n−π−1nEtumπ+KdEtnmtn−tn−1.The subscripttn indicates the n-th sampling timestamp. Etnm is the feedback error [12], which calculates the absolute error between the published data at the current sampling timestamp and the last sampling timestamp. PID error δtnm contains three parts: (1) KpEtnm is the proportional error standing for the current error; (2) Kg∑u=n−π−1nEtum/π is the integral error standing for the sum of past π feedback errors; (3) KdEtnm/tn−tn−1 is the derivative error standing for the future error.When the data change rapidly, the PID error becomes larger. To reduce approximation error, the sampling interval should become smaller. Meanwhile, if the remaining budget is small, the sampling interval should become larger to reduce the perturbation noise. Therefore, the sampling interval is calculated as follows:(17)Itnm=max1,Itn−1+θ1−δtnm·ηtnm2,Itnm is the sampling interval of page m at timestamp tn. ηtnm is the remaining budget for page m at timestamp tn. The parameter θ controls the changing rate of the sampling interval.


### 4.2.2. Perturbation and Filtering

The perturbation component adds the Laplace random noise into datartm. The perturbation budget is denoted by εtm. The sanitized output data is calculated as follows:(18)otm=rtm+ℒ0,lεtm.The filtering component uses the Kalman Filter to reduce the perturbation noise. Since it only accesses the sanitized output data, it does not leak sensitive information. More details of Kalman Filter can be found in [9, 12].


### 4.2.3. Budget Allocation in STR

Budget allocation in STR allocates the perturbation budget based on the sampling interval. If the sampling interval is small, the number of sampling timestamps could be more. Therefore, we should allocate a small portion of the remaining budget to the current timestamp and leave more budget to the future. The pseudocode is shown in Algorithm4. It first calculates the remaining budget for each page (Lines 1–6). Then, it calculates the proportion p of the remaining budget allocated to the perturbation component (Line 7). The pmax and εmax are used to avoid consuming too much budget at a single publication (Lines 7-8).Algorithm 4: Budget allocation in STR.
Input:ε11,…,ετ−1M,ε,w,nOutput:ετm(1)
forn-range window win do(2)
ϕtwin=maxm∈winεtm(3)
ψτwin=ε−∑t=τ−w+1τ−1ϕtwin(4)
end for(5)
for nodem do(6)
ητm=minwin∈mψτwin(7)
pτm=mins·lnIτm+1,pmax(8)
ετm=minpτm·ητm,εmax(9)
end for(10)
returnετm


### 4.2.4. Privacy Analysis

Theorem 7.
STR algorithm satisfies thew,n-differential privacyProof.
The perturbation component accesses the sensitive datartm, while the other three components do not. The perturbation component adds ℒ0,l/εtm to the data rtm and the sensitivity of rtm is l. According to Theorem 1, the perturbation component satisfies εtm-differential privacy. The budget allocation component guarantees that ∑t=τ−w+1τmaxm∈winεtm<ε for any n-range window win and any τ. Therefore, STR algorithm satisfies w,n-differential privacy. □


## 4.2.1. Sampling

The sampling component uses the PID control algorithm [12] to predict the data change. The PID error is defined as follows:(16)Etnm=otnm−otn−1m,δtnm=KpEtnm+Kg∑u=n−π−1nEtumπ+KdEtnmtn−tn−1.The subscripttn indicates the n-th sampling timestamp. Etnm is the feedback error [12], which calculates the absolute error between the published data at the current sampling timestamp and the last sampling timestamp. PID error δtnm contains three parts: (1) KpEtnm is the proportional error standing for the current error; (2) Kg∑u=n−π−1nEtum/π is the integral error standing for the sum of past π feedback errors; (3) KdEtnm/tn−tn−1 is the derivative error standing for the future error.When the data change rapidly, the PID error becomes larger. To reduce approximation error, the sampling interval should become smaller. Meanwhile, if the remaining budget is small, the sampling interval should become larger to reduce the perturbation noise. Therefore, the sampling interval is calculated as follows:(17)Itnm=max1,Itn−1+θ1−δtnm·ηtnm2,Itnm is the sampling interval of page m at timestamp tn. ηtnm is the remaining budget for page m at timestamp tn. The parameter θ controls the changing rate of the sampling interval.


## 4.2.2. Perturbation and Filtering

The perturbation component adds the Laplace random noise into datartm. The perturbation budget is denoted by εtm. The sanitized output data is calculated as follows:(18)otm=rtm+ℒ0,lεtm.The filtering component uses the Kalman Filter to reduce the perturbation noise. Since it only accesses the sanitized output data, it does not leak sensitive information. More details of Kalman Filter can be found in [9, 12].


## 4.2.3. Budget Allocation in STR

Budget allocation in STR allocates the perturbation budget based on the sampling interval. If the sampling interval is small, the number of sampling timestamps could be more. Therefore, we should allocate a small portion of the remaining budget to the current timestamp and leave more budget to the future. The pseudocode is shown in Algorithm4. It first calculates the remaining budget for each page (Lines 1–6). Then, it calculates the proportion p of the remaining budget allocated to the perturbation component (Line 7). The pmax and εmax are used to avoid consuming too much budget at a single publication (Lines 7-8).Algorithm 4: Budget allocation in STR.
Input:ε11,…,ετ−1M,ε,w,nOutput:ετm(1)
forn-range window win do(2)
ϕtwin=maxm∈winεtm(3)
ψτwin=ε−∑t=τ−w+1τ−1ϕtwin(4)
end for(5)
for nodem do(6)
ητm=minwin∈mψτwin(7)
pτm=mins·lnIτm+1,pmax(8)
ετm=minpτm·ητm,εmax(9)
end for(10)
returnετm


## 4.2.4. Privacy Analysis

Theorem 7.
STR algorithm satisfies thew,n-differential privacyProof.
The perturbation component accesses the sensitive datartm, while the other three components do not. The perturbation component adds ℒ0,l/εtm to the data rtm and the sensitivity of rtm is l. According to Theorem 1, the perturbation component satisfies εtm-differential privacy. The budget allocation component guarantees that ∑t=τ−w+1τmaxm∈winεtm<ε for any n-range window win and any τ. Therefore, STR algorithm satisfies w,n-differential privacy. □


## 5. Experimental Evaluation

Baseline models. In this section, we compare STBD and STR with two state-of-the-art algorithms, BD [11] and RescueDP [12]. BD is a w,N-differential privacy algorithm, and RescueDP is a w,1-differential privacy algorithm. Since the Uniform algorithm [11], which allocates the same budget to every timestamp, performs much worse than baseline models, we do not include it in the following experiments. All algorithms are written by Python on a computer with Intel Core i7-8700 CPU. We run each experiment 50 times and report the average results.Utility metrics. We use the Mean Absolute Error (MAE) and Mean Relative Error (MRE) as the utility metrics to measure the performance of algorithms.(19)MAERT,OT=1T·M∑t=1T∑m=1Mrtm−otm,MRERT,OT=1T·M∑t=1T∑m=1Mrtm−otmmaxγ,rtm,where RT=r1,r2,…,rT denotes the real number of visits, and OT=o1,o2,…,oT is the sanitized output. γ is used to avoid the special case when rtm is 0. We set γ to 0.1% of ∑m=1Mrtm, which is the same as [12].In the STBD algorithm, we use the Louvain algorithm [42] to cluster pages into 39 groups. To fairly compare with RescueDP, STR uses the same parameters in [12], which are shown in Table 2. We refer readers to [12] for more details. We set l to 20.Table 2
STR parameters.
Kp0.9θ10Kg0.1s0.2Kd0pmax0.6π3εmax0.2εUtility vs.ε. Figure 8 shows the MAE and MRE of four algorithms when ε changes from 0.2 to 1.0 under the condition that w=120 and n=6. Because larger privacy budget results in smaller Laplace random noise, the MAE and MRE of the four algorithms decrease when ε becomes larger. RescueDP and STR outperform BD and STBD. Since BD and STBD only allocate half of the privacy budget for the perturbation component, they get larger perturbation noise. Furthermore, RescueDP and STR use Kalman Filter to reduce the random noise.Figure 8
Utility vs.ε.
(a)(b)Utility vs.w. Figure 9 shows the MAE and MRE of four algorithms when w changes from 40 to 200 under the condition that ε=1 and n=6. The MAE and MRE of BD and STBD increase when w becomes larger. This is because the evaluation budget becomes smaller when w becomes larger, which results in larger evaluation noise and more bad decisions. Although a larger w may result in more publications and less perturbation budget for each publication, STR and RescueDP increase the sampling interval when the remaining budget becomes small. Therefore, the perturbation budget cannot be too small, and the performance of STR and RescueDP is relatively stable when w changes.Figure 9
Utility vs.w.
(a)(b)Utility vs.n. Figure 10 shows the MAE and MRE of four algorithms when n changes from 4 to 9 under the condition that ε=1 and w=120. Because the n-range spatial window constrains the maximum perturbation budget consumed on each page, the performance of STR is worse than RescueDP. We can also observe that the performance of STBD and STR is stable as n increases. The reason is that STBD and STR can prevent performance degradation when n becomes too large. A much larger n brings a stronger budget constraint on the spatial dimension and can lead to greater perturbation noise. However, STBD and STR evaluate the data changes and skip some publications to save the budget for future publications. Thus, the performance degradation is not obvious. On the contrary, if we publish the data at every timestamp, data utility will significantly decrease as n increases.Figure 10
Utility vs.n.
(a)(b)Utility vs. Trajectory privacy guarantee. Comparing four algorithms in Figures8–10, we can observe that BD gets the worst data utility. However, BD protects any spatial-temporal sequence within w successive timestamps, so it provides the strongest trajectory privacy guarantee. RescueDP gets the best data utility, but it cannot protect trajectories that traverse multiple places. STBD allows pages to have different publication decisions and different perturbation noises. Thus, STBD outperforms BD. STR constrains the perturbation budget consumed by the pages in the n-range spatial window. Therefore, the performance of STR is worse than that of RescueDP. STBD and STR protect any spatial-temporal sequence within any spatial-temporal window of size w,n, which can cover most trajectories. Therefore, STBD and STR can achieve a balance between data utility and trajectory privacy guarantee.


## 6. Conclusion

In this paper, we proposew,n-differential privacy to protect trajectory privacy in spatial-temporal streams. This privacy model protects any spatial-temporal sequence occurring in any window of w timestamps and n-range places. We introduce the way of constructing the spatial-temporal window and finding the appropriate window size. To achieve better data utility, two implementation algorithms, STBD and STR, are proposed. Both of these two algorithms adaptively allocate the privacy budget and publish data according to the characteristics of data. Experiments on a real-world dataset show that our proposed algorithms can achieve a balance between data utility and trajectory privacy guarantee.



---

*Source: 9968905-2021-08-05.xml*