![](https://csdnimg.cn/release/download_crawler_static/15777406/bg4.jpg)
in [17], which provides provable privacy guarantee for any
event sequence occurring at any window of w time stamps.
Before introducing the definition of w-event privacy,we
first explain some notions it requires. We call two datasets
D
i
;D
0
i
at time stamp i as neighboring if they differs in at
most one row. A stream prefix of an infinite series
S ¼ðD
1
;D
2
; ...Þ at time stamp t is defined as S
t
¼ðD
1
;
D
2
; ...;D
t
Þ.
Definition 3 (w-Neighboring [17]). Let w be a positive inte-
ger, two stream prefixes S
t
, S
0
t
are w-neighboring, if
1) for each S
t
½i, S
0
t
½i such that i 2½t and S
t
½i 6¼ S
0
t
½i,it
holds that S
t
½i, S
0
t
½i are neighboring, and
2) for each S
t
½i
1
, S
t
½i
2
, S
0
t
½i
1
, S
0
t
½i
2
with i
1
<i
2
,
S
t
½i
1
6¼ S
0
t
½i
1
and S
t
½i
2
6¼ S
0
t
½i
2
, it holds that
i
2
i
1
þ 1 w.
Definition 4 (w-Event Privacy [17]). A mechanism M satis-
fies w-event -differential privacy, if for all sets S
RangeðMÞ and all w-neighboring stream prefixes S
t
;S
0
t
and
all t, it holds that
Pr½MðS
t
Þ2SexpðÞPr½MðS
0
t
Þ2S: (4)
A mechanism satisfying w-event privacy will protect the
sensitive information that may be disclosed from a sequence
of some length w.
Theorem 3 ([17]). Let M be a mechanism that takes stream pre-
fix S
t
as input, where S
t
½i¼D
i
2D, and outputs s =(s
1
; ...; s
t
) 2 RangeðMÞ. Suppose M can be decomposed into t
mechanisms M
1
; ...; M
t
such that M
i
ðD
i
Þ¼s
i
, each M
i
generates independent randomness and achieves
i
-differential
privacy. Then, M satisfies w-event privacy if
8i 2½t;
X
i
k¼iwþ1
k
: (5)
This theorem enables a w-event private scheme to view
as the total available privacy budget in any sliding window
of size w, and appropriately allocate portions of it across the
time stamps. This is the fundamental theorem, based on
which we design a novel w-event privacy mechanism for
real-time data publishing.
3.3 Problem Statement
Under the architecture of real-time data crowd-sourcing
and data publishing in Fig. 1, in this paper, we consider the
popular statistics application where the “check in” informa-
tion of mobile users in social networks are crowd-sourced
to a trusted server and the statistics (e.g., the number of
users) of each region are continually published in real-time
to the public. We assume that users travel and “check in” at
regions in a two-dimensional area. The “check in” informa-
tion of a user (e.g., location) is crowd-sourced to a trusted
server through cellular network or Wifi hotspots. Based on
the “check in” information, the server creates a database D
over time. The goal is to continually publish statistics com-
puted on D in real-time with w-event privacy guarantee.
Therefore, instead of releasing the true value of statistics,
the trusted server applies an appropriate privacy protection
mechanism and releases a sanitized version of the raw sta-
tistics to the third party (e.g., analysts).
Let D
i
denote the database crowd-sourced at time stamp
i, where each row corresponds to a user and each column
corresponds to the occurrence of users of a region. The
value in row u and column j is 1 if a user u appears at region
j at time stamp i; 0 otherwise. Note that each row of D
i
con-
tains at most one 1 since a user cannot appear at two regions
simultaneously. The trusted server wishes to publish the
statistic of every column in D
i
(the total number of users in
each region). Considering the statistics as the results of a
query Q on D
i
, QðD
i
Þ¼X
i
¼ðx
1
i
;x
2
i
; ...;x
d
i
Þ where d is the
total number of regions and x
j
i
is the number of users at
region j at time stamp i. Since each user can only appear at
most one region per time stamp, the sensitivity DðQÞ¼1.In
order to protect the privacy of statistics, a sanitized version
of x
j
i
, say r
j
i
, is released instead of releasing x
j
i
directly.
Given the statistics at time stamp i, X
i
, its sanitized version
is denoted by R
i
¼ðr
1
i
;r
2
i
; ...;r
d
i
Þ. Therefore, the problem
studied in this paper can be formally stated as follows:
Problem 1. Given an infinite multi-dimensional time series X ¼
fX
1
;X
2
; ...;X
i
; ...g, for each X
i
at time stamp i, release a
sanitized version R
i
in real-time such that the continued release
R ¼fR
1
;R
2
; ...;R
i
; ...g satisfies w-event -differential
privacy.
4RESCUEDP: REAL-TIME SPATIO-TEMPORAL
CROWD-SOURCED DATA PUBLISHING WITH
DIFFERENTIAL PRIVACY
In this section, we present RescueDP, a privacy protection
scheme to realize real-time spatio-temporal data publishing
with w-event privacy guarantee. Fig. 2 shows a high-level
overview of the RescueDP, which mainly consists of five
mechanisms: adaptive sampling, adaptive budget alloca-
tion, dynamic grouping, perturbation and filtering.
We propose an adaptive sampling mechanism that adjusts
the sampling rate according to data dynamics, which perturbs
statistics at selected sampling time stamps and approximates
the non-sampled statistics with perturbed statistics at last
sampling time stamp. Then we propose an adaptive budget
allocation mechanism that dynamically distributes the entire
privacy budget at sampling points over any successive w
time stamps. The idea behind the sampling mechanism and
Fig. 2. A high-level overview of RescueDP.
594 IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, VOL. 15, NO. 4, JULY/AUGUST 2018