OptStream: Releasing Time Series Privately (Extended Abstract)
Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. Journal track. Pages 5135-5139.
https://doi.org/10.24963/ijcai.2020/722
Keywords
- Multidisciplinary Topics and Applications: Security and Privacy
- Constraints and SAT: Constraint Optimization
Abstract
Many applications of machine learning and optimization operate on sensitive data streams, posing significant privacy risks for individuals whose data appear in the stream. Motivated by an application in energy systems, this paper presents OptStream, a novel algorithm for releasing differentially private data streams under the w-event model of privacy. The procedure ensures privacy while guaranteeing bounded error on the released data stream. OptStream is evaluated on a test case involving the release of a real data stream from the largest European transmission operator. Experimental results show that OptStream may not only improve the accuracy of state-of-the-art methods by at least one order of magnitude but also support accurate load forecasting on the privacy-preserving data.
- [Alwan and Roberts, 1988] Layth C Alwan and Harry V Roberts. Time-series modeling for statistical process con- trol. Journal of Business & Economic Statistics, 6(1):87- 95, 1988.
- [Dwork and Roth, 2013] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Theo- retical Computer Science, 9(3-4):211-407, 2013.
- [Dwork, 2010] Cynthia Dwork. Differential privacy in new settings. In Proceedings of the twenty-first annual ACM- SIAM symposium on Discrete Algorithms, pages 174-183. SIAM, 2010.
- [Fioretto and Van Hentenryck, 2018] Ferdinando Fioretto and Pascal Van Hentenryck. Constrained-based differen- tial privacy: Releasing optimal power flow benchmarks privately. In Proceedings of the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR), pages 215-231, 2018.
- [Fioretto and Van Hentenryck, 2019] Ferdinando Fioretto and Pascal Van Hentenryck. Optstream: Releasing time series privately. Journal of Artificial Intelligence Research, 65:423-456, 2019.
- [Fioretto et al., 2020] Ferdinando Fioretto, Terrence W. K. Mak, and Pascal Van Hentenryck. Differential privacy for power grid obfuscation. IEEE Transactions on Smart Grid, 11(2):1356-1366, March 2020.
- [Hardt and Rothblum, 2010] Moritz Hardt and Guy N Roth- blum. A multiplicative weights mechanism for privacy- preserving data analysis. In Foundations of Computer Sci- ence. IEEE, 2010.
- [Kellaris et al., 2014] Georgios Kellaris, Stavros Pa- padopoulos, Xiaokui Xiao, and Dimitris Papadias. Dif- ferentially private event sequences over infinite streams. Proceedings of the VLDB Endowment, 7(12):1155-1166, 2014.
- [Mak et al., 2020] Terrence W. K. Mak, Ferdinando Fioretto, Lyndon Shi, and Pascal Van Hentenryck. Privacy- preserving power system obfuscation: A bilevel optimiza- tion approach. IEEE Transactions on Power Systems, 35(2):1627-1637, March 2020.
- [Nogales et al., 2002] Francisco Javier Nogales, Javier Con- treras, Antonio J Conejo, and Rosario Espínola. Forecast- ing next-day electricity prices by time series models. IEEE Transactions on power systems, 17(2):342-348, 2002.
- [Ochoa and Harrison, 2011] Luis F Ochoa and Gareth P Har- rison. Minimizing energy losses: Optimal accommoda- tion and smart operation of renewable distributed gener- ation. IEEE Transactions on Power Systems, 26(1):198- 205, 2011.
- [Rastogi and Nath, 2010] Vibhor Rastogi and Suman Nath. Differentially private aggregation of distributed time- series with transformation and encryption. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, pages 735-746. ACM, 2010.
- [Zhang, 2003] G Peter Zhang. Time series forecasting using a hybrid arima and neural network model. Neurocomput- ing, 50:159-175, 2003.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
This paper was motivated by a desire to release privacypreserving streams of energy demands, also called loads, in transmission systems. The goal is to protect changes in consumer loads up to some desired amount within critical time intervals. Although customer identities are typically considered public information (e.g., each facility is served by some energy provider), their loads can be highly sensitive as they may reveal the economic activities of grid customers. For example, changes in load consumption may indirectly reveal production levels and strategic investments. Moreover, these time series are often input to complex analytic tasks, e.g., demand forecasting algorithms [Nogales et al., 2002] and optimal power flows [Ochoa and Harrison, 2011]. As a result, the accuracy of the privacy-preserving datasets is critical and, as shown later in the paper, existing privacy-preserving algorithms for time series fall short in this respect for this application.
The main contribution of this paper is a new privacy mechanism that remedies these limitations and is sufficiently precise for use in forecasting and optimization applications. The new algorithm, called OPTSTREAM, is presented under the framework of w-event privacy and is a 4-step procedure consisting of sampling, perturbation, reconstruction, and postprocessing modules. The sampling module selects a small set of points for privacy-preserving measurement in each period of interest, the perturbation module introduces noise to the sampled data points to guarantee privacy, the reconstruction module re-assembles the non-sampled data points from the perturbed ones, and the post-processing module uses convex optimization over the privacy-preserving output of the previous modules, as well as the privacy-preserving answers of additional queries on the data stream, to improve accuracy by redistributing the added noise. It is important to emphasize that, although OPTSTREAM was motivated by an energy application, it is potentially useful for many other domains since its design is independent of the underlying problem.
�This paper is an extended abstract of the article OptStream: Releasing Time Series Privately in Journal of Artificial Intelligence Research [Fioretto and Van Hentenryck, 2019].
OPTSTREAM is evaluated on real datasets from R´eseau de Transport d' ´Electricit´e, the French transmission operator and the largest in Europe. Experimental results show that OPTSTREAM improves the accuracy of state-of-the-art algorithms by at least one order of magnitude for this application domain and show that it supports accurate load forecasting on the privacy-preserving data.
2 Preliminaries
2.1 PrivacyModel and Goals
A data stream is an infinite sequence of tuples pi, tq, describing an event reported by user i that occurred at a discrete time t. This paper uses a simplified notation and denotes the data stream as a vector x � px1, x2, . . .q with each xt P R� describing a positive quantity, such as that associated to the aggregated consumption of a set of customers at time t. A stream prefix xrts describes the sequence x1, . . . , xt of all tuples observed on or before time t.
At every time step t, the data curator receives information about data xt and wishes to privately report such quantity. In the target application of this paper, the data curator is interested in publishing every element xt for a recurring period of w time steps. A w-period is a set of w contiguous time steps t�w�1,. . . ,t (w¥1). Thus, private reports xt are generated in real time for windows of w time steps.
2.2 Differential Privacy and w-Privacy
Differential Privacy [Dwork, 2010] focuses on protecting the participation of an individual user in a computation. In a nutshell, an algorithm A, that takes as input a dataset D and returns a response o from some output set, is ϵ-differentially private if, for all possible datasets D1 differing from D by only one individual, and any output responses o,
The privacy level is controlled by parameter ϵ ¥ 0, describing the privacy loss, with small values denoting strong privacy.
The w-event privacy framework [Kellaris et al., 2014] extends the definition of differential privacy to protect data streams. The framework operates on stream prefixes and two data streams prefixes xrts and x1 rts are said w-neighbors, denoted by xrts �w x1 rts, if
- for each xi, x1i with i P rts, xi � x1i , and
- for each xi, x1i , xj, x1j such that i � j P rts and xi � x1i , xj � x1j , j � i � 1 / w holds.
In other words, two stream prefixes are w-neighbors if their elements are pairwise neighbors and all the differing elements are within a time window of up to w time steps. As a result, when ensuring the privacy guarantees, the w-event framework does not consider data streams where the differences are beyond a time window of size w: It only needs to consider windows of w elements.
Definition1 (w-privacy) Let A be a randomized algorithm that takes as input a stream prefix xrts of arbitrary size and outputs an element o from a set of possible output sequences O. Algorithm A satisfies w-event ϵ-differential privacy (wprivacy for short) if, for all t, all outputs o P O, and all w-neighboring stream prefixes xrts and x1 rts:
An algorithm satisfying w-privacy protects the sensitive information that could be disclosed from a sequence of finite length w. All the classical properties of differential privacy, including composability and immunity to post-processing [Dwork and Roth, 2013] carry over to w-privacy.
The Laplace mechanism which adds Laplace noise to each element of the stream with parameter w∆{ϵ achieves wprivacy [Kellaris et al., 2014], where ∆ is the maximal contribution of an individual to the data stream.
3 OptStreamFor StreamRelease
The proposed algorithm processes a data stream x � px1, x2, . . .q, along with the period size w whose privacy is to be protected, and the total privacy loss ϵ, and outputs a privacy-preserving version ˆx � pˆx1, ˆx2, . . .q of the stream x. OPTSTREAM processes the data stream in consecutive and disjoint w-periods consists of four steps: (1) data sampling, (2) perturbation, (3) reconstruction of the non-sampled data points, and (4) optimization-based post-processing, summarized below. 1 The algorithm seeks to balance two types of
1 For an in-depth description of the OPTSTREAM procedures and their theoretical analysis, please refer to the full paper [Fioretto and Van Hentenryck, 2019].
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
g
G
p
u
I
m
d
/
7
Y
A
Q
L
H
V
k
>
B
c
N
S
8
E
J
3
U
r
q
9
5
K
o
M
C
F
T
+
z
D
Z
j
w
y
X
O
W
n
f
P
0
2
v
R
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
g
G
p
u
I
m
d
/
7
Y
A
Q
L
H
V
k
>
B
c
N
S
8
E
J
3
U
r
q
9
5
K
o
M
C
F
T
+
z
D
Z
j
w
y
X
O
W
n
f
P
0
2
v
R
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
g
G
p
u
I
m
d
/
7
Y
A
Q
L
H
V
k
>
B
c
N
S
8
E
J
3
U
r
q
9
5
K
o
M
C
F
T
+
z
D
Z
j
w
y
X
O
W
n
f
P
0
2
v
R
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
g
G
p
u
I
m
d
/
7
Y
A
Q
L
H
V
k
>
B
c
N
S
8
E
J
3
U
r
q
9
5
K
o
M
C
F
T
+
z
D
Z
j
w
y
X
O
W
n
f
P
0
2
v
R
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
W
T
V
U
F
I
o
S
m
O
2
c
K
5
Q
z
j
+
E
>
A
C
3
d
B
L
w
M
G
v
Y
9
g
k
X
Z
r
8
P
0
y
D
J
u
f
/
N
H
7
q
p
n
R
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
W
T
V
U
F
I
o
S
m
O
2
c
K
5
Q
z
j
+
E
>
A
C
3
d
B
L
w
M
G
v
Y
9
g
k
X
Z
r
8
P
0
y
D
J
u
f
/
N
H
7
q
p
n
R
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
W
T
V
U
F
I
o
S
m
O
2
c
K
5
Q
z
j
+
E
>
A
C
3
d
B
L
w
M
G
v
Y
9
g
k
X
Z
r
8
P
0
y
D
J
u
f
/
N
H
7
q
p
n
R
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
W
T
V
U
F
I
o
S
m
O
2
c
K
5
Q
z
j
+
E
>
A
C
3
d
B
L
w
M
G
v
Y
9
g
k
X
Z
r
8
P
0
y
D
J
u
f
/
N
H
7
q
p
n
R
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
W
M
w
c
z
B
E
L
P
K
8
G
3
9
>
A
7
H
V
N
S
J
X
O
0
I
g
F
U
D
m
/
Y
v
T
y
5
r
2
+
Q
u
n
d
f
k
o
q
j
R
C
Z
p
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
W
M
w
c
z
B
E
L
P
K
8
G
3
9
>
A
7
H
V
N
S
J
X
O
0
I
g
F
U
D
m
/
Y
v
T
y
5
r
2
+
Q
u
n
d
f
k
o
q
j
R
C
Z
p
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
W
M
w
c
z
B
E
L
P
K
8
G
3
9
>
A
7
H
V
N
S
J
X
O
0
I
g
F
U
D
m
/
Y
v
T
y
5
r
2
+
Q
u
n
d
f
k
o
q
j
R
C
Z
p
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
W
M
w
c
z
B
E
L
P
K
8
G
3
9
>
A
7
H
V
N
S
J
X
O
0
I
g
F
U
D
m
/
Y
v
T
y
5
r
2
+
Q
u
n
d
f
k
o
q
j
R
C
Z
p
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
r
w
j
K
+
C
m
M
c
y
H
k
v
X
E
9
0
B
N
P
W
>
A
7
V
S
8
J
3
O
L
I
F
G
Q
p
2
Y
T
d
f
D
5
g
/
Z
u
R
z
n
q
o
U
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
r
w
j
K
+
C
m
M
c
y
H
k
v
X
E
9
0
B
N
P
W
>
A
7
V
S
8
J
3
O
L
I
F
G
Q
p
2
Y
T
d
f
D
5
g
/
Z
u
R
z
n
q
o
U
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
r
w
j
K
+
C
m
M
c
y
H
k
v
X
E
9
0
B
N
P
W
>
A
7
V
S
8
J
3
O
L
I
F
G
Q
p
2
Y
T
d
f
D
5
g
/
Z
u
R
z
n
q
o
U
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
r
w
j
K
+
C
m
M
c
y
H
k
v
X
E
9
0
B
N
P
W
>
A
7
V
S
8
J
3
O
L
I
F
G
Q
p
2
Y
T
d
f
D
5
g
/
Z
u
R
z
n
q
o
U
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
g
w
R
d
j
8
+
9
W
C
y
o
3
m
k
D
J
B
E
>
A
7
H
c
V
N
S
U
r
q
/
L
p
5
K
I
M
F
T
Q
z
u
G
Z
Y
f
v
O
X
n
0
P
2
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
g
w
R
d
j
8
+
9
W
C
y
o
3
m
k
D
J
B
E
>
A
7
H
c
V
N
S
U
r
q
/
L
p
5
K
I
M
F
T
Q
z
u
G
Z
Y
f
v
O
X
n
0
P
2
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
g
w
R
d
j
8
+
9
W
C
y
o
3
m
k
D
J
B
E
>
A
7
H
c
V
N
S
U
r
q
/
L
p
5
K
I
M
F
T
Q
z
u
G
Z
Y
f
v
O
X
n
0
P
2
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
g
w
R
d
j
8
+
9
W
C
y
o
3
m
k
D
J
B
E
>
A
7
H
c
V
N
S
U
r
q
/
L
p
5
K
I
M
F
T
Q
z
u
G
Z
Y
f
v
O
X
n
0
P
2
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
U
L
K
m
g
k
T
I
f
+
N
R
H
M
A
Y
W
P
>
B
7
c
V
S
8
E
J
3
X
O
0
9
F
j
w
r
G
C
Q
v
p
2
d
D
5
/
Z
u
z
n
y
q
o
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
U
L
K
m
g
k
T
I
f
+
N
R
H
M
A
Y
W
P
>
B
7
c
V
S
8
E
J
3
X
O
0
9
F
j
w
r
G
C
Q
v
p
2
d
D
5
/
Z
u
z
n
y
q
o
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
U
L
K
m
g
k
T
I
f
+
N
R
H
M
A
Y
W
P
>
B
7
c
V
S
8
E
J
3
X
O
0
9
F
j
w
r
G
C
Q
v
p
2
d
D
5
/
Z
u
z
n
y
q
o
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
U
L
K
m
g
k
T
I
f
+
N
R
H
M
A
Y
W
P
>
B
7
c
V
S
8
E
J
3
X
O
0
9
F
j
w
r
G
C
Q
v
p
2
d
D
5
/
Z
u
z
n
y
q
o
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
w
u
A
m
k
0
F
q
X
S
T
5
/
g
B
o
Z
P
R
H
>
7
c
V
N
8
E
J
3
W
O
L
I
9
j
r
G
C
Q
K
v
p
2
Y
d
f
M
D
+
z
n
y
U
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
w
u
A
m
k
0
F
q
X
S
T
5
/
g
B
o
Z
P
R
H
>
7
c
V
N
8
E
J
3
W
O
L
I
9
j
r
G
C
Q
K
v
p
2
Y
d
f
M
D
+
z
n
y
U
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
w
u
A
m
k
0
F
q
X
S
T
5
/
g
B
o
Z
P
R
H
>
7
c
V
N
8
E
J
3
W
O
L
I
9
j
r
G
C
Q
K
v
p
2
Y
d
f
M
D
+
z
n
y
U
<
l
a
t
e
x
i
s
h
1
_
b
6
4
=
"
w
u
A
m
k
0
F
q
X
S
T
5
/
g
B
o
Z
P
R
H
>
7
c
V
N
8
E
J
3
W
O
L
I
9
j
r
G
C
Q
K
v
p
2
Y
d
f
M
D
+
z
n
y
U
errors: a perturbation error, introduced by the application of additive noise at the sampled points, and a reconstruction error, introduced by the reconstruction procedure at the nonsampled points. The higher the number of samples in a wperiod, the more perturbation error is introduced while the reconstruction error may be reduced, and vice-versa. The error generated by these two components, in combination with the number of samples that minimizes the error, are analyzed in the full paper.
The SAMPLE Procedure
The procedure selects a subsample S of k points for each wperiod. Its goal is to perform a dimensionality reduction over the data stream whose sample points can be used to generate privacy-preserving stream data points with low error. It does so by minimizing the L1 error between the values associated to the original data points x and those associated to the points generated by a linear interpolation ξS of the k selected points, denoted as xS �pxi|i P Sq. Formally, it minimizes the following quantity: �iPS |ξS i � xSi |. The idea is illustrated in Figure 1. The procedure uses a DP greedy algorithm to select a set S that produces a low L1 error. It is an instantiation of the Sparse Vector Technique [Hardt and Rothblum, 2010], an iterative algorithm that allows answering a sequence of queries consuming low privacy loss, and it uses a portion ϵs of the overall privacy loss budget ϵ.
The PERTURB Procedure
Next, OPTSTREAM uses the canonical Laplace mechanism to guarantee privacy perturbing the k data points sampled in the previous step. The perturbed data points ˜xS of x satisfy ϵp-differential privacy, with ϵp being a portion of the overall privacy loss budget ϵ.
The RECONSTRUCT Procedure
The goal of the reconstruction procedure is to re-assemble the non-sampled data point from the perturbed ones ˜xS using linear interpolation. The procedure uses exclusively privacypreserving data and thus induces no additional privacy loss. In [Fioretto and Van Hentenryck, 2019] the paper analyzes the error induced by this step on the data stream.
The POST-PROCESS Procedure
Finally, the algorithm uses a key post-processing component to enforce consistency of salient features of the data. Its essence is a convex optimization program that employs the privacy-preserving output ˜xS of the above modules, as well as privacy-preserving answers to additional queries (called feature queries) on the data stream.
Formally, a feature is a partition of the w-period and we say that a feature F1 is a sub-feature of F, denoted by F1 � F, if F1 is obtained by sub-partitioning F. The feature query QFpxq associated with feature F � td1, . . . , dmu returns an m-dimensional vector pc1, . . . , cmq where each ci is the sum of the values xj of x for j P di. For example, a feature Fipxq may be described by the partition Fi � tt1, . . . , tw{2uu, trw{2s, . . . ,wuu that divides the winterval in two equal segments, and its associated query set QFi � t�tw{2u j�1 xj, �wj�rw{2s xju represents the aggregated count on the partition induced by Fi on x. For notational simplicity, we assume that the first feature always partitions the data stream w-period into singletons, i.e., F1 � ttiu : i P rwsu. Note that its associated privacy-preserving query QF1 � ˜x is the output of the perturbation procedure.
When viewed as queries, the inputs to the mechanism can be represented as a set of values QFi pxq � ci � pci1, . . . , cimi q p1 / i / pq or, more concisely, as c � pc11, . . . , cpmp q, and ˜c is used to represent their associated noisy (i.e., privacy-preserving) version, obtained via an application of the Laplace mechanism. We assume that a partial ordering � of features is given, and notice that the feature queries QFpxq form a lattice on x. The essence of this procedure is the following optimization program that finds a new vector x� that minimizes:
,
Its decision variables are the post-processed values 9x � p 9x11, . . . , 9xpmp q and the objective minimizes the squared L2Norm of 9x � ˜ c. The optimization is subject to a set of consistency constraints among comparable features (Constraints (O2)) and non-negativity constraints on the variables (Constraints (O3)). By definition of sub-features, there exists a set of elements in Fi1 whose union is equal to dij.
Fioretto and Van Hentenryck [2019] shows that the optimization-based post-process achieves ϵo-differential privacy, it bounds the expected error with respect to the original stream by a contact factor, and that OPTSTREAM satisfies wevent ϵ-differential privacy.
4 Evaluation
Dataset and Algorithms
The source data was obtained through a collaboration with R´eseau de Transport d' ´Electricit´e, the largest energy transmission system operator in Europe. It consists of a one-year national-level load energy consumption data, which is aggregated at a regional level. Each data point in the stream represents the total load consumption of the customers served within a region during a 30 minute time period. For evaluation purposes, the experiments often consider a representative region (Auvergne - Rhˆone-Alpes) to analyze the data stream release.
The following sections compare OPTSTREAM against the Laplace mechanism and the Discrete Fourier Transform (DFT) algorithm [Rastogi and Nath, 2010]. All the algorithms release privacy-preserving data associated with the
13000
12000
13000
11000
12000
13000
10000
11000
12000
9000
10000
11000
8000
9000
10000
7000
8000
9000
6000
7000
8000
5000
6000
7000
4000
5000
6000
13000
4000
5000
12000
4000
13000
11000
12000
13000
10000
11000
12000
9000
10000
11000
8000
9000
10000
7000
8000
9000
6000
7000
8000
5000
6000
7000
4000
5000
6000
13000
4000
5000
12000
4000
13000
11000
12000
13000
10000
11000
12000
9000
10000
11000
8000
9000
10000
7000
8000
9000
6000
7000
8000
5000
6000
7000
4000
5000
6000
4000
5000
4000
13000
12000
13000
11000
12000
13000
10000
11000
12000
9000
10000
11000
8000
9000
10000
7000
8000
9000
6000
7000
8000
5000
6000
7000
4000
5000
6000
Jan
4000
2016
13000
Jan
5000
12000
2016
4000
13000
11000
2016
Jan
10000
12000
13000
11000
12000
9000
10000
11000
8000
9000
10000
7000
8000
9000
6000
7000
8000
5000
6000
7000
4000
5000
6000
Jan
4000
2016
13000
5000
12000
Jan
2016
4000
13000
11000
2016
Jan
12000
13000
10000
11000
12000
9000
10000
11000
8000
9000
10000
7000
8000
9000
6000
7000
8000
5000
6000
7000
4000
5000
6000
2016
Jan
4000
5000
2016
Jan
04
4000
Jan
2016
13000
12000
13000
12000
11
13000
12000
25
18
18
13000
12000
25
13000
12000
13000
12000
11
13000
12000
25
18
18
13000
12000
25
13000
12000
13000
12000
11
13000
12000
25
18
18
13000
12000
25
13000
12000
13000
12000
11
Jan
04
5000
2016
4000
Jan
5000
2016
04
Jan
4000
11
Jan
11
18
2016
Jan
11
18
Jan
25
18
11
11
04
04
04
11
04
04
11
18
25
18
25
Feb
25
18
5000
4000
Feb
25
5000
2016
Jan
Feb
25
04
4000
Jan
Feb Feb Feb
5000
2016
Jan
Feb
4000
Jan
04
5000
2016
Jan
04
4000
11
Jan
04
Feb
11
18
2016
Jan
11
18
Jan
25
18
11
11
04
04
04
11
04
11
18
25
18
25
Feb
25
18
5000
4000
Feb
25
5000
2016
Jan
Feb
25
04
4000
Jan
Feb Feb Feb
5000
2016
04
Jan
Feb
4000
Jan
Feb
5000
2016
04
Jan
4000
11
Jan
11
18
2016
Jan
11
18
Jan
25
18
11
11
04
04
04
04
11
04
11
18
25
18
25
Feb
25
18
5000
4000
Feb
25
5000
2016
Jan
Feb
25
04
4000
Jan
Feb Feb
04
Feb Jan Feb
5000
2016
04
4000
Jan
04
Feb
5000
2016
04
4000
Jan
11
Jan
18
11
2016
Jan
11
18
Jan
25
18
11
11
04
11
04
04
11
25
18
18
25
Feb
25
18
2016 2016 2016 2016 2016 2016 2016 2016 2016 2016 2016 2016 2016 2016 2016 Figure 2: Real load consumption data, in MW, for the AuvergneRhˆone-Alpes region in January 2016 (first column) and its privacypreserving versions obtained using Laplace (second column), DFT (third column), and OPTSTREAM (fourth column) with privacy loss ϵ � 1 (top), ϵ � 0.1 (middle), and ϵ � 0.01 (bottom).
Feb
sub-streams x for each w-period and preserve the same level of privacy. An in-depth description of the algorithms, their parameters, and evaluation setting, as well as a more extensive evaluation, that uses additional algorithms and settings, are provided in the full paper.
Privacy-Preserving Stream Release
Answering queries over contiguous w-periods corresponds to releasing the privacy-preserving stream over the entire available duration. Figure 2 illustrates the real and privacypreserving versions of the data-stream for the AuvergneRhˆone-Alpes region in January, 2016. It uses w-periods of size 48 for given privacy losses ϵ � 1.0, 0.1, and 0.01, shown in the top, middle, and bottom rows, respectively. The choice for the w-period allows the data curator to ensure the protection of the observed power consumptions within each period. Thus, the released stream protects loads in each entire day.
The real loads are illustrated in the first column. The figure compares our proposed OPTSTREAM algorithm (fourth column) against the Laplace mechanism (second column), and the DFT algorithm [Rastogi and Nath, 2010] (third column). The experiments set the number of Fourier coefficients in the DFT and sampling steps in OPTSTREAM to 10. The privacy loss allocated to perform each measurement is split equally. Additionally, for OPTSTREAM ϵs � ϵp � ϵo � 13 ϵ. Finally, OPTSTREAM uses feature queries representing salient moments in the day associated with different consumption patterns. These are proxy of consumer behaviors and thus energy consumption. Finally, if an algorithm reports negative noisy value for a stream point, we truncate it to zero.
Figure 2 clearly illustrates that, for a given privacy disclosure level, OPTSTREAM produces privacy-preserving streams that are substantially more accurate than its competitors when visualized.
A quantification of the errors reported by the algorithms is reported in Figure 3. It shows the L1-errors (in logarithmic scale) between the original x and the privacy preserving ˆx streams obtained by the algorithms analyzed for the months of February (left), June (middle), and October (right). These
18
25
Feb
25
18
18
Feb
25
18
Feb
25
Feb
25
18
18
Feb
25
18
Feb
25
Feb
25
18
18
Feb
25
Feb
25
Feb
25
Feb
25
Feb
25
Feb
25
Feb
25
Feb
25
Feb
25
Feb
25
Feb Feb Feb Feb Feb Feb Feb Feb Feb Feb Average L1 Error
10 4
10 3
10 2
10 1
10 0
months capture the different customers load profile behaviors due to different weather patterns and durations of the day light. In addition to OPTSTREAM (denoted with suffix LS, in the Figure) an additional version (OPTSTREAMES) is presented; It differs from OPTSTREAM only for its sampling process, which is equally-spaced and thus spends no privacy loss budget (i.e., ϵs � 0). The figure highlights that OPTSTREAM consistently outperforms competitor algorithms.
Impact of Privacy on Forecasting Demand
The final results evaluate the capability of the released privacy-preserving streams to accurately predict future consumptions. To do so, the paper adopts the Autoregressive Moving Average (ARMA) model [Alwan and Roberts, 1988; Zhang, 2003], which is a popular stochastic model used for predicting future points in a time series. The ARMA model with parameters p and q refers to the model with p autoregressive terms and q moving-average terms: It estimates a future time step value xt as c � βt � �pi�1 φixt�i � �qi�1 θiβt�i, where where c is a constant, βt is a random variable modeling white noise at time t, φi and θi are, respectively, the autoregressive and moving average model parameters.
The experiments use an ARMA model with parameters p � q � 1 to estimate the future 48 time steps (corresponding to a day) when trained with the past four weeks of the privacypreserving data stream estimated using Laplace, DFT, and OPTSTREAM with L1-sampling. All models use the same parameters adopted in the previous sections.
Figure 4 visualizes the forecast for the load consumptions in the Auvergne-Rhˆone-Alpes region for February 2, 2016. The black and gray solid lines illustrate, respectively, the real load values observed so far and those of the day to be forecasted. The dotted red lines illustrate the privacy-preserving stream data estimated so far (and used as input to the predic- Average L1 Error
0.01
10 5
10 4
10 3
10 2
0.01
tion model) and the solid red lines depict the prediction obtained using the ARMA model. Figure 4 shows the forecast results using the real data (Real) and the privacy-preserving stream obtained through Laplace, DFT, and OPTSTREAM, respectively. The figure clearly shows that OPTSTREAM is able to produce substantially better estimates for the next day forecast.
The experiments also quantitatively evaluate the average L1-error for each prediction produced by the mechanisms. They adopt the same setting as above for the prediction and report, in Figure 5, the average L1-errors for predicting each day in the month of February, June, and October for the Auvergne-Rhˆone-Alpes region. Each histogram reports the log10 value of the average error of 30 random trials. We observe that OPTSTREAM reports substantially smaller errors compared to all other privacy-preserving algorithms, and that the error made by OPTSTREAM in reporting the next day forecast is closer to the error made in the forecast prediction using the real data than when using another method.
5 Conclusions
This paper presented OPTSTREAM, a novel algorithm for privately releasing stream data in the w-event privacy model. OPTSTREAM is a 4-step procedure consisting of sampling, perturbation, reconstruction, and post-processing modules. OPTSTREAM was evaluated on a real dataset from the largest transmission operator in Europe. Experimental results on multiple test cases show that OPTSTREAM improves the accuracy of the state-of-the-art by at least one order of magnitude in this application domain. The accuracy improvements are measured, not only in terms of the error distance to the original stream but also in the accuracy of a popular load forecasting algorithm trained on privacy-preserving data substreams. In the full paper, the results additionally show that OPTSTREAM exhibits similar benefits on hierarchical stream data which is also highly desirable in practice. An important direction of future work is to generalize these results to the streaming setting where a data element is emitted at each time step. Future work will also focus on ensuring that salient properties of an optimization problem of interest hold, when the problem relies on inputs that include the load consumption data, e.g., as in [Fioretto and Van Hentenryck, 2018; Fioretto and Van Hentenryck, 2018; Fioretto et al., 2020; Mak et al., 2020].
0.01
@inproceedings{ijcai2020p722,
title = {OptStream: Releasing Time Series Privately (Extended Abstract)},
author = {Fioretto, Ferdinando and Van Hentenryck, Pascal},
booktitle = {Proceedings of the Twenty-Ninth International Joint Conference on
Artificial Intelligence, {IJCAI-20}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
editor = {Christian Bessiere},
pages = {5135--5139},
year = {2020},
month = {7},
note = {Journal track},
doi = {10.24963/ijcai.2020/722},
url = {https://doi.org/10.24963/ijcai.2020/722},
}
TY - CPAPER TI - OptStream: Releasing Time Series Privately (Extended Abstract) AU - Fioretto, Ferdinando AU - Van Hentenryck, Pascal T2 - Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20 PB - International Joint Conferences on Artificial Intelligence Organization PY - 2020 SP - 5135 EP - 5139 DO - 10.24963/ijcai.2020/722 UR - https://doi.org/10.24963/ijcai.2020/722 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
