# Stateful Switch: Optimized Time Series Release with Local Differential
Privacy

Qingqing Ye †, Haibo Hu †, Kai Huang ‡, Man Ho Au ♯, Qiao Xue †
† The Hong Kong Polytechnic University,
‡ The Hong Kong University of Science and Technology, ♯ The University of Hong
Kong
_{qqing.ye, haibo.hu<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>_

###### Abstract

Time series data have numerous applications in big data analytics. However,
they often cause privacy issues when collected from individuals. To address
this problem, most existing works perturb the values in the time series while
retaining their temporal order, which may lead to significant distortion of
the values. Recently, we propose TLDP model [45] that perturbs temporal
perturbation to ensure privacy guarantee while retaining original values. It
has shown great promise to achieve significantly higher utility than value
perturbation mechanisms in many time series analysis. However, its
practicability is still undermined by two factors, namely, utility cost of
extra missing or empty values, and inflexibility of privacy budget settings.
To address them, in this paper we propose switch as a new two-way operation
for temporal perturbation, as opposed to the one-way dispatch operation in
[45]. The former inherently eliminates the cost of missing, empty or repeated
values. Optimizing switch operation in a stateful manner, we then propose
$StaSwitch$ mechanism for time series release under TLDP. Through both
analytical and empirical studies, we show that $StaSwitch$ has significantly
higher utility for the published time series than any state-of-the-art
temporal- or value-perturbation mechanism, while allowing any combination of
privacy budget settings.

###### Index Terms:

Local differential privacy; time series; temporal perturbation; switch
operation

##  I Introduction

In big data era, continual data, i.e., a sequence of values in the temporal
order (a.k.a., _time series_), has numerous real-world applications [39].
Among them, many time series are collected from individuals, such as
biosensors in telecare, IoT sensors in smart home, and trajectories for
mobility tracking in COVID-19 pandemic. Directly releasing them to the public
can cause privacy infringement [28, 21]. For example, the periodic heart rate
readings from an Apple Watch may reveal the daily activity of its owner, e.g.,
sleeping, sitting, or walking.

To address this issue, many privacy-preserving time series publishing
techniques have been proposed [32, 43], most of which are based on
differential privacy [13], in either a centralized [14, 31] or a local setting
[9, 36, 4, 42]. However, all these works are value perturbation mechanisms,
i.e., they perturb the value at each timestamp so that no value at any
timestamp can be inferred with high confidence. Unfortunately, in medical and
financial applications, such mechanisms do not work because distorted values
are useless or even harmful, for example ECG/blood pressure readings, and
stock trading prices.

Our recent work [45] has proposed to mitigate this issue by perturbing the
temporal order of a time series. The privacy model, namely local differential
privacy in the temporal setting (TLDP), guarantees an adversary cannot infer
the original timestamp of a value with high confidence. As temporal
perturbation does not inject any noise to the value, the accuracy of most time
series statistics (e.g., moving average, range count) and manipulations (e.g.,
window smoothing, resampling) can be significantly enhanced. The following is
a concrete example beyond the medical or financial domain.

Example: Smart Meter. Utility (electricity, gas, and water) companies are
deploying smart meters in households to collect real-time consumption data for
usage prediction and resource scheduling. However, such data may disclose the
activities in an individual household, such as away-from-home (low usage of
all three utilities) and heavy washing (high usage of both electricity and
water in a laundry room). To preserve privacy under differential privacy,
unfortunately we cannot perturb these reading values as they must be
accurately reflected in the utility bills. Therefore, temporal perturbation
(independently on these three time series) becomes the natural way to achieve
deniability and differential privacy.

Although TLDP is a promising privacy model in value-critical applications,
there remain two issues in [45]. First, the proposed Threshold Mechanism (TM)
is built on the operation of dispatch, which randomly moves the value of the
current timestamp to a future timestamp within a sliding window of length $k$.
But since this is a one-way operation (i.e., only from current to future, but
not vice versa), it causes missing, empty or repeated values in a released
time series. Second, TLDP has two privacy parameters, namely, the privacy
budget $\epsilon$ and the sliding window length $k$. However, the Threshold
Mechanism (TM) cannot effectively support all combinations of $\epsilon$ and
$k$. A mismatch of $\epsilon$ and $k$ could either cost TM extra missing or
empty values to satisfy a small $\epsilon$ or a large $k$, or waste the large
$\epsilon$ for a small $k$. The following two examples explain this mismatch
issue of TM.

  * •

Frequency counting, which counts the occurrences of a specific value in a time
series, is sensitive to missing values. Using TM with $\epsilon=1.0$ and
$k=10$ causes very large estimation error, $382$ times higher than Randomized
Response [38], a value-perturbation mechanism on time series.

  * •

When $k=4$, the largest privacy budget TM can support is only $2.19$. In other
words, any $\epsilon$ larger than $2.19$ has to be wasted [45].

In this paper, we present a switch-based mechanism for TLDP that addresses
these two issues. As opposed to the dispatch operation in TM, switch is a two-
way operation in a time series, which exchanges two values $S_{i}$ and $S_{j}$
of timestamps $t_{i}$ and $t_{j}$. In essence, a switch is equivalent to two
synchronous dispatch operations, and it is free of missing, empty or repeated
values. Based on this operation, we propose $StaSwitch$ (short for Stateful
Switch) perturbation mechanism, which bounds each value’s choice of switch by
a stateful probability distribution. Furthermore, this new mechanism does not
cause any mismatch on $\epsilon$ and $k$ as in TM. As such, users have full
flexibility on the choice privacy parameters without degrading data utility.
To summarize, our contributions in this paper are three-fold.

  * •

We propose a two-way atomic operation switch for temporal perturbation, which
inherently eliminates missing, empty or repeated values in the released time
series.

  * •

We design two temporal perturbation mechanisms based on switch operation,
namely the baseline mechanism $RanSwitch$ and an optimized one $StaSwitch$.
They are capable of offering full flexibility for users to set any privacy
parameters without degrading data utility.

  * •

We present detailed analysis on the privacy guarantee and utility cost of
$RanSwitch$ and $StaSwitch$. Through intensive analytical and empirical
studies, we show that $StaSwitch$ has significantly higher utility for the
released time series than any state-of-the-art temporal-perturbation or value-
perturbation mechanism.

The rest of the paper is organized as follows. Section II formulates the
problem of time series release. Section III presents switch operation,
together with our baseline mechanism $RanSwitch$. Section IV introduces
$StaSwitch$ mechanism with theoretical analysis on privacy guarantee and
utility cost. Section V presents experimental results and case studies on both
real and synthetic datasets. Finally, we review existing work in Section VI
and conclude this paper in Section VII.

##  II Problem Definition and Preliminaries

###  II-A Problem Definition

In this paper, we define a time series as an infinite sequence of values
$S=\\{S_{1},S_{2},...,S_{n},...\\}$ in a discrete temporal domain
$T=\\{t_{1},t_{2},...,t_{n},...\\}$. Our task is to release a sanitized time
series $R=\\{R_{1},R_{2},...,R_{n},...\\}$ out of the original one $S$ under
local differential privacy, and as with [45], our goal is to minimize the
collective cost arising from each value’s missing, repetition, empty and
misaligned between $R$ and $S$. Specifically, a missing cost, whose unit is
$M$, occurs when a value in $S$ is missed in $R$; a repetition cost, whose
unit is $N$, occurs when a value is duplicated once in $S$; an empty cost,
whose unit is $E$, occurs when a timestamp in $R$ has not been filled with any
value, causing a default; and finally a misalignment cost 111The delay cost in
[45] is a special case of misalignment cost. The latter also considers the
cost when a value is released in advance of the original timestamp. occurs
when a value is released at an earlier or delayed timestamp, and one timestamp
of misalignment bears a unit cost of $D$.

###  II-B Existing Value-Perturbation LDP Mechanisms for Time Series

A number of solutions have been proposed for time series release under LDP.
Depending on the privacy requirements, canonical definitions of neighboring
time series include user-level [31], event-level [14], and w-event [24]
privacy. Given a definition of neighboring time series as above, a formal
definition of $(\epsilon,\delta)$-LDP on time series is as below.

###### Definition II.1

($\bm{(\epsilon,\delta)}$-LDP) Given privacy parameters $\epsilon$ and
$\delta$, a randomized algorithm $\mathcal{A}$ satisfies
$(\epsilon,\delta)$-LDP, iff for any two neighboring time series $S$ and
$S^{\prime}$, and any possible output $R$ of $\mathcal{A}$, the following
inequality holds:

$\mathrm{Pr}(\mathcal{A}(S)=R)\leq
e^{\epsilon}\cdot\mathrm{Pr}(\mathcal{A}(S^{\prime})=R)+\delta$ (1)

Since $(\epsilon,\delta)$-LDP is defined on difference in values, all existing
works [17, 9, 36, 4] adopt value-perturbation mechanisms, such as Laplace
mechanism [13], Gaussian mechanism [15], and Randomized Response [38], to
inject noise to released value or statistics of the time series.

###  II-C Local Differential Privacy in Temporal Setting

As opposed to the above value-perturbation LDP model, we follow the temporal-
perturbation LDP model (TLDP) as in [45]. In TLDP, two (temporally)
neighboring time series are defined as those can be turned into one another by
exchanging the values of two timestamps.

###### Definition II.2

(Neighboring Time Series) Two time series $S$ and $S^{\prime}$ are neighbors
if there exist two timestamps $t_{i}\neq t_{j}$ such that

1) $|i-j|<k$, and

2) $S_{i}=S^{\prime}_{j}$ and $S_{j}=S^{\prime}_{i}$, and

3) for any other timestamp $t_{l}(l\neq i,j)$, $S_{l}=S^{\prime}_{l}$.

In the above definition, $k$ is the length of a time sliding window, which is
an additional privacy parameter. The larger the $k$, the longer period the
value remains sensitive to the user. For example, by setting $k$ to $24$
hours, a smart watch user can be assured that a released heart rate reading
can be from anytime of that day; but if $k$ is set to $1$ hour, this period of
“deniability” is shortened to $1$ hour and might not be sufficient to preserve
the user’s privacy. Based on Definition II.2, local differential privacy in
the temporal setting, a.k.a. $(\epsilon,\delta)$-TLDP, is defined as follows.

###### Definition II.3

($\bm{(\epsilon,\delta)}$-TLDP) Given privacy parameters $\epsilon$ and
$\delta$, a randomized algorithm $\mathcal{A}$ satisfies
$(\epsilon,\delta)$-TLDP, iff for any two neighboring (in a window of length
$k$) time series $S$ and $S^{\prime}$, and any possible output $R$ of
$\mathcal{A}$, the following inequality holds:

$\mathrm{Pr}(\mathcal{A}(S)=R)\leq
e^{\epsilon}\cdot\mathrm{Pr}(\mathcal{A}(S^{\prime})=R)+\delta$ (2)

The degree of privacy in TLDP is controlled by $\epsilon$, $\delta$, and $k$.

##  III Switch Operation and RanSwitch Mechanism

In this section, we first define the switch operation for temporal
perturbation, based on which we present a baseline mechanism $RanSwitch$ to
satisfy $(\epsilon,\delta)$-TLDP, together with its perturbation protocol, and
privacy and utility analysis.

###  III-A Switch Operation

To perturb a time series temporally, an intuitive operation is to
probabilistically assign a temporal position for the incoming value at each
timestamp. This is the rationale of the dispatch operation in [45]. However,
since the dispatch position is independently selected at each timestamp,
dispatch conflicts may occur. We argue that the root cause lies in the one-way
nature of dispatch operation. For example, at timestamp $t_{i}$, dispatching
its value $S_{i}$ to timestamp $t_{j}$ only decides the destination of $S_{i}$
is $t_{j}$, but it is uncertain which value $S_{x}$ should fill in $t_{i}$. In
other words, the timestamp $t_{i}$’s “from” and “to” dispatches (i.e.,
$S_{x}\Rightarrow t_{i}$, and $S_{i}\Rightarrow t_{j}$) always happen
asynchronously and independently, which leads to missing, empty and repeated
values.222According to [45], if the “from” dispatch fails with conflict, then
$t_{i}$ has to report an empty value; if the “to” dispatch fails, then the
value $S_{i}$ will be missed; if two or more values happen to be dispatched to
the same timestamp, or if a value is repeatedly dispatched to more than one
timestamp, some values will be overwritten and thus missed. To address this
issue, in this paper we propose switch as a two-way atomic operation for
temporal perturbation, which is formally defined below.

###### Definition III.1

(Switch Operation) Given a sliding window of length $k$, a switch operation
$S_{i}\Leftrightarrow S_{j}$ exchanges two values $S_{i}$ and $S_{j}$ with
each other in $R$, that is, $R_{j}=S_{i}$ and $R_{i}=S_{j}$, where $0\leq
i-j<k$.

In essence, a switch operation $S_{i}\Leftrightarrow S_{j}$ is equivalent to
two simultaneous and correlated dispatch operations $S_{i}\Rightarrow t_{j}$
(i.e., “to” dispatch at $t_{i}$) and $S_{j}\Rightarrow t_{i}$ (i.e., “from”
dispatch at $t_{i}$) in [45]. Therefore, it inherently eliminates missing,
empty or repeated values. In the sequel, to avoid confusion with “dispatch”,
we use term “allocate” for the one-way perturbation in a switch operation,
i.e., $S_{i}$ is allocated to $t_{j}$ and $S_{j}$ is allocated to $t_{i}$.

Another advantage of the switch operation is its inherit resemblance to
neighboring time series in Definition II.2. Recall that two temporally
neighboring time series are those which can be turned into one another by
exchanging the values of two timestamps. Therefore, to satisfy
$(\epsilon,\delta)$-TLDP becomes intuitive — at each timestamp we just
randomly switch the current value with another one within the sliding window
of length $k$. This idea leads to our baseline perturbation mechanism
$RanSwitch$ for TLDP. In what follows, we will first present the perturbation
protocol of $RanSwitch$ in Sec. III-B, and then analyze its privacy guarantee
in Sec. III-D and utility cost in Sec. III-E.

###  III-B RanSwitch: A Baseline Mechanism

For a time series $S=\\{S_{1},S_{2},...,S_{n},...\\}$, at each timestamp
$t_{i}$, $RanSwitch$ randomly selects a timestamp $t_{j}$ in the sliding
window $\\{t_{i},t_{i+1},...,t_{i+k-1}\\}$ according to the following
perturbation probability distribution:

$\displaystyle\mathrm{Pr}[j=i+l]=\begin{cases}p,\quad\text{if}\quad l=0\\\
q,\quad\text{if}\quad l\in\\{1,2,...,k-1\\}\end{cases}$ (3)

and then applies the switch operation to values $S_{i}$ and $S_{j}$. Here $p$
denotes the probability of selecting the current timestamp (i.e., retaining
$S_{i}$), while $q$ is the probability of selecting one of the other $k-1$
timestamps, and $p+(k-1)q=1$. The pseudo-code of $RanSwitch$ mechanism is
shown in Algorithm 1. $S_{i}$ may be finally allocated to one of the $k-1$
backward timestamps $\\{t_{i-k+1},t_{i-k+2},...,t_{i-1}\\}$, the current
timestamp $t_{i}$, or one of the forward timestamps
$\\{t_{i+1},t_{i+2},...\\}$.

Algorithm 1 Perturbation protocol of $RanSwitch$

Input: |  Original time series $S=\\{S_{1},S_{2},...,S_{n},...\\}$
---|---
|  Sliding window length $k$
|  Perturbation probabilities $p$ and $q$
Output: |  Released time series $R=\\{R_{1},R_{2},...,R_{n},...\\}$

1: Initialize the released time series $R=\emptyset$

2: for each timestamp $t_{i}$ ($i\in\\{1,2,...,n,...\\}$) do

3: Randomly select an index $j$ from $\mathbb{X}=\\{l|i\leq l\leq i+k-1\\}$
according to Eq. 3

4: Switch $S_{i}$ and $S_{j}$

5: Set $R_{i}=S_{i}$ and release $R_{i}$

(a) Switch operation (b) Probability distribution

Figure 1: Dispatching probability of $RanSwitch$ mechanism

We show an example of $k=3$ in Fig. 1(a). Since there are $3$ timestamps,
$RanSwitch$ performs $3$ switch operations
\footnotesize1⃝\footnotesize2⃝\footnotesize3⃝, one at each timestamp. At
timestamp $t_{1}$, suppose $S_{1}$ switches with $S_{3}$, then $S_{3}$ is
allocated backward to $t_{1}$ and released. At timestamp $t_{2}$, suppose
$t_{2}$ itself is selected, then $S_{2}$ is released at the current
timestamp.At timestamp $t_{3}$, suppose $t_{3}$ itself is selected, then the
original $S_{1}$ (denoted by $S_{3}$ now) is allocated to its forward
timestamp $t_{3}$ and then released.

Since $RanSwitch$ (or any TLDP perturbation mechanism) probabilistically
allocates $S_{i}$ to timestamps $t_{i-k+1}$, …, $t_{i}$, …, $t_{i+k-1},...$
with probabilities irrespective of $i$, we can use
$\\{\mathcal{P}_{1-k},...,\mathcal{P}_{-1},\mathcal{P}_{0},\mathcal{P}_{1},...,\mathcal{P}_{k-1},...,\mathcal{P}_{n}\\}$
to denote these probabilities, where the subscripts are the temporal deviation
of the allocated timestamp from the original timestamp. Fig. 1(b) illustrates
the allocating probabilities of $S_{3}$ to timestamps
$\\{t_{1},t_{2},t_{3},t_{4},t_{5}\\}$. Note that $n\geq k-1$ and can be as
large as infinity, since a value can be repeatedly allocated to its forward
timestamps (although with rapidly decreasing probabilities).333As will be
elaborated in Theorem III.3, privacy analysis only needs the first $2k-1$
allocating probabilities, i.e.,
$\\{\mathcal{P}_{1-k},...,\mathcal{P}_{-1},\mathcal{P}_{0},\mathcal{P}_{1},...,\mathcal{P}_{k-1}\\}$,
which spans across two adjacent sliding windows. In this paper, we
collectively call these probabilities the allocating probability distribution
of $RanSwitch$, the derivation of which lays the foundation of privacy and
utility analysis.

###  III-C Allocating Probability Distribution in $RanSwitch$

We now derive the allocating probability distribution of $RanSwitch$. For each
value $S_{i}$, $RanSwitch$ can allocate it backward, stationarily, or forward.
As such, we derive the three probabilities separately.

  * •

Backward probability
$\\{\mathcal{P}_{1-k},\mathcal{P}_{2-k},...,\mathcal{P}_{-1}\\}$, when $S_{i}$
is dispatched to a previous timestamp within a sliding window. To start with,
$\mathcal{P}_{1-k}$ denotes the probability when $S_{i-k+1}$ switches with
$S_{i}$ so that $S_{i}$ is released at timestamp $t_{i-k+1}$. Hence
$\mathcal{P}_{1-k}=q$. The next probability $\mathcal{P}_{2-k}$ is when
$S_{i}$ is released at $t_{i-k+2}$, which occurs when $S_{i}$ has not been
released at $t_{i-k+1}$ and is then selected at timestamp $t_{i-k+2}$. Hence
$\mathcal{P}_{2-k}=q(1-q)$. Similarly, we can derive other backward
probabilities as $\mathcal{P}_{j}=q(1-q)^{k-1+j},$ where
$j\in\\{1-k,2-k,...,-1\\}$.

  * •

Current probability $\mathcal{P}_{0}$, when the value $S_{i}$ stays at the
current timestamp. This occurs only when $S_{i}$ has not been released until
$t_{i}$ (w.p. $(1-q)^{k-1}$) and is then released at $t_{i}$ (w.p. $p$). As
such, $\mathcal{P}_{0}=p(1-q)^{k-1}.$

  * •

Forward probability
$\\{\mathcal{P}_{1},\mathcal{P}_{2},...,\mathcal{P}_{k-1}\\}$, when the value
$S_{i}$ is released after $t_{i}$ within a sliding window. Similar to the
derivation of backward probability, for any $j\in\\{1,2,...,k-1\\}$, we have
$\mathcal{P}_{j}=q(1-q)^{k-1+j}.$

Combining the above three cases, we reach the following Theorem III.2 on
allocating probability distribution in $RanSwitch$ for all the $2k-1$
timestamps.

###### Theorem III.2

For $1-k\leq j\leq k-1$, the allocating probability distribution of
$RanSwitch$ mechanism is

$\displaystyle\mathcal{P}_{j}=\begin{cases}p(1-q)^{k-1},&\text{if}\ j=0\\\
q(1-q)^{k-1+j},&\text{otherwise}\end{cases}$ (4)

###  III-D Privacy Analysis of RanSwitch

Based on Theorem III.2, the following theorem proves that $RanSwitch$
satisfies $(\epsilon,\delta)$-TLDP.

###### Theorem III.3

Given a sliding window of length $k$ and the probabilities $p$ and $q$, the
mechanism $RanSwitch$ satisfies $(\epsilon,\delta)$-TLDP, where
$\epsilon=\ln\frac{p^{2}(1-q)^{2(k-1)}-q}{q^{2}(1-q)^{2(k-1)}}$ and
$\delta=q$.

  * Proof.

For any two neighboring time series
$S=\\{S_{1},S_{2},...,S_{i},...,S_{j},...\\}$ and
$S^{\prime}=\\{S_{1},S_{2},...,S_{i}^{\prime},...,S_{j}^{\prime},...\\}$, let
$t_{i}$ and $t_{j}$ denote the two timestamps when $S$ and $S^{\prime}$
differ, and $|i-j|<k$. As each value may be allocated to a forward/backward
timestamp within a sliding window or any forward timestamp beyond this window,
the difference of output time series occurs when the value $S_{i}$ in $S$ is
allocated to a forward timestamp which $S_{i}^{\prime}$ in $S^{\prime}$ cannot
reach. Thus,

$\displaystyle\delta=\max\\{\mathcal{P}_{1-k},\mathcal{P}_{2-k},...,\mathcal{P}_{-2},\mathcal{P}_{-1}\\}=q$

To derive $\epsilon$, for any output time series $R$, $\epsilon$ must satisfy

$\displaystyle\epsilon=\mathop{\sup}_{S,S^{\prime},R}\ln\frac{\mathrm{Pr}[\mathcal{A}(S)=R]-\delta}{\mathrm{Pr}[\mathcal{A}(S^{\prime})=R]}$

For any output $R$ by $RanSwitch$, suppose $S_{i}$ (or $S^{\prime}_{j}$) is
allocated to timestamp $t_{\alpha}$, and $S_{j}$ (or $S^{\prime}_{i}$) is
allocated to timestamp $t_{\beta}$. Then,
$\frac{\mathrm{Pr}[\mathcal{A}(S)=R]-\delta}{\mathrm{Pr}[\mathcal{A}(S^{\prime})=R]}=\frac{\mathcal{P}_{\alpha-i}\cdot\mathcal{P}_{\beta-j}-\delta}{\mathcal{P}_{\alpha-j}\cdot\mathcal{P}_{\beta-i}}$.

According to Eq. 4, except for the case of $j=0$, the allocating probability
decreases as $j$ increases. So $\mathcal{P}_{1-k}>\mathcal{P}_{k-1}$.
Depending on whether they are larger or smaller than $P_{0}$, we derive
$\epsilon$ separately:

    * –

When $q\leq p(1-q)^{k-1}$,
$\mathcal{P}_{k-1}<\mathcal{P}_{1-k}<\mathcal{P}_{0}$ holds. So

$\displaystyle\epsilon=\ln\frac{\mathcal{P}_{0}^{2}-\delta}{\mathcal{P}_{\alpha-\beta}\cdot\mathcal{P}_{\beta-\alpha}}=\frac{p^{2}(1-q)^{2(k-1)}-q}{q^{2}(1-q)^{2(k-1)}}$
(5)

    * –

When $q>p(1-q)^{k-1}$, $\mathcal{P}_{1-k}>\mathcal{P}_{0}$ holds. Since $p>q$,
$p(1-q)^{k-1}>q(1-q)^{2(k-1)}$ always holds. Therefore,
$\mathcal{P}_{k-1}<\mathcal{P}_{0}<\mathcal{P}_{1-k}$. So

$\displaystyle\epsilon=\max\\{\ln\frac{\mathcal{P}_{0}\cdot\mathcal{P}_{\beta-j}-\delta}{\mathcal{P}_{i-j}\cdot\mathcal{P}_{\beta-i}},\ln\frac{\mathcal{P}_{0}^{2}-\delta}{\mathcal{P}_{\alpha-\beta}\cdot\mathcal{P}_{\beta-\alpha}}\\}$
(6)

As both
$\frac{\mathcal{P}_{0}\cdot\mathcal{P}_{\beta-j}-\delta}{\mathcal{P}_{i-j}\cdot\mathcal{P}_{\beta-i}}=\frac{p(1-q)^{2(k-1)+\beta-j}-1}{q(1-q)^{2(k-1)+\beta-j}}<0$
and
$\frac{\mathcal{P}_{0}^{2}-\delta}{\mathcal{P}_{\alpha-\beta}\cdot\mathcal{P}_{\beta-\alpha}}<\frac{p^{2}(1-q)^{k-1}-p}{q^{2}(1-q)^{k-1}}<0$
always hold when $q>p(1-q)^{k-1}$, any privacy budget $\epsilon>0$ is
sufficient to satisfy Eq. 6.

Therefore, Eq. 5 becomes the only requirement of setting privacy budget, i.e.,
$\epsilon=\ln\frac{p^{2}(1-q)^{2(k-1)}-q}{q^{2}(1-q)^{2(k-1)}}$.

###  III-E Utility Analysis of RanSwitch

In Sec. II-A, there are four costs that collectively determine the utility of
a temporal perturbation approach. Fortunately, $RanSwitch$ mechanism only
involves misalignment cost, as there are no missing, empty or repeated values.
As such, the expectation of the total cost $\mathbb{E}[C]$ is

$\displaystyle\begin{split}\quad\mathbb{E}[C]=-D\sum\nolimits_{j=1-k}^{-1}j\mathcal{P}_{j}+D\sum\nolimits_{j=1}^{\infty}j\mathcal{P}_{j}\end{split}$
(7)

Note the second term means the count of (forward) misaligned timestamps $j$
spans from $1$ to $\infty$. As the first two sliding window (i.e., $1-k\leq
j\leq k-1$) dominates the total cost, we can derive a lower bound of it as

$\displaystyle\begin{split}\mathbb{E}[C]&<\sum\nolimits_{j=1-k}^{-1}(-j)\cdot
P_{j}+\sum\nolimits_{j=1}^{k-1}j\cdot P_{j}\\\
&=\left(k\gamma-\frac{\gamma^{2}}{q}+(k-1)(\gamma-\gamma^{2})\right)D\end{split}$
(8)

where $\gamma=1-(1-q)^{k}$.

From Eq. 8, the lower bound of the total cost is approximately proportional to
$k$. As such, if $k$ is large enough, $\mathbb{E}[C]$ becomes very close to
$kD$, which means the asymptotic utility of $RanSwitch$ could be poor with
respect to large $k$. To illustrate this, in Fig. 2 we plot its allocating
probability distribution in green line for $k=10$ and the privacy budget
$\epsilon=2$. We observe that the dispatching probabilities beyond the sliding
window, i.e., $\mathcal{P}_{10}$, … $\mathcal{P}_{19}$, …, are non-negligible.
They form a long tail and dominate $\mathbb{E}[C]$, which is around $4.54$
444We set the maximum misaligned timestamps to $2k$ in Fig. 2 according to Eq.
7. Furthermore, for those $\mathcal{P}_{j}$ within the sliding window, the
probabilities significantly decrease as $j$ increases, which pushes up the
upper bound of the ratio of any two allocating probabilities and thus incurs
heavy perturbation to guarantee privacy.

As a comparison, we also plot the allocating probability distribution of the
ideal mechanism in blue line, which splits the probabilities equally among all
timestamps except $\mathcal{P}_{0}$, i.e.,
$\mathcal{P}_{-9}=\mathcal{P}_{-8}=...=\mathcal{P}_{-1}=P_{1}=...=\mathcal{P}_{8}=\mathcal{P}_{9}=(1-\mathcal{P}_{0})/18$.
As such, $\mathbb{E}[C]$ is only around $3.82$ according to Eq. 8. Although
this ideal mechanism cannot be designed in practice, because the perturbation
probability distribution is accumulated throughout an infinite time series, it
inspires us to design a close-to-ideal perturbation mechanism in the next
section, namely $StaSwitch$, with a more balanced allocating probability
distribution than $RanSwitch$.

Figure 2: Allocating probability distribution ($k=10$ and $\epsilon=2$)

##  IV StaSwitch: A Mechanism with Stateful Switch

The root cause of $RanSwitch$’s high misalignment cost lies in the repeated
deferment of a value through multiple switch operations. For example, a value
at timestamp $t_{i}$ is first forward switched to $t_{i+j}$, and then switched
to $t_{i+j+l}$, so on and so forth. To reduce this cost, in this section we
propose $StaSwitch$ which keeps track of the switch state of each value and
guarantees its final allocated timestamp is still within the initial sliding
window. That is, if a value has never been delayed, its allocating space can
be the whole sliding window; otherwise, for a value that has already been
delayed for $l(l<k)$ timestamps, its new allocation space is limited to the
first $k-l$ timestamps of the sliding window.

In what follows, we will first present the perturbation protocol of
$StaSwitch$ in Sec. IV-A, and then derive its allocating probability
distribution in Sec. IV-B, followed by privacy analysis in Sec. IV-C and
utility analysis in Sec. IV-D.

###  IV-A Perturbation Protocol of StaSwitch

Given a sliding window of length $k$, for each value $S_{i}$, $StaSwitch$
mechanism allows at most $k-1$ timestamps delay. To guarantee this, at
timestamp $t_{i}$, $StaSwitch$ randomly selects a timestamp $t_{j}$ in the
sliding window $\\{t_{i},t_{i+1},...,t_{i+k-1}\\}$ according to the
perturbation probability distribution in Eq. 9, and then switches $S_{i}$ and
$S_{j}$.

$\displaystyle\mathrm{Pr}[t_{j}]=\begin{cases}p+bq,\quad&\text{if}\quad j=0\\\
q,\quad&\text{if}\quad j\in\\{1,2,...,k-1-b\\}\\\
0,\quad&\text{otherwise}\end{cases}$ (9)

Note that $b$ denotes the timestamps $S_{i}$ has been delayed. If the value
$S_{i}$ has never been delayed, then $b=0$ and Eq. 9 degrades to Eq. 3 of
$RanSwitch$ mechanism. Otherwise, $S_{i}$ cannot be allocated to the last $b$
timestamps $\\{t_{k-b},...,t_{k-1}\\}$ in the sliding window of $t_{i}$. And
their perturbation probabilities, which is $bq$, are reclaimed by $StaSwitch$
and allocated to $t_{i}$. As such, $StaSwitch$ guarantees each value can be
delayed up to $k-1$ timestamps. $StaSwitch$ gets its name from stateful
switch, as the perturbation probability distribution depends on the current
state of delayed timestamps $b$. Table I shows an example under different
delayed timestamps $b$ when $k=4$, where each cell shows the perturbation
probability of $S_{i}$ being allocated to $t_{i+j}$.

TABLE I: Perturbation probability distribution when $k=4$ | $j=0$ | $j=1$ | $j=2$ | $j=3$
---|---|---|---|---
$b=0$ | $p$ | $q$ | $q$ | $q$
$b=1$ | $p+q$ | $q$ | $q$ | $0$
$b=2$ | $p+2q$ | $q$ | $0$ | $0$
$b=3$ | $p+3q$ | $0$ | $0$ | $0$
Algorithm 2 Perturbation protocol of $StaSwitch$

Input: |  Original time series $S=\\{S_{1},S_{2},...,S_{n},...\\}$
---|---
|  Sliding window length $k$
|  Perturbation probabilities $p$ and $q$
Output: |  Released time series $R=\\{R_{1},R_{2},...,R_{n},...\\}$

1: Initialize a released time series $R=\emptyset$

2: Initialize a vector of delayed timestamps $b=\\{0\\}^{|S|}$

3: for each timestamp $t_{i}$ ($i\in\\{1,2,...,n,...\\}$) do

4: Randomly select an index $j$ from $\mathbb{X}=\\{l|i\leq l\leq
i+k-1-b_{i}\\}$ according to Eq. 9

5: Switch $S_{i}$ and $S_{j}$

6: $b_{j}=b_{j}+j-i$

7: $R_{i}=S_{i}$ and release $R_{i}$

Algorithm 2 shows the pseudo-code of $StaSwitch$ mechanism. The procedure is
similar to Algorithm 1, except for vector $b$, which record the current
delayed timestamps of each value. At each timestamp $t_{i}$, an index $j$ is
randomly drawn from Eq. 9 (Line 4), and then the current value $S_{i}$ and the
selected one $S_{j}$ are switched (Line 5). As such, $S_{i}$ is delayed by
$j-i$ timestamps, so $b_{j}$, the delayed timestamps of $S_{j}$, is
incremented by $j-i$ (Line 6). Finally, the current value $S_{i}$ (i.e., the
original $S_{j}$) is released (Line 7).

###  IV-B Allocating Probability Distribution in $StaSwitch$

We now derive the allocating probability distribution
$\mathcal{P}=\\{\mathcal{P}_{1-k},...,\mathcal{P}_{-1},\mathcal{P}_{0},\mathcal{P}_{1},...,\mathcal{P}_{k-1}\\}$
of $StaSwitch$ for privacy and utility analysis. To start with, we first
derive the expected perturbation probability distribution over all $b$’s from
Eq. 9 as below.

$\displaystyle\mathbb{E}[\mathrm{Pr}[t_{j}]]\\!=\\!\begin{cases}p_{0}=\\!\sum_{i=0}^{k-1}P_{b}^{i}(p\\!+\\!iq),&\text{if}\
j=0\\\ q_{j}=\\!\sum_{i=0}^{k\\!-\\!j\\!-\\!1}P_{b}^{i}q,&\text{if}\ 1\leq
j\leq k\\!-\\!1\end{cases}$ (10)

where $P_{b}^{i}=\mathrm{Pr}[b=i]$. Note that, at timestamp $t_{i+j}$,
$P_{b}^{i}$ is the probability that the current value comes from $S_{j}$
(i.e., with $i$ timestamps delay) before switching value $S_{i+j}$. Since
there are $i$ such cases, we sum them up as below.

$\displaystyle P_{b}^{i}$
$\displaystyle=q\sum\nolimits_{j=0}^{i-1}P_{b}^{j}\cdot\prod\nolimits_{l=1}^{i-1-j}(1-q_{l}),$
(11)

where $P_{b}^{0}=\prod_{j=1}^{k-1}(1-q_{j})$ denotes the probability that the
current value has never been delayed.

By substituting Eq. 11 for $P_{b}^{i}$ in Eq. 10, we obtain the expected
perturbation probability distribution over $p_{0}$ and all $q_{j}$. Then we
derive the allocating probability distribution as follows. First, we know
$\mathcal{P}_{1-k}$ means $S_{i-k+1}$ selects timestamp $t_{i}$, so $S_{i}$ is
released at $t_{i-k+1}$. Hence $\mathcal{P}_{1-k}=q_{k-1}$. Similarly, we can
derive other allocating probabilities as follows. For any $1\leq j\leq k-1$,

$\displaystyle\mathcal{P}_{j-k}=q_{k-j}\prod\nolimits_{i=1}^{j-1}(1-q_{k-i})$
$\displaystyle\mathcal{P}_{0}=p\prod\nolimits_{j=1}^{k-1}(1-q_{k-j})$ (12)
$\displaystyle\mathcal{P}_{j}=q\\!\sum_{l=0}^{j-1}\\!P_{b}^{l}\\!\left(\\!(p\\!+\\!jq)\prod_{i=1}^{j\\!-\\!l\\!-\\!1}(1\\!-\\!q_{i})\\!+\\!\sum_{i=1}^{k\\!-\\!j\\!-\\!1}\\!q_{i}\\!\prod_{r=1}^{j\\!-\\!l\\!-\\!1}\\!(1\\!-\\!q_{r+i})\\!\right)$

To interpret the last equation, $\mathcal{P}_{j}$, the allocating probability
of a value being deviated by $j$ timestamps, is comprised of $j$ joint
probabilities, each first allocating a value with $l$ ($0\leq l\leq j-1$)
timestamps deviation (i.e., $P_{b}^{l}$ ) and then allocating the same value
with another $j-l$ timestamps deviation. The latter probability is further
comprised of two terms. The first term, $(p+jq)\prod_{i=1}^{j-l-1}(1-q_{i})$,
denotes the probability that a value with $l$ timestamps deviation is directly
switched to timestamp $t_{j}$, and the second term,
$\sum_{i=1}^{k-j-1}q_{i}\prod_{r=1}^{j-l-1}(1-q_{r+i})$, is the probability
that the value first selects a timestamp after $t_{j}$ and then switches it
with value $S_{j}$.

###  IV-C Privacy Analysis

This subsection establishes the privacy guarantee of $StaSwitch$ mechanism.
Lemmas IV.1 and IV.2 first show the monotonicity of the probability
distribution $P_{b}^{i}(1\leq i\leq k-1)$ and the allocating probability
distribution $\mathcal{P}_{i}(1-k\leq i\leq k-1)$ respectively, based on which
we prove $StaSwitch$ satisfies ($\epsilon$, $\delta$)-TLDP in Theorem IV.3.

###### Lemma IV.1

For $j\in\\{1,2,...,k-1\\}$, the probability $P_{b}^{j}$ monotonously
increases with $j$, i.e., $P_{b}^{1}<P_{b}^{2}<...<P_{b}^{k-1}$.

###### Lemma IV.2

The minimum of $StaSwitch$’s allocating probabilities
$\\{\mathcal{P}_{1-k},...,\mathcal{P}_{-1},\mathcal{P}_{0},\mathcal{P}_{1},...,\mathcal{P}_{k-1}\\}$
is
$\mathcal{P}_{min}=\min\\{\mathcal{P}_{1-k},\mathcal{P}_{-1},\mathcal{P}_{1}\\}$.

###### Theorem IV.3

The $StaSwitch$ satisfies ($\epsilon$, $\delta$)-TLDP, where
$\epsilon=\ln\frac{\frac{p^{2}}{\sigma}-(p^{2}-p+2)}{q\left(1+q-\frac{k(1-p)q}{2(1+q)}-\frac{q}{2-p}\right)}$,
$\delta=\max\\{\mathcal{P}_{1-k},\mathcal{P}_{2-k},...,\mathcal{P}_{-1}\\}$,
$\sigma=\frac{(1-p)(1+p+q)(2-p)-q}{2(k-2)(1+q)(2-p)}+\frac{(k-3)q^{2}(1-q)^{k-1}}{2}$,
and $p$ and $q$ are parameters defined in Eq. 9.

  * Proof.

Let $t_{i}$ and $t_{j}$ denote the two timestamps that neighboring time series
$S$ and $S^{\prime}$ differ. That is, $S_{i}$ = $S^{\prime}_{j}$, and $S_{j}$
= $S^{\prime}_{i}$. In the output $R$, let $t_{\alpha}$ and $t_{\beta}$ denote
the timestamps to which the values of $S_{i}$ and $S_{j}$ are allocated,
respectively. Therefore,

$\displaystyle\begin{split}\epsilon\\!&=\\!\mathop{\sup}_{S,S^{\prime},R}\\!\ln\\!\frac{\mathrm{Pr}[\mathcal{A}(S)\\!=\\!R]\\!-\\!\delta}{\mathrm{Pr}[\mathcal{A}(S^{\prime})\\!=\\!R]}=\mathop{\sup}_{\alpha,\beta,i,j}\\!\ln\\!\frac{\mathcal{P}_{\alpha-i}\mathcal{P}_{\beta-j}\\!-\\!\delta}{\mathcal{P}_{\alpha-j}\mathcal{P}_{\beta-i}}\end{split}$
(13)

According to Lemma IV.2, the minimum allocating probability is
$\mathcal{P}_{min}=\min\\{\mathcal{P}_{1-k},\mathcal{P}_{-1},\mathcal{P}_{1}\\}$,
where $\mathcal{P}_{1-k}=q_{k-1}$,
$\mathcal{P}_{-1}=q_{1}\prod_{j=2}^{k-1}(1-q_{j})$, and
$\mathcal{P}_{1}=\prod_{j=1}^{k-1}(1-q_{j})q(p+q+1-p_{0}-q_{k-1})$.

Therefore, Eq. 13 is reduced to

$\displaystyle\begin{split}\epsilon&=\ln\frac{\mathcal{P}_{0}^{2}-\delta}{\mathcal{P}_{1}\cdot\mathcal{P}_{-1}}\leq\ln\left(\frac{\mathcal{P}_{0}^{2}}{\mathcal{P}_{1}\cdot\mathcal{P}_{-1}}-\frac{1}{\mathcal{P}_{1}}\right)\\\
&<\ln\frac{p^{2}-q_{1}(p^{2}-p+2)}{qq_{1}(p+q+1-p_{0}-\frac{q}{2-p})}\end{split}$
(14)

From the above inequality, to derive an upper bound of $\epsilon$, we need to
have an upper bound of $p_{0}$ and a lower bound of $q_{1}$ respectively.
First we know that

$\displaystyle P_{b}^{k\\!-\\!1}$
$\displaystyle=q\sum\nolimits_{i=0}^{k-2}P_{b}^{i}\prod\nolimits_{l=1}^{k\\!-\\!2\\!-\\!i}(1\\!-\\!q_{l})<q\\!\sum_{i=0}^{k-2}P_{b}^{i}=q\\!-\\!qP_{b}^{k\\!-\\!1}$

Therefore, $P_{b}^{k-1}<\frac{q}{1+q}$, and hence,

$\displaystyle p_{0}$
$\displaystyle=\sum\nolimits_{i=0}^{k-1}P_{b}^{i}\cdot(p+iq)=p+q\sum\nolimits_{i=1}^{k-1}P_{b}^{i}\cdot
i$ $\displaystyle<p+qP_{b}^{k-1}\frac{k(k-1)}{2}<p+\frac{k(1-p)q}{2(1+q)}$

Then we derive a lower bound of $q_{1}$. For any $j\in\\{1,2,...,k-2\\}$,
according to Eq. 10 and Lemma IV.1,

$\displaystyle q_{j}-q_{j+1}$
$\displaystyle=\sum\nolimits_{i=0}^{k\\!-\\!j\\!-\\!1}P_{b}^{i}q-\sum\nolimits_{i=0}^{k\\!-\\!j\\!-\\!2}P_{b}^{i}q=qP_{b}^{k\\!-\\!j\\!-\\!1}>qP_{b}^{1}$

Thus,
$q_{1}-(k\\!-\\!2)qP_{b}^{1}>q_{2}-(k\\!-\\!3)qP_{b}^{1}>\cdots>q_{k-2}-qP_{b}^{1}=q_{k-1}$.
The first term $q_{1}-(k\\!-\\!2)P_{b}^{1}$ must be greater than the average
of the first $k-2$ terms, i.e.,

$\displaystyle q_{1}-(k-2)qP_{b}^{1}$
$\displaystyle>\frac{\sum_{i=1}^{k-2}q_{i}-qP_{b}^{1}\sum_{i=1}^{k-2}i}{k-2}$
$\displaystyle=\frac{1-p_{0}-q_{k-1}}{k-2}-\frac{k-1}{2}qP_{b}^{1}$

Therefore,

$\displaystyle q_{1}$
$\displaystyle>\frac{1-p_{0}-q_{k-1}}{k-2}-\frac{k-1}{2}qP_{b}^{1}+(k-2)qP_{b}^{1}$
$\displaystyle>\frac{(1\\!-\\!p)(1\\!+\\!p\\!+\\!q)(2\\!-\\!p)\\!-\\!q}{2(k-2)(1+q)(2-p)}+\frac{(k\\!-\\!3)q^{2}(1\\!-\\!q)^{k-1}}{2}=\sigma$

Then following Eq. 14, the upper bound of $\epsilon$ becomes
$\ln\frac{\frac{p^{2}}{\sigma}-(p^{2}-p+2)}{q\left(1+q-\frac{k(1-p)q}{2(1+q)}-\frac{q}{2-p}\right)}$.
The proof for $\delta$ follows that of Theorem III.3, where $\delta$ must
cover the difference between the output space of any two neighboring time
series $S$ and $S^{\prime}$, that is,
$\delta=\max\\{\mathcal{P}_{1-k},\mathcal{P}_{2-k},...,\mathcal{P}_{-2},\mathcal{P}_{-1}\\}$.

Theorem IV.3 provides a close-form of $\epsilon$, but not $\delta$. The
following corollary gives a good estimation on it.

###### Corollary IV.4

The maximum of the first $k-1$ allocating probabilities can be approximated by
$\mathcal{P}_{max}$, where
$max=\lceil\frac{\sqrt{q^{2}-4p+8}-2}{2q}\rceil-(k+1)$.

  * Proof.

According to Eq. 11, $P_{b}^{1}=\prod_{j=1}^{k-1}(1-p_{j})q=qP_{b}^{0}$. For
$j\in\\{2,3,...,k-1\\}$, by approximating $P_{b}^{j}$ by $P_{b}^{1}$ , i.e.,
$P_{b}^{j}\approx P_{b}^{1}$, we have $\sum_{j=0}^{k-1}P_{b}^{i}\approx
P_{b}^{0}+(k-1)qP_{b}^{0}=(2-p)P_{b}^{0}$.

By solving $(2-p)P_{b}^{0}\approx 1$, we know for $j\in\\{1,...,k-1\\}$,

$\displaystyle P_{b}^{0}\approx\frac{1}{2-p},\ P_{b}^{j}\approx\frac{q}{2-p}$
(15)

By substituting Eq. 15 in Eq. 10, we have

$\displaystyle q_{j}\approx\frac{q+(k-j-1)q^{2}}{2-p}$ (16)

Then according to Eq. IV-B,

$\displaystyle\mathcal{P}_{j-k}\\!-\\!\mathcal{P}_{j-k-1}\\!=\\!0$
$\displaystyle\Leftrightarrow q_{k-j}-q_{k-j+1}-q_{k-j}\cdot
q_{k-j+1}\\!=\\!0$
$\displaystyle\Leftrightarrow\frac{(1+(j-1)q)(1+(j-2)q)}{2-p}=1$
$\displaystyle\Leftrightarrow j=\frac{\sqrt{q^{2}-4p+8}+3q-2}{2q}$

Therefore, the maximum probability is $\mathcal{P}_{max}$, where $max=\lceil
j-0.5\rceil-k=\lceil\frac{\sqrt{q^{2}-4p+8}-2}{2q}\rceil-(k+1)$.

###  IV-D Utility Analysis

The only cost of $StaSwitch$ is misalignment cost. So the expectation of the
total cost is

$\displaystyle\quad\mathbb{E}[C]=D\left(\sum\nolimits_{j=1}^{k-1}(-j)\mathcal{P}_{j-k}+\sum\nolimits_{j=1}^{k-1}j\mathcal{P}_{j}\right)$
(17)

To derive $\mathbb{E}[C]$, we substitute Eqs. 15 and 16 in Eq. IV-B, then

$\displaystyle\mathcal{P}_{j-k}\approx\frac{q+(j-1)q^{2}}{2-p}\prod\nolimits_{i=1}^{j-1}(1-\frac{q+(i-1)q^{2}}{2-p})$
$\displaystyle\mathcal{P}_{0}\approx
p\prod\nolimits_{j=1}^{k-1}(1-\frac{q+(j-1)q^{2}}{2-p})$ (18)
$\displaystyle\mathcal{P}_{j}\approx\frac{q\left(\Phi(j,0)+\Psi(j,0)\right)}{2-p}+\frac{q^{2}\sum_{l=1}^{j-1}\left(\Phi(j,l)+\Psi(j,l)\right)}{2-p},$

where

$\displaystyle\Phi(j,l)=(p+jq)\prod\nolimits_{i=1}^{j-l-1}(1-\frac{q+(k-i-1)q^{2}}{2-p})$
$\displaystyle\Psi(j,l)=\sum_{i=1}^{k\\!-\\!j\\!-\\!1}\frac{q\\!+\\!(k\\!-\\!i\\!-\\!1)q^{2}}{2-p}\prod_{r=1}^{j\\!-\\!l\\!-\\!1}(1\\!-\\!\frac{q+(k\\!-\\!r\\!-\\!i\\!-\\!1)q^{2}}{2-p})$

By substituting Eq. IV-D in Eq. 17, we obtain an approximation of the expected
total cost $\mathbb{E}[C]$ of $StaSwitch$ mechanism. For example, we can
obtain $\mathbb{E}[C]=3.89$ in Fig. 2. Compared with $\mathbb{E}[C]=3.82$ for
the ideal mechanism, $StaSwitch$ achieves very similar utility.

##  V Experimental Evaluation

In this section, we evaluate and compare $RanSwtich$ and $StaSwitch$ with
state-of-the-art TLDP mechanism, namely (Extended) Threshold mechanism
(TM/ETM) [45], and value-perturbation mechanisms for time series such as
Randomized Response [38] and Piecewise mechanism [33].

###  V-A Experimental Setting

Datasets. We conduct experiments on two real and one synthetic time series
datasets.

  * •

US stock [2] consists of historical daily prices of 14,058 trading days. We
first extract all daily close price as a numerical time series Stock-N, and
then derive another binary time series Stock-B by comparing each close price
with its previous day, so each value indicates “up” or “down” of daily stock
price.

  * •

Trajectory [1] consists of 6,307 taxi trajectories, each of which has GPS
coordinates in a 15-second interval and has at least 300 timestamps.

  * •

SyntheticTS is a generated synthetic time series that consists of $10^{6}$
timestamps, whose values are integers randomly drawn from $[0,100]$.

Experiment Design. We design two sets of experiments. The first set evaluates
the overall cost of the three TLDP mechanisms under various datasets and
parameters, including the sliding window length $k$ and privacy budget
$\epsilon$. The second set compares their utility in three real-world
applications of popular time series manipulation, namely, simple moving
average, frequency counting, and trajectory clustering.

We implement all mechanisms in Java and conduct experiments on a desktop
computer with Intel Core i9-9900K 3.60 GHz CPU, 64G RAM running Windows 10
operating system.

(a) Total cost of $k=10$

(b) Total cost of $k=20$

(c) Total cost of $k=40$

(d) Total cost of $k=80$

Figure 3: Overall comparison of total cost of different TLDP mechanisms on
SyntheticTS

###  V-B Overall Cost Evaluation

This subsection evaluates the total cost of three TLDP mechanisms, i.e.,
$RanSwitch$, $StaSwitch$ and TM/ETM. According to Sec. II-A, the total cost is

$C=D\sum\nolimits_{i}l_{i}+M\cdot n_{1}+N\cdot n_{2}+E\cdot n_{3},$

where $l_{i}$ denotes each value $S_{i}$’s count of timestamps deviated after
perturbation, and $n_{1}$, $n_{2}$ and $n_{3}$ are the numbers of missing,
empty and repeated values, respectively. In the experiment, we set the unit
cost of misalignment $D=1$, and set unit cost of missing, repetition and empty
$M=N=E=k$, which means these costs are as worse as allocating a value to the
endpoint of the sliding window.

Fig. 3 plots the total cost of three mechanisms on the dataset SyntheticTS, by
varying the length of sliding window from $10$ to $80$, and the privacy budget
from $1$ to $8$.555The privacy parameter $\delta$ can be derived by Theorems
III.3 (for $RanSwitch$) and IV.3 (for $StaSwitch$) according to $\epsilon$ and
$k$, so it is not shown in the figure. Overall, $StaSwitch$ performs the best
and consistently outperforms $RanSwitch$ in all cases, thanks to its stateful
switch operation. The gain of $StaSwitch$ becomes more eminent with the
increasing $k$, and exceeds $20\%$ when $k=80$. We observe that TM/ETM incurs
higher cost than both $RanSwitch$ and $StaSwitch$ in most cases, especially
for small privacy budgets. The reason is that TM/ETM has to introduce missing
and empty values to fully satisfy the privacy guarantee. On the other hand, as
we show the results in Table II, when the privacy budget becomes even larger
(e.g., $\epsilon>8$), TM/ETM cannot further benefit from it. This is because
the utility gain of TM/ETM is capped at the upper limit of the threshold
$k-1$, and is consistent with our analysis in Sec. I, which motivates this
work.

TABLE II: Total Cost of Larger Privacy Budgets ($k=10$) $\epsilon$ | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14
---|---|---|---|---|---|---|---|---
TM/ETM | 2.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00
RanSwitch | 1.96 | 1.34 | 0.89 | 0.56 | 0.35 | 0.22 | 0.13 | 0.08
StaSwitch | 1.77 | 1.24 | 0.83 | 0.54 | 0.34 | 0.21 | 0.12 | 0.08

###  V-C Utility Evaluation in Real Applications

To compare the effectiveness of our proposed mechanisms $RanSwitch$ and
$StaSwitch$ against TM/ETM, we measure their utilities in three real-world
time series applications — simple moving average, frequency counting, and
trajectory clustering. We also compare them with value perturbation mechanisms
in each application. For frequency counting, as each value is binary, we use
Randomized Response (RR) [38] which achieves the best performance for binary
data [35]. For simple moving average and trajectory clustering, we use
Piecewise mechanism (PM) [33], the state-of-the-art LDP solution for numerical
value perturbation.

####  V-C1 Simple Moving Average

We conduct simple moving average of the stock’s daily close price on Stock-N
and calculate the mean square error (MSE) of the estimated results as
$\frac{1}{|S|-r+1}\sqrt{\sum\nolimits_{i=1}^{|S|-r+1}(m_{i}-m_{i}^{\prime})^{2}},$
where $m_{i}=\frac{1}{r}\sum_{j=i}^{i+r-1}S_{j}$ and
$m_{i}^{\prime}=\frac{1}{r}\sum_{j=i}^{i+r-1}R_{j}$ are the moving averages
from the original time series $S$ and the released one $R$, with averaging
range $r$.

(a) $k=10$, $r=10$

(d) $k=10$, $r=40$

(a) $k=40$, $r=10$

(d) $k=40$, $r=40$

Figure 4: Results of simple moving average on Stock-N

Fig. 4 plots the results, where the privacy budget $\epsilon$ varies from $1$
to $8$, and the length of sliding window $k$ and the averaging range $r$ are
set to $10$ or $40$, respectively. To best accommodate all the results, we re-
scale the y-axis in Fig. 4. Under different $k$ and $r$, PM always has the
highest MSE, 1-3 orders of magnitude higher than that of TM/ETM and 3-5 orders
of magnitude higher than that of $RanSwitch$ and $StaSwitch$. This
demonstrates the superiority of temporal perturbation over value perturbation
for simple moving average. Both $RanSwitch$ and $StaSwitch$ outperform TM/ETM,
and the gain is more eminent when privacy budget is small. This is because
TM/ETM suffers from missing and empty values when the given privacy budget is
relatively small, while $RanSwitch$ and $StaSwitch$ are free of missing or
empty values thanks to the two-way nature of switch operation. Between
$RanSwitch$ and $StaSwitch$, $StaSwitch$ consistently outperforms $RanSwitch$
in all cases and the average gain exceeds $20\%$, as the stateful switch
operation adopted by $StaSwitch$ further reduces the misalignment cost in the
released time series. In addition, when the averaging range $r$ increases from
$10$ to $40$, the accuracy of all four mechanisms is improved. For PM, it is
because more injected noise is canceled with each other according to law of
large numbers; for TLDP mechanisms, it is because temporal perturbation is
almost constrained within a sliding window of length $k$, but this
disadvantage is mitigated when the averaging range becomes larger, e.g.,
$k=10$ and $r=40$.

(a) $k=10$

(b) $k=20$

(c) $k=40$

(d) $k=80$

Figure 5: Results of frequency counting on Stock-B

####  V-C2 Frequency Counting

To compare the accuracy of counting the frequency of value “up” on the dataset
Stock-B, we adopt RR, TM/ETM, $RanSwitch$ and $StaSwitch$ respectively to
perturb the time series, and measure their deviation from the ground-truth
count by calculating the MSE as
$\frac{1}{|S|}\sqrt{\sum\nolimits_{i=1}^{|S|}(c_{i}-c_{i}^{\prime})^{2}},$
where $c_{i}=\sum_{j=1}^{i}\mathbbm{1}(S_{j}=up)$ and
$c_{i}^{\prime}=\sum_{j=1}^{i}\mathbbm{1}(R_{j}=up)$ are the “up” counts at
timestamp $t_{i}$ in $S$ and $R$, respectively.

Fig. 5 plots the MSE of these mechanisms, where the time window length $k$
varies from $10$ to $80$ and the privacy budget $\epsilon$ varies from $1$ to
$8$. Overall, $StaSwitch$ performs the best among the four mechanisms,
followed by $RanSwitch$, and their gap becomes more eminent as the window
length $k$ gets larger (e.g., $RanSwitch$ reduces $25\%$ of MSE when $k=80$).
On the other hand, TM/ETM no longer outperforms RR (a value perturbation
method) for small privacy budget (e.g., $\epsilon\leq 3$) or large sliding
window (e.g., $k=80$). This is because frequency counting is very sensitive to
missing values, as a missing of “up” decreases all subsequent counts by $1$.

####  V-C3 Trajectory Clustering

Same as [45], we adopt a classic clustering algorithm, namely the $k$-medoids
algorithm [29], to cluster all 6,307 trajectories in the dataset Trajectory
into $6$ groups. The clustering result over the original dataset is regarded
as the ground truth. Then we perturb all trajectories by three TLDP mechanisms
(i.e., $RanSwitch$, $StaSwitch$ and TM/ETM, $k=10$) and one value perturbation
mechanism, namely PM, and apply the same clustering again. To measure the
similarity between the ground-truth clusters and those from perturbed
trajectories, we adopt a classic metric, Normalized Mutual Information (NMI)
[40], whose range is $[0,1]$ and a larger NMI means more similarity. Table III
shows the results of four mechanisms with privacy budget from 1 to 8. We
observe that PM has much smaller NMI than those TLDP mechanisms, because value
perturbation heavily damages the utility of the released trajectories. On the
other hand, $StaSwitch$ always achieves the highest NMI, followed by
$RanSwitch$, which indicates they have more similar clustering results to the
ground truth than TM/ETM.

TABLE III: NMI on Trajectory Clustering $\bm{\epsilon}$ |  $1$ |  $2$ |  $3$ |  $4$ |  $5$ |  $6$ |  $7$ |  $8$
---|---|---|---|---|---|---|---|---
PM |  $0.003$ |  $0.005$ |  $0.006$ |  $0.007$ |  $0.008$ |  $0.008$ |  $0.007$ |  $0.008$
TM/ETM |  $0.572$ |  $0.590$ |  $0.610$ |  $0.616$ |  $0.699$ |  $0.705$ |  $0.706$ |  $0.768$
RanSwitch |  $0.593$ |  $0.613$ |  $0.609$ |  $0.623$ |  $0.703$ |  $0.713$ |  $0.726$ |  $0.845$
StaSwitch |  $0.624$ |  $0.650$ |  $0.703$ |  $0.725$ |  $0.756$ |  $0.745$ |  $0.858$ |  $0.928$

##  VI Related Work

In this section, we review existing works on differential privacy, with a
focus on time series release.

Differential Privacy. Differential privacy was first proposed in the
centralized setting [13]. To avoid relying on a trusted data collector, local
differential privacy (LDP) was proposed to let each user perturb her data
locally [12, 25]. In the literature, many LDP techniques have been proposed
for various statistical collection tasks, such as frequency of categorical
data [17, 23, 5, 35], and mean of numerical data [9, 33, 26]. Recently, the
research focus in LDP has been shifted to more complex tasks, such as itemset
mining [37], marginal release [8, 48], graph data mining [30, 44], key-value
data analysis [46, 20, 47], high-dimensional data analysis [10, 11], and
learning problems [49, 27].

Centralized DP for Time Series. Existing works on centralized DP for time
series focus on differentially private aggregate statistics, e.g., frequency
estimation. Depending on the privacy requirement, a perturbation mechanism can
satisfy _event-level_ privacy [14, 7], _user-level_ privacy [31, 3], or _w-
event_ privacy [24, 34]. There are also several strategies proposed to reduce
the overall variance in the released statistics, such as Fourier
transformation [31], sampling [18], clustering [3], and smoothing techniques
[7, 19]. Another line of works also consider temporal correlation of
continuously released time series data [41, 6].

LDP for Time Series. More recently, there are a number of studies on the
problem of continual time series analysis under LDP. A technique based on
_memoization_ was first proposed in the local setting [17, 9]. Besides that,
Joseph _et al._ [22] design an approach to track changing statistics by
assuming that user data are sampled from several evolving distributions.
Erlingsson _et al._[16] further investigate a shuffle model for collecting
correlated time series data. Wang _et al._ [36] develop a framework for
estimating the sum of real values over a time interval, and Bao _et al._ [4]
propose correlated Gaussian mechanism to reduce the noise injected to time
series. Xue _et al._ [42] investigate continuous frequency estimation in the
user population by exploring an optimal privacy budget allocation scheme to
improve estimation accuracy.

The above works are all based on _value perturbation_. The most relevant work
to this paper is [45], which is the first work on TLDP privacy model and
adopts _temporal perturbation_ to satisfy TLDP. However, this mechanism
suffers from missing, repetition and empty cost, as well as limitations on
settings of privacy parameters $\epsilon$ and $k$. These issues have been
addressed in this paper.

##  VII Conclusion

This paper studies the problem of time series release following TLDP privacy
model. We first define switch as a two-way atomic operation for the time
series perturbation, which inherently eliminates missing, empty or repeated
values. Then we propose a baseline mechanism $RanSwitch$ and an optimized
mechanism $StaSwitch$, the latter of which adopts stateful switch to bound
each value’s timestamp deviation, and thus enhances the utility significantly.
We compare $RanSwitch$ and $StaSwitch$ with the existing temporal-perturbation
and value-perturbation mechanisms through extensive analytical and empirical
analysis under various privacy budgets and time window sizes, and show that
the optimized mechanism $StaSwitch$ always achieves the best performance in
various tasks.

As for future work, we plan to extend this work to more complicated time
series analysis tasks, such as temporally correlated time series release, time
series forecasting, pattern recognition and curve fitting.

## Acknowledgment

This work was supported by the National Natural Science Foundation of China
(Grant No: 62102334, 62072390, 92270123 and 61972332), and the Research Grants
Council, Hong Kong SAR, China (Grant No: 15222118, 15218919, 15203120,
15226221, 15225921, 15209922 and C2004-21GF).

## References

  * [1] Taxi trajectory.  https://www.kaggle.com/crailtap/taxi-trajectory.
  * [2] Us stock.  https://www.kaggle.com/borismarjanovic/price-volume-data-for-all-us-stocks-etfs.
  * [3] G. Acs and C. Castelluccia.  A case study: Privacy preserving release of spatio-temporal density in paris.  In SIGKDD, pages 1679–1688, 2014.
  * [4] E. Bao, Y. Yang, X. Xiao, and B. Ding.  CGM: an enhanced mechanism for streaming data collection with local differential privacy.  PVLDB, 14(11):2258–2270, 2021.
  * [5] R. Bassily and A. Smith.  Local, private, efficient protocols for succinct histograms.  In ACM symposium on Theory of computing, pages 127–135. ACM, 2015\.
  * [6] Y. Cao, M. Yoshikawa, Y. Xiao, and L. Xiong.  Quantifying differential privacy in continuous data release under temporal correlations.  IEEE Transactions on Knowledge and Data Engineering, 31(7):1281–1295, 2019.
  * [7] Y. Chen, A. Machanavajjhala, M. Hay, and G. Miklau.  PeGaSus: Data-adaptive differentially private stream processing.  In ACM SIGSAC Conference on Computer and Communications Security, pages 1375–1388. ACM, 2017.
  * [8] G. Cormode, T. Kulkarni, and D. Srivastava.  Marginal release under local differential privacy.  In SIGMOD, pages 131–146. ACM, 2018.
  * [9] B. Ding, J. Kulkarni, and S. Yekhanin.  Collecting telemetry data privately.  In NIPS, pages 3574–3583, 2017.
  * [10] R. Du, Q. Ye, Y. Fu, and H. Hu.  Collecting high-dimensional and correlation-constrained data with local differential privacy.  In International Conference on Sensing, Communication and Networking, pages 1–9, 2021.
  * [11] J. Duan, Q. Ye, and H. Hu.  Utility analysis and enhancement of ldp mechanisms in high-dimensional space.  In International Conference on Data Engineering, pages 407–419. IEEE, 2022.
  * [12] J. C. Duchi, M. I. Jordan, and M. J. Wainwright.  Local privacy and statistical minimax rates.  In FOCS, pages 429–438. IEEE, 2013.
  * [13] C. Dwork, F. McSherry, K. Nissim, and A. Smith.  Calibrating noise to sensitivity in private data analysis.  In TCC, pages 265–284, 2006.
  * [14] C. Dwork, M. Naor, T. Pitassi, and G. N. Rothblum.  Differential privacy under continual observation.  In ACM symposium on Theory of computing, pages 715–724. ACM, 2010\.
  * [15] C. Dwork, A. Roth, et al.  The algorithmic foundations of differential privacy.  Foundations and Trends in Theoretical Computer Science, 9(3–4):211–407, 2014.
  * [16] Ú. Erlingsson, V. Feldman, I. Mironov, A. Raghunathan, K. Talwar, and A. Thakurta.  Amplification by shuffling: From local to central differential privacy via anonymity.  In Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2468–2479. SIAM, 2019.
  * [17] Ú. Erlingsson, V. Pihur, and A. Korolova.  RAPPOR: Randomized aggregatable privacy-preserving ordinal response.  In ACM SIGSAC Conference on Computer and Communications Security, pages 1054–1067. ACM, 2014.
  * [18] L. Fan and L. Xiong.  An adaptive approach to real-time aggregate monitoring with differential privacy.  IEEE Transactions on Knowledge and Data Engineering, 26(9):2094–2106, 2013.
  * [19] S. Ghayyur, Y. Chen, R. Yus, A. Machanavajjhala, M. Hay, G. Miklau, and S. Mehrotra.  IoT-Detective: Analyzing iot data under differential privacy.  In SIGMOD, pages 1725–1728, 2018.
  * [20] X. Gu, M. Li, Y. Cheng, L. Xiong, and Y. Cao.  PCKV: Locally differentially private correlated key-value data collection with optimized utility.  In USENIX Security Symposium, pages 967–984, 2020.
  * [21] K. Huang, H. Hu, S. Zhou, J. Guan, Q. Ye, and X. Zhou.  Privacy and efficiency guaranteed social subgraph matching.  The VLDB Journal, 31(3):581–602, 2022.
  * [22] M. Joseph, A. Roth, J. Ullman, and B. Waggoner.  Local differential privacy for evolving data.  In NIPS, page 2381–2390, 2018.
  * [23] P. Kairouz, S. Oh, and P. Viswanath.  Extremal mechanisms for local differential privacy.  In NIPS, pages 2879–2887, 2014.
  * [24] G. Kellaris, S. Papadopoulos, X. Xiao, and D. Papadias.  Differentially private event sequences over infinite streams.  PVLDB, 7(12):1155–1166, 2014.
  * [25] N. Li and Q. Ye.  Mobile data collection and analysis with local differential privacy.  In IEEE International Conference on Mobile Data Management, pages 4–7. IEEE, 2019.
  * [26] Z. Li, T. Wang, M. Lopuhaä-Zwakenberg, N. Li, and B. Škoric.  Estimating numerical distributions under local differential privacy.  In SIGMOD, pages 621–635, 2020.
  * [27] W. Lin, B. Li, and C. Wang.  Towards private learning on decentralized graphs with local differential privacy.  IEEE Transactions on Information Forensics and Security, pages 2936–2946, 2022.
  * [28] S. Papadimitriou, F. Li, G. Kollios, and P. S. Yu.  Time series compressibility and privacy.  In VLDB, pages 459–470, 2007.
  * [29] H.-S. Park and C.-H. Jun.  A simple and fast algorithm for k-medoids clustering.  Expert Systems with Applications, 36(2):3336–3341, 2009.
  * [30] Z. Qin, T. Yu, Y. Yang, I. Khalil, X. Xiao, and K. Ren.  Generating synthetic decentralized social graphs with local differential privacy.  In ACM SIGSAC Conference on Computer and Communications Security, pages 425–438. ACM, 2017.
  * [31] V. Rastogi and S. Nath.  Differentially private aggregation of distributed time-series with transformation and encryption.  In SIGMOD, pages 735–746. ACM, 2010.
  * [32] E. Shi, H. Chan, E. Rieffel, R. Chow, and D. Song.  Privacy-preserving aggregation of time-series data.  In NDSS, 2011.
  * [33] N. Wang, X. Xiao, Y. Yang, J. Zhao, S. C. Hui, H. Shin, J. Shin, and G. Yu.  Collecting and analyzing multidimensional data with local differential privacy.  In International Conference on Data Engineering. IEEE, 2019.
  * [34] Q. Wang, Y. Zhang, X. Lu, Z. Wang, Z. Qin, and K. Ren.  Real-time and spatio-temporal crowd-sourced social network data publishing with differential privacy.  IEEE Transactions on Dependable and Secure Computing, 15(4):591–606, 2016.
  * [35] T. Wang, J. Blocki, N. Li, and S. Jha.  Locally differentially private protocols for frequency estimation.  In USENIX Security Symposium, pages 729–745, 2017.
  * [36] T. Wang, J. Q. Chen, Z. Zhang, D. Su, Y. Cheng, Z. Li, N. Li, and S. Jha.  Continuous release of data streams under both centralized and local differential privacy.  In ACM SIGSAC Conference on Computer and Communications Security, pages 1237–1253, 2021.
  * [37] T. Wang, N. Li, and S. Jha.  Locally differentially private frequent itemset mining.  In Symposium on Security and Privacy, pages 127–143, 2018.
  * [38] S. L. Warner.  Randomized response: A survey technique for eliminating evasive answer bias.  Journal of the American Statistical Association, 60(309):63–69, 1965.
  * [39] W. W. Wei.  Time series analysis.  In The Oxford Handbook of Quantitative Methods in Psychology: Vol. 2. 2006.
  * [40] I. H. Witten, E. Frank, M. A. Hall, and C. J. Pal.  Data Mining: Practical machine learning tools and techniques.  Morgan Kaufmann, 2016.
  * [41] Y. Xiao and L. Xiong.  Protecting locations with differential privacy under temporal correlations.  In ACM SIGSAC Conference on Computer and Communications Security, pages 1298–1309, 2015.
  * [42] Q. Xue, Q. Ye, H. Hu, Y. Zhu, and J. Wang.  Ddrm: A continual frequency estimation mechanism with local differential privacy.  IEEE Transactions on Knowledge and Data Engineering, 2022.
  * [43] Y. Yang, M. Shao, S. Zhu, and G. Cao.  Towards statistically strong source anonymity for sensor networks.  ACM Transactions on Sensor Networks, 9(3):34, 2013.
  * [44] Q. Ye, H. Hu, M. H. Au, X. Meng, and X. Xiao.  Towards locally differentially private generic graph metric estimation.  In International Conference on Data Engineering, pages 1922–1925. IEEE, 2020.
  * [45] Q. Ye, H. Hu, N. Li, X. Meng, H. Zheng, and H. Yan.  Beyond value perturbation: Local differential privacy in the temporal setting.  In EEE International Conference on Computer Communications, pages 1–10. IEEE, 2021.
  * [46] Q. Ye, H. Hu, X. Meng, and H. Zheng.  PrivKV: Key-value data collection with local differential privacy.  In Symposium on Security and Privacy, pages 294–308. IEEE, 2019\.
  * [47] Q. Ye, H. Hu, X. Meng, H. Zheng, K. Huang, C. Fang, and J. Shi.  PrivKVM*: Revisiting key-value statistics estimation with local differential privacy.  IEEE Transactions on Dependable and Secure Computing, 2021.
  * [48] Z. Zhang, T. Wang, N. Li, S. He, and J. Chen.  CALM: Consistent adaptive local marginal for marginal release under local differential privacy.  In ACM SIGSAC Conference on Computer and Communications Security, pages 212–229, 2018.
  * [49] H. Zheng, Q. Ye, H. Hu, C. Fang, and J. Shi.  Protecting decision boundary of machine learning model with differentially private perturbation.  IEEE Transactions on Dependable and Secure Computing, 19(3):2007–2022, 2022.