# A Review of Differential Privacy in Individual Data Release

Authors: Jun Wang; Shubo Liu; Yongkai Li
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

The rapid development of mobile technology has improved users’ quality of treatment, and tremendous amounts of medical information are readily available and widely used in data analysis and application, which bring on serious threats to users’ privacy. Classical methods based on cryptography and anonymous-series models fail due to their high complexity, poor controllability, and dependence on the background knowledge of adversaries when it comes to current mobile healthcare applications. Differential privacy is a relatively new notion of privacy and has become the de facto standard for a security-controlled privacy guarantee. In this paper, the key aspects of basic concepts and implementation mechanisms related to differential privacy are explained, and the existing research results are concluded. The research results presented include methods based on histograms, tree structures, time series, graphs, and frequent pattern mining data release methods. Finally, shortcomings of existing methods and suggested directions for future research are presented.


---

## Body

## 1. Introduction

With the further development of mobile technology, it is easy to attain, store, and analyze mobile healthcare information, such as physiological data, social interactions, consumer record, and track data, which all inevitably involve user’s privacy. MHR (mobile healthcare record) has been questioned because of user’s privacy disclosure since its inception due to the high sensitivity of health data [1, 2]. In 2015, MIT researchers (de Montjoye et al. [3]) reported that the so-called unimportant dates and locations of only four pieces of consumption records are enough to identify 90 percent of the people in a dataset recording three months of credit-card transactions by 1.1 million users. Based on concerns about user’s privacy in mobile healthcare, researchers propose a series of privacy protection schemes mainly including data distortion, data encryption, and restrictive release [4].The anonymity models based on restrictive release were proposed greatly to guarantee user’s privacy in healthcare application [5], such as k-anonymity, l-diversity, and t-closeness. k-anonymity was first introduced by Sweeney and Samarati [6, 7] and it has the property that each record is indistinguishable from at least k-1 records; however, it may disclose privacy information [8, 9], so l-diversity and t-closeness were proposed to enhance privacy security. But all these methods fail to offer quantifiable guarantee for user’s privacy and are short of demarcation clearly for adversary’s ability.Avancha et al. [10] presented the privacy problems in mHealth systems and gave a conceptual privacy framework without specific technology; Francis et al. [11] proposed a privacy preserving model for the e-health system which uses the trusted authority to maintain the privacy of user’s health records; Sadki and El Bakkali [12] proposed an integrated privacy module to protect user’s privacy in mobile healthcare. However, existing privacy preserving models mainly depend on the background knowledge of adversaries who may harm the data by reidentifying it [1]. By reason of the dependence, the research of privacy protection falls into the strange circle; that is, a method is proposed to protect the privacy and is broken subsequently. Then, another method is proposed to solve this problem and is broken again, but differential privacy [13] can protect the presence of an individual regardless of the adversary’s background knowledge and give the demarcation of adversary’s ability.In 2006, differential privacy based on probability model was first proposed by Dwork. It could be classified as data distortion and uses random noise to ensure that the adversary fails to guess whether the tuple is present in the dataset with high probability even if he knows all the tuples except the current tuple, which is the theoretical upper limit of attacking capability of the adversary. Differential privacy is a strictly provable and security-controlled method and is introduced quickly and widely to other data application scenes since it was proposed in database domain [14–16]. The popularity of network applications [17, 18] will certainly promote the development of differential privacy.Leoni [19] reviewed differential privacy, which contains noninteractive processing and is mainly classified under technical level, such as dimensionality reduction and filtering; Xiong et al. [20] gave a survey on differential privacy and applications and neglected time series and graph data release methods; Yang et al. [21] described the classification of differential privacy; however, the detailed statement is insufficient. As the classification of many existing surveys is incomplete and its account is not quite clear, this paper is going to summarize the state of the art in differential privacy research from data level, mainly including a variety of categories, histogram, tree structure, time series, graph, and frequent pattern mining data release methods, and then to discuss open problems by analysis and comparison of existing methods.The rest of this paper is organized as follows. Section2 provides the preliminaries on differential privacy and implementation mechanism. Section 3 introduces data processing models and releasing strategies of differential privacy. Section 4 presents data release methods of differential privacy. Finally, it comes to conclude the paper and presents research directions for future work in Section 5.


## 2. Preliminaries

Differential privacy is a relatively new notion of privacy and is one of the most popular privacy concepts as well. Starting from the basic concept of privacy, this section introduces the notion, implementation mechanism, and two important properties of differential privacy.


### 2.1. Base Definitions

Privacy is most often defined as the right to be left alone, free from intrusion or interruption. It is an umbrella term, encompassing elements such as physical privacy, communications privacy, and information privacy [22].Intuitionally, differential privacy ensures that the removal or addition of a single database tuple does not affect the outcome of any analysis [23]. The definition of differential privacy is as follows.Definition 1 (differential privacy [13]).
LetD and D′ be two neighboring datasets which differ on at most one tuple, denoted by d(D,D′)=1; given a randomized function A:D→R, Range(A) is the set of all possible outputs of A in D and D′, and given an arbitrary subset S⊆Range(A), A is said to be ε-differential privacy if (1)Pr⁡AD∈S≤exp⁡ε∗Pr⁡AD′∈S.The parameterε is called privacy budget, which is used to control the ratio of output of function A in neighboring datasets D and D′. The smaller ε is, the more close ratio is to 1; that is to say, the output probability distributions of function A in neighboring datasets D and D′ are approximately the same; meanwhile, the higher the security becomes, the lower the utility gets. The value of ε is small usually, such as 0.01, 0.1, 0.5, and 0.8.The strong privacy guarantee of differential privacy comes at the price of much noise added to the results of queries and analyses [21]. Dwork et al. further proposed enhancing the utility of data by reducing the requirements of data security; then (ε,δ)-differential privacy was proposed to this issue.Definition 2 ((ε,δ)-differential privacy [24, 25]).
LetD and D′ be two neighboring datasets which differ on at most one tuple, denoted by d(D,D′)=1; given a randomized function A:D→R, Range(A) is the set of all possible outputs of A in D and D′, and given an arbitrary subset S⊆Range(A), A is said to be (ε,δ)-differential privacy if(2)Pr⁡AD∈S≤exp⁡ε∗Pr⁡AD′∈S+δ.No hard rule dictates what value of privacy budgetε and δ should be and they can be set according to the actual application requirements. The value of δ is small usually (δ≤10-4) and (ε,δ)-differential privacy equals ε-differential privacy when δ=0.The output probabilities of randomized functionA in neighboring datasets D and D′ for ε-differential privacy are shown in Figure 1 [26, 27], where c≤|A(D)-A(D′)|; the larger c is, the wider the distribution will be and the higher the probability of adding more noise becomes.Figure 1
Output probabilities of randomized functionA in neighboring datasets D and D′.FunctionA provides privacy guarantee by adding random noise to the output; that is, A(D)=f(D)+noise, where f is such query operations as average, count, and sum and noise is the random noise following Laplace distribution which will be introduced in Section 2.2. The smaller the difference between two curves is, the stronger the security received is.A simple attack example is as follows: Table1 is a health dataset and provides count service f(x)=count(·) for querying the number of people suffering from HIV. Without privacy protection strategy, the adversary just needs to query the number of four people containing Alice with HIV which is Yes and the number of three people excluding Alice also with HIV is Yes; then the adversary obtains that Alice is suffering from HIV only by count(4)-count(3)=1. Obviously, practical application for health data release comes to failure if it fails to resist these attacks.Table 1
Health records.
Name
HIV (0 is No; 1 is Yes)
Address
Tim
0
New York
Bob
1
Washington
Tony
0
New York
Alice
1
Hawaii
⋮
⋮
⋮Now, we add a random noise to the output of count functionf and let two count results fall into the same range with higher probability; for example, count(3)={1,1.5,2} and count(4)={1,1.5,2}; by this time, the adversary fails to get Alice’s health information by the above method as both count(4) and count(3) may output 1.5 and count(4)-count(3)=0. Differential privacy gives the maximum capacity of the adversary in this instance; that is to say, the adversary knows statistics whether the Alice is present in the dataset or not.


### 2.2. Noise Mechanism

The two main noise mechanisms are Laplace mechanism and exponential mechanism, and the noise magnitude refers to privacy budget and global sensitivity.Definition 3 (global sensitivity [13]).
Given a randomized functionf:D→Rd, the global sensitivity of function f is(3)Δf=maxD,D′fD-fD′1,where D and D′ are two neighboring datasets, R is the real space of mapping, d is the dimension, and fD-fD′1 is the first-order norm distance between f(D) and f(D′) and is denoted by L1=fD-fD′1.The global sensitivity for count functionΔf=1; however, Δf is larger for other operations. For instance, given dataset D={1,1,1,1,21}, f is sum operation; then the global sensitivity Δf=21 is larger than the sensitivity of count function. So Nissim et al. first proposed the notion of local sensitivity to reduce the sensitivity magnitude as the noise will become large with the increasing of global sensitivity.Definition 4 (local sensitivity [41, 42]).
Given a randomized functionf:D→Rd, the local sensitivity LSf of function f is(4)LSf=maxD′⁡L1.For example, given the subsetD1={1,1,1,1} of D, the local sensitivity LSf=1 is smaller than the global sensitivity 21 under adding operation. Local sensitivity may reduce the noise magnitude, but noise magnitude might reveal information about the dataset; for details see [41, Example  1]. So Nissim et al. further proposed the notion of β-smooth sensitivity to avoid disclosing privacy information; now the added noise is proportional to a smooth upper bound on the local sensitivity.Definition 5 (smooth sensitivity [41]).
Forβ>0, given a randomized function f:D→Rd, the β-smooth sensitivity Sf,β(D) of function f is(5)Sf,βD=maxD′⁡LSfD′·e-βdD,D′.


#### 2.2.1. Laplace Mechanism

The literature [42] proposed Laplace mechanism to achieve differential privacy by adding random noise drawn from the Laplace distribution to the output. Its definition is as follows.Definition 6 (Laplace mechanism).
Given a datasetD and the function f:D→Rd, global sensitivity is Δf; random algorithm A(D)=f(D)+noise satisfies ε-differential privacy if the noise obeys the Laplace distribution; that is, noise~Lap(Δf/ε); thereinto, location parameter is 0 and scale parameter is Δf/ε.
LetLap(b) denote the Laplace distribution when location parameter is 0 and scale parameter is b, and its probability density function is p(x)=exp(-|x|/b)/2b. From Figure 2, the larger the noise added to the output is, the larger b is and, meanwhile, the smaller ε becomes.
Letσ(x) denote standard deviation; D(x) denotes variance, and noise~Lap(b), σ(x)=D(x), D(x)=2b2, and b=Δf/ε; then we obtain the results D(x)=2(Δf/ε)2=2Δf2/ε2, σ(x)=D(x)=2Δf2/ε2=2Δf/ε.Figure 2
Probability density function.


#### 2.2.2. Exponential Mechanism

Laplace mechanism is used when the output is numerical, and exponential mechanism is another security-controlled scheme to satisfy differential privacy when the outputs are nonnumerical.Intuitionally, exponential mechanism still ensures that the change of a single database tuple does not affect the outcome of the score function, and the definition is as follows.Definition 7 (exponential mechanism [43]).
LetD denote the input dataset; r∈R denotes a potential answer, given a score function u:D×R→R; if a random algorithm A selects an answer based on the following probability, then algorithm A is said to satisfy ε-differential privacy:(6)AD,u=r:∣Pr⁡r∈R∝exp⁡εuD,r2Δu,where Δu denotes the sensitivity of score function u and is defined as(7)Δu=maxr∈R⁡maxDΔD′=1⁡uD,r-uD′,r.The exponential mechanism can output nonnumerical results according to their values of score function. The output probability refers to privacy budget from the definition above, and the highest scored result is outputted with higher probability whenε is larger; meanwhile, when the difference between the output probabilities grows, the security becomes less; vice versa, the smaller ε is, the higher the security will be.


### 2.3. Combination Properties

Differential privacy has two important properties [44], as follows.Property 1 (sequential composition).
SetA1,A2,…,An satisfying differential privacy for ε1,ε2,…,εn; multiple mechanism A(A1,A2,…,An) satisfies ∑i=1nεi-differential privacy for the same dataset D.Sequential composition shows that privacy budget and error are cumulative linearly when we use multiple differential privacy to release data for the same dataset.Property 2 (parallel composition).
SetA1,A2,…,An satisfying differential privacy for ε1,ε2,…,εn; multiple mechanism A(A1,A2,…,An) satisfies max⁡εi-differential privacy for the different datasets D1,D2,…,Dn.Parallel composition shows that the degree of privacy guarantee depends on the value ofεi; when the value of εi grows, the security decreases gradually.These two properties play a major role in proving whether an algorithm satisfies differential privacy and judging whether the budgeting strategy is reasonable [4]. For instance, given an algorithm A with n-step, each step has budget εi(i=1,2,…,n); then the algorithm A satisfies ∑i=1nεi-differential privacy.Differential privacy has great advantages compared to traditional privacy protection model; however, there will be some sacrifice for utility of the data to satisfy differential privacy. From Definition2, the level of similarity in query result of neighboring datasets depends on the value of ε: the smaller ε is, the higher the level of similarity of query results becomes and the stronger privacy guarantee for raw data will become; at the same time, smaller ε leads to larger noise and poor data utility, and vice versa. In short, utility and security of data are a pair of contradictions, so the aim of privacy guarantee is to ensure very high level of privacy while simultaneously providing extremely accurate information about the database [13].In order to balance the security and the utility of the data, we need to consider how to meet the maximum number of queries using the smallest budget before exhaustingε or how to enhance the accuracy of query under giving ε. Existing methods usually use relative error [31], absolute error [31], variance [30, 38], standard deviation [31], and false negative [40] to evaluate the rationality of algorithm.


## 2.1. Base Definitions

Privacy is most often defined as the right to be left alone, free from intrusion or interruption. It is an umbrella term, encompassing elements such as physical privacy, communications privacy, and information privacy [22].Intuitionally, differential privacy ensures that the removal or addition of a single database tuple does not affect the outcome of any analysis [23]. The definition of differential privacy is as follows.Definition 1 (differential privacy [13]).
LetD and D′ be two neighboring datasets which differ on at most one tuple, denoted by d(D,D′)=1; given a randomized function A:D→R, Range(A) is the set of all possible outputs of A in D and D′, and given an arbitrary subset S⊆Range(A), A is said to be ε-differential privacy if (1)Pr⁡AD∈S≤exp⁡ε∗Pr⁡AD′∈S.The parameterε is called privacy budget, which is used to control the ratio of output of function A in neighboring datasets D and D′. The smaller ε is, the more close ratio is to 1; that is to say, the output probability distributions of function A in neighboring datasets D and D′ are approximately the same; meanwhile, the higher the security becomes, the lower the utility gets. The value of ε is small usually, such as 0.01, 0.1, 0.5, and 0.8.The strong privacy guarantee of differential privacy comes at the price of much noise added to the results of queries and analyses [21]. Dwork et al. further proposed enhancing the utility of data by reducing the requirements of data security; then (ε,δ)-differential privacy was proposed to this issue.Definition 2 ((ε,δ)-differential privacy [24, 25]).
LetD and D′ be two neighboring datasets which differ on at most one tuple, denoted by d(D,D′)=1; given a randomized function A:D→R, Range(A) is the set of all possible outputs of A in D and D′, and given an arbitrary subset S⊆Range(A), A is said to be (ε,δ)-differential privacy if(2)Pr⁡AD∈S≤exp⁡ε∗Pr⁡AD′∈S+δ.No hard rule dictates what value of privacy budgetε and δ should be and they can be set according to the actual application requirements. The value of δ is small usually (δ≤10-4) and (ε,δ)-differential privacy equals ε-differential privacy when δ=0.The output probabilities of randomized functionA in neighboring datasets D and D′ for ε-differential privacy are shown in Figure 1 [26, 27], where c≤|A(D)-A(D′)|; the larger c is, the wider the distribution will be and the higher the probability of adding more noise becomes.Figure 1
Output probabilities of randomized functionA in neighboring datasets D and D′.FunctionA provides privacy guarantee by adding random noise to the output; that is, A(D)=f(D)+noise, where f is such query operations as average, count, and sum and noise is the random noise following Laplace distribution which will be introduced in Section 2.2. The smaller the difference between two curves is, the stronger the security received is.A simple attack example is as follows: Table1 is a health dataset and provides count service f(x)=count(·) for querying the number of people suffering from HIV. Without privacy protection strategy, the adversary just needs to query the number of four people containing Alice with HIV which is Yes and the number of three people excluding Alice also with HIV is Yes; then the adversary obtains that Alice is suffering from HIV only by count(4)-count(3)=1. Obviously, practical application for health data release comes to failure if it fails to resist these attacks.Table 1
Health records.
Name
HIV (0 is No; 1 is Yes)
Address
Tim
0
New York
Bob
1
Washington
Tony
0
New York
Alice
1
Hawaii
⋮
⋮
⋮Now, we add a random noise to the output of count functionf and let two count results fall into the same range with higher probability; for example, count(3)={1,1.5,2} and count(4)={1,1.5,2}; by this time, the adversary fails to get Alice’s health information by the above method as both count(4) and count(3) may output 1.5 and count(4)-count(3)=0. Differential privacy gives the maximum capacity of the adversary in this instance; that is to say, the adversary knows statistics whether the Alice is present in the dataset or not.


## 2.2. Noise Mechanism

The two main noise mechanisms are Laplace mechanism and exponential mechanism, and the noise magnitude refers to privacy budget and global sensitivity.Definition 3 (global sensitivity [13]).
Given a randomized functionf:D→Rd, the global sensitivity of function f is(3)Δf=maxD,D′fD-fD′1,where D and D′ are two neighboring datasets, R is the real space of mapping, d is the dimension, and fD-fD′1 is the first-order norm distance between f(D) and f(D′) and is denoted by L1=fD-fD′1.The global sensitivity for count functionΔf=1; however, Δf is larger for other operations. For instance, given dataset D={1,1,1,1,21}, f is sum operation; then the global sensitivity Δf=21 is larger than the sensitivity of count function. So Nissim et al. first proposed the notion of local sensitivity to reduce the sensitivity magnitude as the noise will become large with the increasing of global sensitivity.Definition 4 (local sensitivity [41, 42]).
Given a randomized functionf:D→Rd, the local sensitivity LSf of function f is(4)LSf=maxD′⁡L1.For example, given the subsetD1={1,1,1,1} of D, the local sensitivity LSf=1 is smaller than the global sensitivity 21 under adding operation. Local sensitivity may reduce the noise magnitude, but noise magnitude might reveal information about the dataset; for details see [41, Example  1]. So Nissim et al. further proposed the notion of β-smooth sensitivity to avoid disclosing privacy information; now the added noise is proportional to a smooth upper bound on the local sensitivity.Definition 5 (smooth sensitivity [41]).
Forβ>0, given a randomized function f:D→Rd, the β-smooth sensitivity Sf,β(D) of function f is(5)Sf,βD=maxD′⁡LSfD′·e-βdD,D′.


### 2.2.1. Laplace Mechanism

The literature [42] proposed Laplace mechanism to achieve differential privacy by adding random noise drawn from the Laplace distribution to the output. Its definition is as follows.Definition 6 (Laplace mechanism).
Given a datasetD and the function f:D→Rd, global sensitivity is Δf; random algorithm A(D)=f(D)+noise satisfies ε-differential privacy if the noise obeys the Laplace distribution; that is, noise~Lap(Δf/ε); thereinto, location parameter is 0 and scale parameter is Δf/ε.
LetLap(b) denote the Laplace distribution when location parameter is 0 and scale parameter is b, and its probability density function is p(x)=exp(-|x|/b)/2b. From Figure 2, the larger the noise added to the output is, the larger b is and, meanwhile, the smaller ε becomes.
Letσ(x) denote standard deviation; D(x) denotes variance, and noise~Lap(b), σ(x)=D(x), D(x)=2b2, and b=Δf/ε; then we obtain the results D(x)=2(Δf/ε)2=2Δf2/ε2, σ(x)=D(x)=2Δf2/ε2=2Δf/ε.Figure 2
Probability density function.


### 2.2.2. Exponential Mechanism

Laplace mechanism is used when the output is numerical, and exponential mechanism is another security-controlled scheme to satisfy differential privacy when the outputs are nonnumerical.Intuitionally, exponential mechanism still ensures that the change of a single database tuple does not affect the outcome of the score function, and the definition is as follows.Definition 7 (exponential mechanism [43]).
LetD denote the input dataset; r∈R denotes a potential answer, given a score function u:D×R→R; if a random algorithm A selects an answer based on the following probability, then algorithm A is said to satisfy ε-differential privacy:(6)AD,u=r:∣Pr⁡r∈R∝exp⁡εuD,r2Δu,where Δu denotes the sensitivity of score function u and is defined as(7)Δu=maxr∈R⁡maxDΔD′=1⁡uD,r-uD′,r.The exponential mechanism can output nonnumerical results according to their values of score function. The output probability refers to privacy budget from the definition above, and the highest scored result is outputted with higher probability whenε is larger; meanwhile, when the difference between the output probabilities grows, the security becomes less; vice versa, the smaller ε is, the higher the security will be.


## 2.2.1. Laplace Mechanism

The literature [42] proposed Laplace mechanism to achieve differential privacy by adding random noise drawn from the Laplace distribution to the output. Its definition is as follows.Definition 6 (Laplace mechanism).
Given a datasetD and the function f:D→Rd, global sensitivity is Δf; random algorithm A(D)=f(D)+noise satisfies ε-differential privacy if the noise obeys the Laplace distribution; that is, noise~Lap(Δf/ε); thereinto, location parameter is 0 and scale parameter is Δf/ε.
LetLap(b) denote the Laplace distribution when location parameter is 0 and scale parameter is b, and its probability density function is p(x)=exp(-|x|/b)/2b. From Figure 2, the larger the noise added to the output is, the larger b is and, meanwhile, the smaller ε becomes.
Letσ(x) denote standard deviation; D(x) denotes variance, and noise~Lap(b), σ(x)=D(x), D(x)=2b2, and b=Δf/ε; then we obtain the results D(x)=2(Δf/ε)2=2Δf2/ε2, σ(x)=D(x)=2Δf2/ε2=2Δf/ε.Figure 2
Probability density function.


## 2.2.2. Exponential Mechanism

Laplace mechanism is used when the output is numerical, and exponential mechanism is another security-controlled scheme to satisfy differential privacy when the outputs are nonnumerical.Intuitionally, exponential mechanism still ensures that the change of a single database tuple does not affect the outcome of the score function, and the definition is as follows.Definition 7 (exponential mechanism [43]).
LetD denote the input dataset; r∈R denotes a potential answer, given a score function u:D×R→R; if a random algorithm A selects an answer based on the following probability, then algorithm A is said to satisfy ε-differential privacy:(6)AD,u=r:∣Pr⁡r∈R∝exp⁡εuD,r2Δu,where Δu denotes the sensitivity of score function u and is defined as(7)Δu=maxr∈R⁡maxDΔD′=1⁡uD,r-uD′,r.The exponential mechanism can output nonnumerical results according to their values of score function. The output probability refers to privacy budget from the definition above, and the highest scored result is outputted with higher probability whenε is larger; meanwhile, when the difference between the output probabilities grows, the security becomes less; vice versa, the smaller ε is, the higher the security will be.


## 2.3. Combination Properties

Differential privacy has two important properties [44], as follows.Property 1 (sequential composition).
SetA1,A2,…,An satisfying differential privacy for ε1,ε2,…,εn; multiple mechanism A(A1,A2,…,An) satisfies ∑i=1nεi-differential privacy for the same dataset D.Sequential composition shows that privacy budget and error are cumulative linearly when we use multiple differential privacy to release data for the same dataset.Property 2 (parallel composition).
SetA1,A2,…,An satisfying differential privacy for ε1,ε2,…,εn; multiple mechanism A(A1,A2,…,An) satisfies max⁡εi-differential privacy for the different datasets D1,D2,…,Dn.Parallel composition shows that the degree of privacy guarantee depends on the value ofεi; when the value of εi grows, the security decreases gradually.These two properties play a major role in proving whether an algorithm satisfies differential privacy and judging whether the budgeting strategy is reasonable [4]. For instance, given an algorithm A with n-step, each step has budget εi(i=1,2,…,n); then the algorithm A satisfies ∑i=1nεi-differential privacy.Differential privacy has great advantages compared to traditional privacy protection model; however, there will be some sacrifice for utility of the data to satisfy differential privacy. From Definition2, the level of similarity in query result of neighboring datasets depends on the value of ε: the smaller ε is, the higher the level of similarity of query results becomes and the stronger privacy guarantee for raw data will become; at the same time, smaller ε leads to larger noise and poor data utility, and vice versa. In short, utility and security of data are a pair of contradictions, so the aim of privacy guarantee is to ensure very high level of privacy while simultaneously providing extremely accurate information about the database [13].In order to balance the security and the utility of the data, we need to consider how to meet the maximum number of queries using the smallest budget before exhaustingε or how to enhance the accuracy of query under giving ε. Existing methods usually use relative error [31], absolute error [31], variance [30, 38], standard deviation [31], and false negative [40] to evaluate the rationality of algorithm.


## 3. Data Process Models and Release Strategies

There are two data process models of differential privacy, namely, noninteractive model and interactive model; the latter is also called online query model as data requester is only allowed to access the information through an interface provided by data owner. Similarly, noninteractive model is called offline query model as data requester can directly access the sanitized dataset released by data owner [20, 42].Interactive model is shown in Figure3; data owner provides a data query algorithm based on differential privacy, and data requester sends a query request; when the query algorithm receives the request, it gets the raw data from the original database and does sanitizing process of raw data; then the sanitized data is returned to the requester. In this model, query number is restricted by privacy budget ε; the more query number leads to smaller budget for each query if total budget ε is a constant and a larger noise is added to the query result; in the end, the query result becomes inutile. So how to design the query algorithm to provide the maximum number of queries under limited budget ε is the key to this model.Figure 3
Interactive model.Noninteractive model is shown in Figure4; data owner is a trusted curator and releases a sanitized dataset, and data requester sends a query request; when the sanitized dataset receives the request, the noisy result is returned to the requester. In this model, query number is unrestricted by privacy budget ε, so how to design the release algorithm with high efficiency to enhance the accuracy of query is the key to this model.Figure 4
Noninteractive model.Difference privacy research is based on the two above models and there are roughly three data release strategies as follows.Strategy 1 (see [45]).
NoiseLap(Δf/ε) is added to raw data D={x1,x2,…,xn} and gets noisy data D~, which can be further optimized by postprocessing, for example, least square method, to enhance the query accuracy by the optimized data D-; then D- is released. In this strategy, ε is usually uniform budgeting; its process is shown in Algorithm 1.Algorithm 1.
Input. Raw data D={x1,x2,…,xn}, privacy budget ε.
Output. Released data D-(1)
D~={x1+Lap(Δf/ε),x2+Lap(Δf/ε),…,xn+Lap(Δf/ε)}(2)
D-=postprocess(D~).Strategy 2 (see [45]).
First, the conversion and the compression, which usually can reduce the sensitivityΔf of the function f, are applied to obtain a synthetic data D-; for example, the graph is converted into tree structure; then noise is added to D- and noisy data D~ is gotten. In this strategy, ε is uniform budgeting; finally, D~ is released; the process of Strategy 2 is shown in Algorithm 2.Algorithm 2.
Input. Raw data D={x1,x2,…,xn}, privacy budget ε.
Output. Released data D~(1)
D-=postprocess(D)(2)
D~={x-1+Lap(Δf/ε),x-2+Lap(Δf/ε),…,x-n+Lap(Δf/ε)}.Strategy 3.
NoiseLapΔf/εi is added to raw data D={x1,x2,…,xn} and gets noisy data D~; note that ε is nonuniform budgeting; that is, εi≠εj; it uses the reasonable budgeting strategy to reduce the error of data query; the process of Strategy 3 is shown in Algorithm 3.Algorithm 3.
Input. Raw data D={x1,x2,…,xn}, privacy budget ε1,ε2,…,εn, εi≠εj.
Output. Released data D~(1)
D~={x1+Lap(Δf/ε1),x2+Lap(Δf/ε2),…,xn+Lap(Δf/εn)}.These three data release strategies can be used alone or in combination. For instance, given a data release method, Strategy3 is first used to allocate the budget reasonably; then Strategy 1 is used to further enhance the query accuracy by postprocessing.


## 4. Data Release Categories

How to ensure the level of privacy guarantee while simultaneously providing highly utility of the data is a real concern; therefore, many methods were proposed in this section, and we will give our categories of differential privacy.


### 4.1. Histogram Release

Histogram is constructed by splitting the input dataset into mutually disjoint subsets called buckets or bins depends on a set of attributes. Any access to the raw data is conducted through the differential privacy interface when users send data query, and the differential privacy histogram is used to answer the user’s queries; the process is shown in Figure5 [46].Figure 5
Different private histogram release.The most straightforward method is to add Laplace noise to each histogram bucket using privacy parameterε, and the noise is Lap(1/ε) as count function sensitivity Δf=1; this method is fit for unit length queries and short-range queries, and it will lead to larger query error under long-range (i.e., the number of bucket n is larger) queries according to noise variance formula 2n/ε2. In order to reduce the query error, multiple buckets are merged into one partition; now the number of tuples which fall into each partition is the average value of the number of tuples in these buckets, as shown in Figure 6.Figure 6
Example of buckets merger.The noisenoise is added to each bucket before the merger, and the total noise is 7noise; after merge operation, the total noise becomes 3noise, which is smaller than the value before the merger. However, merge operation introduces an approximation error as the number of tuples in the partition is the average value of the number of tuples in multiple buckets.We need to make the least possible number of partitions to reduce the noise error and make the number of tuples of buckets in a partition the same as much as possible to reduce the approximation error. In general, a finer-grained partitioning will introduce smaller approximation error but larger noise error, so finding the right balance between approximation error and noise error is a key question [46].Xiao et al. [29, 46] proposed a partitioning strategy based on the kd-tree. It seeks to merge buckets which are close to uniform into a partition using a variance-like metric U(p0), which is defined as U(p0)=∑ci∈P0x(ci)-a0, where p0 is the current partition, ci is the each bucket in p0, x(ci) is the number of tuples in ci, and a0 is the average value of buckets in p0. If U(p0)>T, where T is a giving threshold, then current partition p0 is split into two partitions according to the split median of all the numbers of buckets in p0. The process repeats until the whole domain is split into several partitions and each partition is close to uniform.The process ofkd-tree based histogram release is as follows. First, the original histogram is constructed according to the kth different attributes of raw data and the noise is added to original histogram using privacy budget ε/2 to generate a noisy k-dimensional dataset. Next, the noisy k-dimensional dataset is partitioned by kd-tree algorithm according to U(P0), getting final partitions. Then, the noise is added to each partition using the remaining privacy budget ε/2. Finally, the noisy histogram is released. The property of the algorithm is decided by the parameter U(p0) and the tree depth when partitioning or the number of tuples in each partition. kd-tree based histogram release algorithm is further used in health information DE-identification in Xiao et al.’s subsequent research and is named DPCube, which is based on Strategy 1 and kd-tree is used for postprocessing after adding noise. DPCube supports multidimensional data, long-range query and query error may be lower if the value of parameters selected properly.In view of the right balance between the appropriation error and the noise error, Xu et al. [15] proposed the notion of Sum of Squared Error (SSE) in order to reduce the appropriation error and enhance the data query accuracy. SSE is defined as follows: SSE(H,D)=∑j∑lj≤i≤rjxoptj-xi2, D={x1,x2,…,xn} is a series of counts of original histogram and xi is the count of each bucket, H={p1,p2,…,pk} represents the partitioned histogram which merges neighboring counts into k partitions and pj is the partition of the histogram, which contains an interval [lj,rj]⊆[1,n], and xoptj is the optimal value for pj and is generally computed by the mean value of the counts in [lj,rj]; that is, xoptj=∑i=ljrjxi/(rj-lj+1).Two algorithms NoiseFirst and StructureFirst are proposed dependent on SSE to measure the error between the histogramH and the original count data D. Strategy 1 based NoiseFirst constructs the optimal histogram adopting by dynamic programming method after adding noise and is fit for short-range query; Strategy 2 based StructureFirst generates the optimal histogram based on the original count sequence, which has the risk of privacy disclosure. StructureFirst first uses partly privacy budget ε1 to guarantee the sensitive information in the histogram; then, the noise is added to the partitions using remaining privacy budget (ε-ε1), and StructureFirst is fit for long-range query. StructureFirst and DPCube proposed by Xiao et al. are very similar; the maximal difference is that the two steps in DPCube separately allocated privacy budget ε/2, that is, uniform budgeting, while StructureFirst is a near-optimal budgeting strategy. The two above methods need to reconstruct the histogram; that is, the original histogram is reconstructed, and the number of partitions k is the key factor that affects the algorithm’s performance.In order to reduce the error in long-range query, Hay et al. [47] proposed optimizing histogram by hierarchical tree structure. Histogram is transformed into hierarchical tree structure; then one can arrange all queried intervals into a tree, where the unit-length intervals are the leaves [48], and the query accuracy is enhanced by the consistency check between each layer node of the tree.In view of the hierarchical method for optimizing histogram, Qardaji et al. [48] researched the factors which affect the mean squared error (MSE) of range query under the consistency check and different budgeting strategies. The hierarchical method in one dimension can reduce MSE when branching factor is more than 4; however, the hierarchical method fails to adapt multidimensional histogram when the dimensionality is greater than or equal to 3. The noise is directly added to each unit bucket in the histogram, which is called the Flat method by Qardaji et al., and Flat outweighs the hierarchical method. Detailed analysis of histogram release methods is shown in Table 2.Table 2
Histogram release methods.
Method name
Strategy
Advantage
Defect
Budgeting
DPCube
Strategy1
Supports multidimensional and long-range query
Parameter affects query accuracy heavily
Uniform budgeting
NoiseFirst
Strategy1
Fit for short-range query
Histogram reconstruction is expensive
Uniform budgeting
Structure First
Strategy2
Fit for long-range query
Histogram reconstruction is expensive
Near-optimal budgeting
Flat
Strategy1
Fit for multidimensional data
Low-dimensional data query error is larger
Uniform budgetingIn a word, methods based on histogram release usually need to reconstruct the original histogram; when the number of partitionsk grows, the approximation error gets less, but the noise error becomes larger; meanwhile, it will enlarge the time cost and make its application restricted. For instance, the time complexity of StructureFirst is O(kN2), k=O(N); the value of k affects the time cost, so how to improve the efficiency of the algorithm and reduce the approximation error especially when data dimensionality is larger is one research direction of histogram. Moreover, many algorithms adopt uniform budgeting, and how to allocate the privacy parameter ε based on the requirements of application to enhance the query accuracy is another research direction. Note that Li et al. [49] first proposed DPSynthesizer, an open source visual toolkit for differentially private histogram data release, which can make the user see the one-dimensional or multidimensional differential privacy histogram data directly in terms of graph.


### 4.2. Tree Structure Release

In order to seek differential privacy budgeting strategy and reduce the query error, a series of methods based on tree-structure data split were proposed, and they are known as private spatial decompositions which divide the geospatial data into smaller regions and obtain statistics on the points within each region [30]. If the partition discloses the sensitive information during spatial decomposition, it is called data-dependent decomposition; otherwise, it is called data-independent decomposition. For instance, kd-tree is recursively split through the median data value, which discloses the median value itself, so it is called data-dependent decomposition.(1) Data-Dependent Decomposition. As shown in Figure 7, node 5,4 discloses itself during splitting; in order to mask the real information, the noise is added to the node. Let D={x1,…,xn}, xi∈[l,r]; the data in D is sorted in ascending order and xm is the median value; then the noisenoise is added; that is, M(D)=xm+noise, noise~Lap(Δf/ε); however, the noise median M(D) may go beyond the range of the data D; that is, M(D)∉[l,r]; as for this issue, Inan et al. [50, 51] proposed to adopt the mean instead of the median for numerical data, and the mean can be approximated as the ratio of the sum of noisy counts to the number of the counts, but this method fails to ensure the degree of approximation between the mean and the median.Figure 7
Example of privatekd-tree.As for indexing structure based onkd-tree, Xiao et al. [29, 46] first use privacy budget ε/2 for original data and then construct kd-tree and compute the median by noisy data, finally guaranteeing the privacy of the median.Cormode et al. [30] proposed EM method to judge the median according to exponential mechanism among the kd-tree; EM returns x with Pr[EM(D)=x]∝e-ε|rank(x)-rank(xm)|/2, and rank(x) represents the rank of x in data D. Since the value x is approximately equal to the median xm, the median is guaranteed. After the selection, using privacy budget εmedian for xm, using privacy budget εcount for count computation, and ε=εmedian+εcount, a consideration is that larger value of εmedian leads to more accurate median, but larger count error, while smaller value of εmedian generates more accurate count computation, but larger median error, so how to allocate the budget ε for the count computation and the median computation and balance the errors on the count error and the median error is a concern. The above algorithm based on kd-tree and EM medians is called kd-standard.(2) Data-Independent Decomposition. Cormode et al. [30] proposed the algorithm Quad-opt based on quadtree, which recursively divides the data space into equal quadrants, does not disclosure data information, and belongs to data-independent decomposition. As shown in Figure 8, the data a is divided into four quadrants bi, i∈[1,4], and bi would continue to divide until the predefined tree depth h is reached; h begins with 0. Compared to classical uniform budgeting, that is εi=ε/(h+1), Cormode proposed a novel geometrical budgeting strategy (by a factor of 23), which allocates εi for each level of the tree, thereto, εi=2(h-i)/3ε(23-1)/(2(h+1)/3-1), i=[0,h], ∑i=0hεi=ε; then the least upper bound of error in query Q satisfies ErrQ=Var(Q)≤2h+7/ε2; the query error is the sum of the nodes contained in Q variances. Quad-opt can handle the noisy data through the least square method during postprocessing and further enhance the query accuracy. For example, if the node a’s budget is ε1 and its children’s budget is ε2, in order to optimize the query error Err(Q) when querying the noisy count in node a, we should let Q(a)=(4ε12/4ε12+ε02)x~a+(ε02/(4ε12+ε02))∑i=14x~bi, where x~a is the noisy count in node a itself and x~bi is the noisy count of four children; then Err(Q(a))=Var(Q(a))=8/4ε12+ε02<2/ε12=Var(x~a).Figure 8
Example of private quadtree: the numbers are the actual counts.If allocating all privacy budget to the leaf nodes, the algorithm is equivalent to directly dividing the data space intow×w cells. When the data is very sparse, adding noise to each cell will lead to poor information remaining; inspired by it, Fan et al. [32] proposed Spatial Estimation Algorithm (SEA), which merges similar cells into one group or partition to rise above the sparsity of the data. SEA first models different types of cells dependent on the domain knowledge before split; that is, each cell is sparse or dense, and the partition is called homogeneous if all the cells contained in this partition belong to the same category and need not to split; on the contrary, it is necessary to split until the partition is homogeneous or reaches the predefined tree depth. Then the noisenoise is added to each partition pi after the data splitting has completed, and the cell noise is noise/pi.size(), where pi.size() is the number of cells in the partition pi. Finally, SEA enhances the query accuracy while simultaneously providing very high level privacy guarantee by cells merge operation, essentially by reducing the added noise for cells.The partition based on quadtree orkd-tree is fit for one-dimensional or two-dimensional data; as for multiple-dimensional data, Qardaji et al. [31] proposed method UG based on uniform grid which can be seen as an n-tree especially. There are two sources of error in the grid method: one is noise error introduced by adding random noise followed Laplace distribution; another is nonuniformity error introduced by assuming that the data points are distributed uniformly and nonuniformity error is proportional to the number of data points in the cells that fall on the border of the query rectangle [31]; then the query error Err(Q) refers to the two errors above.UG splits the space data intow×w cells; given a query Q, the query error Err(Q)=2rw/ε+rN/wc0, where N is the number of data points, r is the ratio of the area of the query Q to the area of the whole domain, and c0 is a constant. Note that UG gives the granularity w of the partition, which is the key factor effecting the accuracy of query results, and w is about Nε/c, (c=2c0).UG treats all cells equally whether sparse cells or density cells. When the cell is very sparse, the noise error is too large; on the other hand, when the cell is very dense, the nonuniformity error is too large. Qardaji et al. further proposed the adaptive grids method AG to balance the two errors: when a region is sparse, a finer granularity is needed to reduce the noise error; when a region is dense, a coarse granularity is used to reduce the nonuniformity error.AG first splits the space data intow1×w1 coarse cells. If a cell ci is too dense, ci can be further split into w2×w2 finer cells, and then issuing a count query for each coarse cell and finer cell using privacy budget aε and (1-a)ε is carried out. In order to optimize the data query error, let w1=max10,0.25Nε/c, w2=2x~i(1-α)ε/2c0, where x~i is the noisy count in cell ci. However, UG and AG also lack the adaptive judging criterion whether the cell is sparse or dense. At the same time, it is assumed that the nonuniformity error is proportional to the number of data points in the cells. In this model, the query rectangle is just square, which is not so consistent with the fact because the shape of query may be rectangular, and the query results are influenced severely by the selection of c0. Detailed analysis of tree structure release methods is shown in Table 3.Table 3
Tree structure release methods.
Method name
Strategy
Advantage
Defect
Budgeting
Quad-opt
Strategies2 and 3
Computational efficiency is high; support any range query
Error is large
Geometric budgeting
SEA
Strategy2
Noise error is small
Approximate error is large
Uniform budgeting
k
d-standard
Strategy2
Query accuracy is high
Only fit for low-dimensional data
Median and count use privacy budget together
UG
Strategy1
Support any range query
Neglects the balance between noise error and nonuniformity error
Uniform budgeting
AG
Strategy1
Balance the noise error and the nonuniformity error
Lack of the adaptive judging criterion
Uniform budgetingIn conclusion, there is no privacy risk for tree structure in the data-independent decomposition, but how to reduce the noise error is the key for our special research. In Fan et al.’s data category, there are only sparse data and dense data, and the partition of data category is too coarse, so how to partition the data category based on the variance or information entropy to enhance the query accuracy is one of the research directions in the future. In data-dependent decomposition, some privacy budget is needed to guarantee the privacy forkd-tree itself disclosing the median information; thus, how to balance the allocation of the privacy budget to raise the query accuracy is one of the research directions in the future.


### 4.3. Time Series Release

There are many differential privacy real time data release, such as MHR, GPS, and track. The real time data with higher correlation between time stamps has a timescale, if the length of the time series isT and the noise noiset is added to the data xt at time k, noise~Lap(T/ε), when T is large, the added noise gets large and leads to poor utility of the data.As for time series data, in order to reduce the error, Rastogi and Nath [52] proposed algorithm DFTk based on discrete Fourier transform. For time series D, DFTk first executes the discrete Fourier transform, that is, F=DFT(D), and retains only the first k DEF coefficients; then the Laplace noise is added to those coefficients and the inverse Fourier transform is executed on the noisy coefficients F~, that is D~=IDET(F~). Finally, the perturbed data D~ is released. However, the algorithm DFTk needs to execute the DET() and IDET() operations with the full series, and it is not compatible to real time applications [32].As for real time traffic monitoring data, in order to raise the execution efficiency and query accuracy of the algorithm in the real time environment, Fan et al. [32] proposed Temporal Estimation Algorithm (TEA) based on the time series model. Given the space G, TEA first splits the space into w×w cells and the time span T is discretized into time index, where 0≤k<T. The frequency series Dc of cell c is {xkc∣0≤k<T}, where xkc is the frequency series of c at time stamp k and all frequency series DG in G are {Dc∣c∈G}. Then, the model is constructed dependent on domain knowledge, such as locations, population, and road networks; for each cell c, the process model is xk+1c=xkc+ωc, p(ωc)~N(0,Qc), where Qc represents the degree of variation between neighbor time stamps, and the noise is added to the frequency series of c at time stamp k; that is, x~kc=xkc+noise, noise~Lap(0,1/ε0), where ε0=ε/T and ε is uniform budgeting for the time span T. For estimation purpose, noise is replaced by white Gaussian noise; that is, noise~N(0,R). Finally, the noisy data D~G is released. TEA utilizes the time series model and the educated guess to enhance the query accuracy; meanwhile, the computing complexity is low and time complexity is O(kw2), where k=O(1).For the time spanT, if a real time system has higher sampling rate, larger noise will be introduced to satisfy the differential privacy; on the contrary, the approximate error is larger if the system is with lower sampling rate, so how to select the value of sampling rate is the key. Fan et al. proposed an adaptive sampling algorithm FAST [33, 34] to solve the problem in the subsequent research. FAST can adjust the sampling rate F automatically according to data dynamic and F≤T; the sampling rate is increased when the data changed rapidly and vice versa. The dynamic of current data can be described by the feedback error Ekn, which is defined as |x^kn-x^kn-|/max{x^kn,δ}, where x^kn and x^kn- are the posterior estimate and the prior state estimate for nth (0≤n<F) sampling point at time step kn (0≤kn<T) and δ is a parameter assigned by user and generally δ=1. Because of the data, the sampling frequency is not fixed; in order to achieve the optimal sampling rate in minimal time, FAST uses the PID controller to adjust the rate. Firstly, PID algorithm takes Ekn as the input and gets the output Δ, that is, the PID error, which is defined as follows: Δ=CpEkn+(Ci/Ti)∑j=n-Ti+1nEkj+Cd((Ekn-Ekn-1)/(kn-kn-1)), where Cp, Ci, and Cd are the proportional, integral, and derivative components of PID; then the new sampling rate I′ is max{1,I+θ(1-e(Δ-ξ)/ξ)}, where θ and ξ are parameters specified by user. The adaptive sampling algorithm FAST reduces the noise error from Θ(T) to Θ(F).As for web browsing behavior data, utilizing the rich correlation of the time series, Fan et al. proposed session-level differentially privacy algorithm U-KF [35] based on the user-level framework FAST. U-KF releases the differential privacy aggregates using state-space model in real time and adopts Kalman filter [53] during postprocessing. Given original data {xki,i=1,…,m}, where xki represents the number of sessions browsing pagei at time k. Firstly, in the prediction step, the prior estimate x^ki- is derived from the previous posterior estimate xk-1i, where “^” represents state estimates and the superscript “−” represents variables related to the prior estimate [35]. Then, computing the perturbed value x~ki, that is x~ki=xki+noiseki, noiseki~Lap(0,lmax/ε), where lmax is the query sensitivity. Next, in the correction step, the posterior estimate x^ki is computed according to the perturbed value x~ki and the prior estimate x^ki-, that is, x^ki=x^ki-+Kki(x~ki-x^ki-), where Kki is the Kalman gain [53]. Finally, {x^ki,i=1,…,m} is released. U-KF is a univariate time series algorithm with higher query accuracy and its computing time is proportional to the number of web pages, that is, O(m); however, U-KF only supports the browsing request in the single server, failing to support the request in different servers. Detailed analysis of time series release methods is shown in Table 4.Table 4
Time series release methods.
Method name
Strategy
Advantage
Defect
Budgeting
D
F
T
k
Strategy2
Supports long-range query
Parameter affects query accuracy
Uniform budgeting
TEA
Strategies1 and 2
Computing complexity is low; query accuracy is high
Affected by data type
Uniform budgeting
FAST
Strategies1 and 2
Query accuracy is high; adaptive data changes
Add the cost of feedback control
Uniform budgeting
U-KF
Strategy2
Computing complexity is low; query accuracy is high
Only supports requests in signal server
Uniform budgetingAs for record data, in order to enhance the query accuracy, Xiao et al. [54, 55] proposed Privelet method based on wavelet transform. Privelet does not directly perturb the frequent matrix M of input data, but first transforms the M into the wavelet coefficient matrix C, which is perturbed by Laplace noise; then the noisy coefficient matrix is mapped into noisy frequent matrix M~; finally, M~ is released. It is known then that the differential privacy based on wavelet transform is feasible. As for real time data, such as smart meter, Ferrández-Pastor et al. [56] indicated that using wavelet transform to analyze the behavior of user is feasible, so the time series release combined with wavelet transform is one of the research directions in the future. At the same time, how to split the time span T is the key of time series release methods; the partition granularity of T should be approximate, combined with the features of data, such as the stepped data; how to adaptively spit the data is also one of the research directions in the future for time series.


### 4.4. Graph Release

Nowadays, digital health social network often contains user’s sensitive information, and directly releasing these network data may harm individual privacy, so the network data should be sanitized before the release. Network data is different from general data, and it will be highly sensitive to small changes as the clustering coefficient is larger according to graph theory. For instance, adding random noise to a subgraph counting query for purpose of masking the presence or not of an edge, and larger noise implies poorer utility of the data. In order to enhance the utility of the sanitized data, a series of methods were proposed.Hay et al. [57] first proposed edge differential privacy for networks data or differential privacy for short. Given graphs G1=(V1,E1) and G2=(V2,E2), V1 and V2 are the set of vertices of graphs G1 and G2; E1 and E2 are the set of edges of graph G1 and G2; if V1=V2, E1=E2, and |E1|+1=|E2|, then G1 and G2 are neighbors which are denoted by |G1ΔG2|=1.Definition 8 (edge differential privacy [57]).
LetG1 and G2 be two neighboring datasets which differ on at most one edge, denoted by |G1ΔG2|=1; given a randomized function A:D→R, Range(A) is the set of all possible outputs of A in G1 and G2, and given an arbitrary subset S⊆Range(A), A is said to be ε-edge differential privacy or ε-differential privacy if(8)Pr⁡AD∈S≤exp⁡ε∗Pr⁡AD′∈S.Similarly, edge differential privacy can be expanded to multiple edges; if neighboring datasets differ onk edges, that is, |G1ΔG2|=k, then function A is said to be ε-k edge differential privacy. Furthermore, if neighboring datasets which differ up to all edges connected to one single node, that is, |G1ΔG2|=∀|k|, (ki∈v), then A is said to be ε-node differential privacy, which is the ultimate aim desirable to achieve; however, it will introduce excessive noise and cause the worst utility of the data, in subsequent sections, A satisfies ε-edge differential privacy as the privacy standard.In order to raise the utility of graph under the requested level of privacy, the graph’s structure is needed to be captured first; then it would be converted back into a synthetic graph desired to be the same with original graph after adding noise. Sala et al. [58] proposed Pygmalion method, which captures the graph’s structure according to dK-series graph model [59].d
K can capture the graph’s structure into statistical number called dK-series, which is the number of nodes at different degree distribution for d-node subgraphs. As shown in Figure 9, when d=1, the distribution is the node degree distribution; when d=2, the distribution is the joint degree distribution for 2-node subgraphs; then using a matching generator, a synthetic graph is generated from the dK-series.Figure 9
Example ofdK-series.Pygmalion first captures thedK-series from the original graph and then sorts the dK-series and clusters the dK-series to get a set of subseries. Next, each subseries is perturbed by random noise according to local sensitivity. Finally, a synthetic graph is generated from the perturbed dK-series. However, local sensitivity might reveal sensitive information although it reduces the noise magnitude.Wang and Wu [36] also used dK-series graph model to capture the graph’s structure, in order to strictly achieve differential privacy and avoid revealing the privacy, and adopted the smooth sensitivity. For 2K-graph, Wang and Wu proposed a method DP2K(ε), which satisfies (ε,δ)-differential privacy. DP2K(ε) first uses the parameter (ε,δ) to compute the value of (β,α), where α=ε/2, β=ε/2ln⁡(2/δ), and then obtains the β-smooth sensitivity Sf,β(G) according to β and the sensitivity LSf(G); next, it uses Sf,β(G) to get the random noise which is added to the 2K-graph series; finally, a new graph is generated by perturbed series.Wang et al. [37] proposed another method, that is, LNPP, which uses spectral graph to guarantee the graph data. Spectral graph analysis mainly applies the graph’s adjacent matrix to construct the graph’s topological structure. For example, the adjacent matrix An×n represents the graph G, where Ai×j=1 if there is an edge between nodes i and j; Ai×j=0 if not. LNPP first decomposes matrix A and gets eigenvalues and eigenvectors; then, these values are perturbed based on Laplace mechanism, and the output eigenvectors are postprocessed by the vector orthogonalization technique [60] as the perturbed eigenvectors are no longer orthogonormal [37].Adopting the spectral graph and thedK-graph model to guarantee privacy, the noise introduced by the former is proportional to O(n), and the latter’s sensitivity is O(n), where n is the number of vertices in the input graph. In order to raise the utility of the data, Xiao et al. [38] proposed a novel method hrg-ε1-e-ε2, which is based on hierarchical random graph (HRG) model to reduce the perturbed noise magnitude.Classical graph model is construed by considering the observed edges, and HRG uses the connection probabilities between vertices. In the HRG model, graphG can be represented by a hierarchical structure and the connection probabilities. The hierarchical structure of G is a rooted binary tree which has n leaf nodes corresponding to the n vertices of G [38]. Each internal node r has a probability pr, and any two vertices i and j of G, their connection probability pi,j=pr, pr=er/nLr∗nRr, where r is two vertices’ lowest common ancestor in T, Rr and Lr are the right and left subtrees of internal node r, nLr and nRr are the numbers of leaf nodes in left and right subtrees, and er is the number of edges in G whose endpoints are leaves of the two subtrees of r in T [38]. So, the hierarchical random graph can be defined as (T,{pr}). As shown in Figure 10, original graph G can be represented by dendrogram T1 and dendrogram T2.Figure 10
Example of the HRG model.
(a)
Original graphG
(b)
DendrogramT1
(c)
DendrogramT2For graphG, in order to select a good dendrogram from numerous candidates, the notion likelihood is proposed to estimate how to represent G exactly by the selected dendrogram; that is, L(T,{pr})=∏r∈Tpprer(1-pr)nLr∗nRr-er. In the above instance, firstly, the set of {pr} is calculated for each dendrogram; then the likelihoods of two dendrograms are computed; that is, L(T1)≈0.00165 and L(T2)≈0433; finally, L(T1) is compared to L(T2); one can see that T2 is more exact to represent the original graph as L(T2) is larger.In hrg-ε1-e-ε2, privacy budget ε is divided into two parts; firstly, exponential mechanism is used; a Markov chain Monte Carlo procedure is designed to select a good dendrogram Tsample, in which only one probability would be affected with a single edge change. This step consumes privacy budget, that is, ε1 and score function is log⁡L(T,{pr})=-∑r∈TnLrnRrh(pr), where h(pr)=-prlog⁡pr-1-prlog⁡(1-pr); then, Laplace mechanism is adopted; the set of {pr} of Tsample is perturbed using remaining budget ε2; finally, the sanitized graph G~ is reconstructed by HRG model and is released. The global sensitivity of hrg-ε1-e-ε2 is O(log⁡n) and reduces the added noise magnitude. Detailed analysis of graph release methods is shown in Table 5.Table 5
Time series release methods.
Method name
Strategy
Advantage
Defect
Budgeting
Pygmalion
Strategy2
Reducing the noise by subsection
Having the risk of privacy disclosure using local sensitivity
Uniform budgeting
DP2K(ε)
Strategy2
Guaranteeing the privacy by smooth sensitivity
Noise is large
Uniform budgeting
LNPP
Strategies1 and 2
Enhancing the utility by postprocessing
Noise is large
Uniform budgeting
hrg-ε1-e-ε2
Strategy2
Utility of the data is high
Result affected by different budgeting strategies
Sampling and perturbation use privacy budget togetherTo sum up, directly adding noise to graph will lead to poor utility of the data as high sensitivity of graph, and it requires to project the data to other data types, such as spectral domain,dK-series, and connection probabilities; therefore, how to select a good data type with a lower sensitivity is one of the research directions in the future.


### 4.5. Pattern Mining Release

Frequent pattern is a subset of items and is frequently present in dataset, such as item-set, subsequence, and substructure, and it is the basis of mining tasks, that is, classification, clustering, and so forth. However, it may reveal individual’s privacy during frequent pattern mining, so how to identify the useful patterns in the data while simultaneously guarantee user’s privacy is a new research direction of data mining.Frequent pattern mining algorithm is usually measured by support degree [28, 39, 40], occurrence [61], and stay point [62, 63], given data D={tran1,tran2,…,trann}, trani∈T, where T is the transaction set constituted by all transactions, and each transaction contains some items; that is, trani={item1,item2,…,itemm}, itemm∈I, where I is the item space constituted by all items and itemset itemsetj is the subset of item space I. if transaction trann contains itemset itemsetj, we say that trann supports itemsetj, and the ratio of the number of transactions supporting itemsetj to the total number of transactions is the support degree for itemsetj. Then, it could be said that itemsetj is a frequent itemset if the support degree is more than the giving threshold.In terms of personal location information, in order to mine the useful pattern, for example, people’s interesting geographic location, Ho and Ruan [62] proposed BuildDPQuadTree method based on quadtree and density-based clustering algorithm (DBSCAN). How to define the interesting region when we query the location history database is the focus, and the notion of stay point is proposed. Given the trajectory data trajiki={x1,x2,…,xki}, xj=(Latj,Lonj,tj), where tj is a timestamp, Latj is the latitude, and Lonj is the longitude. If a trajectory stays in a circle region with a ρ radius for at least a time period ΔT, the center (Lat,Lon) of the circle is a stay point; given a set of trajectories TJ={traj1k1,traj2k2,…,trajsks}, the region is called interesting location if it has more than r stay points in it.BuildDPQuadTree first recursively divides the data spaceG into small regions, given stay point set S, threshold Tthreshold, and privacy budget εqt; if |S|+Lap(3Tthreshold/εqt)≤3Tthreshold, stop partition and go to partition if not. After getting the set of spatial partitions, each cluster Gj, which is the set of stay points of the form (Latj,Lonj), is obtained by density-based spatial clustering of application with noise clustering method [64]. Given the threshold r, privacy budget εcg, and εcts, if |Gj|+Lap(Δfctsj/εcts)≥r, where Δfctsj=maxi∈D⁡#{s∈Gj∣sisastaypointforindividuali} and D is the set of all the individuals who have records in the cluster Gj [62], then Gj is called interesting region, and its center location is defined as [∑k=1|Gj|(Latk,Lonk)]/|Gj|+Lap(Δfcgj/εcts), where Δfcgj=max⁡length(pointx,pointy)/2, pointi∈Gj, and ε=∑i=1hεqt+εcg+εcts, where h is the quadtree depth. BuildDPQuadTree provides a novel method identifying the interesting region by stay point; however, its noise magnitude is easily affected by threshold Tthreshold. In the Ho and Ruan’s subsequent research, the algorithm DP-ILD [63] adopting β-smooth sensitivity was proposed and it satisfies (ε,δ)-differential privacy.The sensitivity of itemset query depends on the dimensionality of itemset during Top-k frequent pattern mining. In order to reduce the sensitivity, the data usually is projected into a lower dimensional space. Li et al. [39] proposed PrivBasis method to search Top-k frequent patterns. In the initialization step, PrivBasis tries to reduce the search space by finding the minimal sets of items IB, which contains the top k frequent itemsets [39]; then the supports of all subsets of IB are derived by applying binary itemset support counting [65]; however, the final frequent patterns may be imprecise.In order to raise the utility of the data, Lee and Clifton [40] proposed the NoiseCut method based on the sparse vector technique and FP-tree. NoiseCut first identifies all frequent itemsets L; in this step, sparse vector technique is adopted to reduce consumption of privacy budget, that is, given a noisy threshold τ^ and a count query q, which only pays privacy budget if q(D)+Lap(2k/ε)≥τ^, where τ^=σk+Lap(·), σk is the support of the kth most frequent itemset. It is noted that NoiseCut regards the itemset as frequent if its noisy support (τ+α) is bigger than τ^. Then the noisy FP-tree is built according to L, and the supports of itemsets and Top-k frequent itemsets can be derived from the FP-tree. In NoiseCut, given an itemset whose support is τ+α, its false negative is exp(-αε/2)(αε/2+2)/4; the smaller the false negative is, the higher obtaining correct frequent patterns becomes.As for graph data, Shen and Yu [28] proposed frequent graph pattern mining method Diff-FPM based on Markov chain Monte Carlo random walk technology. Diff-FPM obtains the Top-k frequent subgraph mainly according to random walk; then, the real counts of subgraphs are perturbed by Laplace random noise. The key to Diff-FPM is whether random walk can reach steady state or not. Diff-FPM satisfies ε-differential privacy if steady state is reached; if not, Diff-FPM only satisfies (ε,δ)-differential privacy, in which the security of the data maybe is affected.As for sequential data, such as DNA sequences and trajectories, Luca and Li [61] indicated that there are some disadvantages using support to mine frequent sequential patterns; for example, one pattern may fail to be regarded as frequent pattern if it repetitively occurs in the same transaction, which may issue in a loss of information patterns. In addition, patterns are represented as a subset of an universe of items and may not well describe the sequentiality of important events in reality [61]. In order to successfully mine the frequent sequential patterns from the sequential data, Bonomi et al. proposed the notion of occurrence which can identify repetitive patterns as frequent. Given a pattern p=a0a1⋯an-1, ai∈Σ, and a string x=x0x1⋯xm-1, if there is an integer i(0≤i≤m-n) making xi+j=aj, j=0,…,n-1, it says that the pattern p presents in position i of the string x, and fx(p) represents all number of occurrences of p in x. Given the dataset D={x0,x1,…,xN-1}, FD(p)=∑i=0N-1fxi(p) denotes the number of occurrences of the p in D, and p is called frequent sequential pattern if FD(p) is larger than the giving threshold. Note that adding or removing one string x in the dataset D may affect the count of a pattern up to O(|x|) and lead to higher sensitivity; in order to reduce the sensitivity, it usually uses a prefix tree structure [66, 67] to split the input data and uses the frequency of the prefixes instead of the frequency of the patterns [61]. Detailed analysis of pattern mining release methods is shown in Table 6.Table 6
Pattern mining release methods.
Method name
Strategy
Advantage
Defect
Budgeting
BuildDPQuadTree
Strategy2
Identify the interesting location using stay point
Noise is large
Partition and cluster use the privacy budget together
DP-ILD
Strategy2
Utility of the data is high
Only supports offline data
Uniform budgeting
PrivBasis
Strategy2
Mining speed is fast
The final frequent patterns may be imprecise
Uniform budgeting
NoiseCut
Strategies1 and 2
Utility of the data is high
Results are affected by different budgeting strategies
Privacy budget is allocated for two steps of the algorithm
Diff-FPM
Strategy2
Query accuracy is high
The drop in utility with the increase of the number of outputs [28]
Sampling and perturbation use the privacy budget togetherLuca and Li pointed out the existing differently privacy frequent pattern mining methods mainly based on the exact data; however, the real data usually are noisy, and some patterns may be lost [61]. There are less research about how to mine the frequent patterns in the noisy data, which is a future research direction. At the same time, how to raise the utility of the data while simultaneously providing privacy guarantee is an issue for further research.For different data types, related researchers proposed a series of differential privacy data release methods, and the methods summarized in this paper only are a part of the whole; there are many methods which the paper fails to describe, such as batch query methods based on matrix [68–70] and data release methods based on machine learning [71].


### 4.6. Discussion

Data release methods under different strategies are the main research contents for differential privacy and are the theoretical basis for practical applications. Classification and comparison of the differential privacy data release methods are shown in Table7, from which we can see that there are few research achievements in this new research area, and there still exists many urgent issues to be addressed and some new study directions to be explored.Table 7
Classification and comparison of differential privacy data release methods.
Classification
Advantage
Defect
Representative methods
Typical Applications
Histogram
Supports any range query
The noise is large in high-dimensional data
DPCube [29]NoiseFirst [15] Structure First [15]
Statistical analysis of disease and search history
Tree structure
Supports multiple- dimensional data and data-dependent or data-independent query
The noise is large in high-dimensional data
Quad-opt [30]AG [31]SEA [32]
Location query of user and device, transport planning
Time series
Supports time series query
It is hard to balance the utility and security in high-dimensional data
TEA [32]FAST [33, 34]U-KF [35]
Real time traffic, disease surveillance
Graph
Supports the analysis and query of graph data
Sensitivity is high, and node-differential privacy is difficult to achieve
DP2K(ε) [36]LNPP [37]hrg-ε1-e-ε2 [38]
Relationship analysis of user in health social network
Pattern mining
Supports differential privacy pattern mining, and original data can be constructed by frequent patterns
Long pattern leads to large noise
PrivBasis [39]NoiseCut [40]Diff-FPM [28]
User behavior, DNA sequences, trajectory and disease trend analysis, recommended system(1) Highly Sensitive Problem. As for multiple-dimensional or graph data, whose sensitivity is so high that it may lead to poor utility of the data, how to reduce the sensitivity of function f and enhance the utility require deep-going research.(2) Time Series Problem. As far as time series data is concerned, how to balance the utility and the security when the time T is increasing is a question deserving research, and privacy guarantee for online data is another question worth studying as well.(3) Efficiency Problem. Computational complexity of many differential privacy algorithms is relatively high, so how to ensure privacy while simultaneously improving algorithm efficiency is a question deserving research.(4) New Research Direction for Differential Privacy. Among existing differential privacy data release methods, the data usually are stored in one party; if the data are stored in multiple parties, therefore how to share the data and guarantee user’s privacy between multiple parties is a question deserving further research for distributed differential privacy [72, 73], which is also called security multiparty computation problem. It mainly faces the following difficulties: (1) excessive communication overhead makes the algorithm infeasible if the data and participants are large; (2) how to design an algorithm and make it satisfy differential privacy is another obstacle. So an efficient and safe algorithm with lower communication overhead is a question deserving research, for example, how to design a differential privacy algorithm for such distributed real time streaming data as financial data.(5) The Definition Expansion of Differential Privacy. Kearns et al. [74] introduced the differential privacy into game theory to guarantee player’s privacy. The paper points out that the equilibria of complete information games can be implemented in setting of incomplete information under certain conditions (the number of players is large). Any algorithm that estimates a correlated equilibrium of a complete information game while satisfying a variant of differential privacy is called joint differential privacy. By this time, no group of the players can derive “much” about the type of any player outside the group, even if these players collude in an arbitrary way [74].Definition 9 (joint differential privacy [74]).
Given a randomized functionA:Dn→Rn, let D and D′ be i-neighboring datasets which differ only in their ith coordinate, i∈{1,…,n}; for every event S⊆Rn-1, A is said to be (ε,δ)-joint differential privacy if(9)Pr⁡AD-i∈S≤exp⁡ε∗Pr⁡AD′-i∈S+δ,where A(D)=(r1,…,rn), A(D)i=ri, A(D)-i=(r1,…,ri-1,ri+1,…,rn), and (ε,δ)-joint differential privacy equals ε-joint differential privacy when δ=0.In joint differential privacy, the input date hasn data elements and the output also is a vector of n messages; that is, the input D=(x1,…,xn)∈Dn and the output is r=(r1,…,rn)∈Rn. Each output element ri is corresponding to a input element xi of one player, and it can guarantee ith player’s privacy even if other players collude; that is, they know all information except input xi and output ri of ith player (x1,…,xi-1,xi+1,…,xn and r1,…,ri-1,ri+1,…,rn) but fail to learn much about ith player’s input xi.Joint differential privacy is an appropriate solution concept for problems whose solution can be partitioned amongst then players who provide the privacy data to the algorithm, such as equilibrium computation [74, 75] in game theory and agent’s privacy guarantee in maximum matching problem [76].


## 4.1. Histogram Release

Histogram is constructed by splitting the input dataset into mutually disjoint subsets called buckets or bins depends on a set of attributes. Any access to the raw data is conducted through the differential privacy interface when users send data query, and the differential privacy histogram is used to answer the user’s queries; the process is shown in Figure5 [46].Figure 5
Different private histogram release.The most straightforward method is to add Laplace noise to each histogram bucket using privacy parameterε, and the noise is Lap(1/ε) as count function sensitivity Δf=1; this method is fit for unit length queries and short-range queries, and it will lead to larger query error under long-range (i.e., the number of bucket n is larger) queries according to noise variance formula 2n/ε2. In order to reduce the query error, multiple buckets are merged into one partition; now the number of tuples which fall into each partition is the average value of the number of tuples in these buckets, as shown in Figure 6.Figure 6
Example of buckets merger.The noisenoise is added to each bucket before the merger, and the total noise is 7noise; after merge operation, the total noise becomes 3noise, which is smaller than the value before the merger. However, merge operation introduces an approximation error as the number of tuples in the partition is the average value of the number of tuples in multiple buckets.We need to make the least possible number of partitions to reduce the noise error and make the number of tuples of buckets in a partition the same as much as possible to reduce the approximation error. In general, a finer-grained partitioning will introduce smaller approximation error but larger noise error, so finding the right balance between approximation error and noise error is a key question [46].Xiao et al. [29, 46] proposed a partitioning strategy based on the kd-tree. It seeks to merge buckets which are close to uniform into a partition using a variance-like metric U(p0), which is defined as U(p0)=∑ci∈P0x(ci)-a0, where p0 is the current partition, ci is the each bucket in p0, x(ci) is the number of tuples in ci, and a0 is the average value of buckets in p0. If U(p0)>T, where T is a giving threshold, then current partition p0 is split into two partitions according to the split median of all the numbers of buckets in p0. The process repeats until the whole domain is split into several partitions and each partition is close to uniform.The process ofkd-tree based histogram release is as follows. First, the original histogram is constructed according to the kth different attributes of raw data and the noise is added to original histogram using privacy budget ε/2 to generate a noisy k-dimensional dataset. Next, the noisy k-dimensional dataset is partitioned by kd-tree algorithm according to U(P0), getting final partitions. Then, the noise is added to each partition using the remaining privacy budget ε/2. Finally, the noisy histogram is released. The property of the algorithm is decided by the parameter U(p0) and the tree depth when partitioning or the number of tuples in each partition. kd-tree based histogram release algorithm is further used in health information DE-identification in Xiao et al.’s subsequent research and is named DPCube, which is based on Strategy 1 and kd-tree is used for postprocessing after adding noise. DPCube supports multidimensional data, long-range query and query error may be lower if the value of parameters selected properly.In view of the right balance between the appropriation error and the noise error, Xu et al. [15] proposed the notion of Sum of Squared Error (SSE) in order to reduce the appropriation error and enhance the data query accuracy. SSE is defined as follows: SSE(H,D)=∑j∑lj≤i≤rjxoptj-xi2, D={x1,x2,…,xn} is a series of counts of original histogram and xi is the count of each bucket, H={p1,p2,…,pk} represents the partitioned histogram which merges neighboring counts into k partitions and pj is the partition of the histogram, which contains an interval [lj,rj]⊆[1,n], and xoptj is the optimal value for pj and is generally computed by the mean value of the counts in [lj,rj]; that is, xoptj=∑i=ljrjxi/(rj-lj+1).Two algorithms NoiseFirst and StructureFirst are proposed dependent on SSE to measure the error between the histogramH and the original count data D. Strategy 1 based NoiseFirst constructs the optimal histogram adopting by dynamic programming method after adding noise and is fit for short-range query; Strategy 2 based StructureFirst generates the optimal histogram based on the original count sequence, which has the risk of privacy disclosure. StructureFirst first uses partly privacy budget ε1 to guarantee the sensitive information in the histogram; then, the noise is added to the partitions using remaining privacy budget (ε-ε1), and StructureFirst is fit for long-range query. StructureFirst and DPCube proposed by Xiao et al. are very similar; the maximal difference is that the two steps in DPCube separately allocated privacy budget ε/2, that is, uniform budgeting, while StructureFirst is a near-optimal budgeting strategy. The two above methods need to reconstruct the histogram; that is, the original histogram is reconstructed, and the number of partitions k is the key factor that affects the algorithm’s performance.In order to reduce the error in long-range query, Hay et al. [47] proposed optimizing histogram by hierarchical tree structure. Histogram is transformed into hierarchical tree structure; then one can arrange all queried intervals into a tree, where the unit-length intervals are the leaves [48], and the query accuracy is enhanced by the consistency check between each layer node of the tree.In view of the hierarchical method for optimizing histogram, Qardaji et al. [48] researched the factors which affect the mean squared error (MSE) of range query under the consistency check and different budgeting strategies. The hierarchical method in one dimension can reduce MSE when branching factor is more than 4; however, the hierarchical method fails to adapt multidimensional histogram when the dimensionality is greater than or equal to 3. The noise is directly added to each unit bucket in the histogram, which is called the Flat method by Qardaji et al., and Flat outweighs the hierarchical method. Detailed analysis of histogram release methods is shown in Table 2.Table 2
Histogram release methods.
Method name
Strategy
Advantage
Defect
Budgeting
DPCube
Strategy1
Supports multidimensional and long-range query
Parameter affects query accuracy heavily
Uniform budgeting
NoiseFirst
Strategy1
Fit for short-range query
Histogram reconstruction is expensive
Uniform budgeting
Structure First
Strategy2
Fit for long-range query
Histogram reconstruction is expensive
Near-optimal budgeting
Flat
Strategy1
Fit for multidimensional data
Low-dimensional data query error is larger
Uniform budgetingIn a word, methods based on histogram release usually need to reconstruct the original histogram; when the number of partitionsk grows, the approximation error gets less, but the noise error becomes larger; meanwhile, it will enlarge the time cost and make its application restricted. For instance, the time complexity of StructureFirst is O(kN2), k=O(N); the value of k affects the time cost, so how to improve the efficiency of the algorithm and reduce the approximation error especially when data dimensionality is larger is one research direction of histogram. Moreover, many algorithms adopt uniform budgeting, and how to allocate the privacy parameter ε based on the requirements of application to enhance the query accuracy is another research direction. Note that Li et al. [49] first proposed DPSynthesizer, an open source visual toolkit for differentially private histogram data release, which can make the user see the one-dimensional or multidimensional differential privacy histogram data directly in terms of graph.


## 4.2. Tree Structure Release

In order to seek differential privacy budgeting strategy and reduce the query error, a series of methods based on tree-structure data split were proposed, and they are known as private spatial decompositions which divide the geospatial data into smaller regions and obtain statistics on the points within each region [30]. If the partition discloses the sensitive information during spatial decomposition, it is called data-dependent decomposition; otherwise, it is called data-independent decomposition. For instance, kd-tree is recursively split through the median data value, which discloses the median value itself, so it is called data-dependent decomposition.(1) Data-Dependent Decomposition. As shown in Figure 7, node 5,4 discloses itself during splitting; in order to mask the real information, the noise is added to the node. Let D={x1,…,xn}, xi∈[l,r]; the data in D is sorted in ascending order and xm is the median value; then the noisenoise is added; that is, M(D)=xm+noise, noise~Lap(Δf/ε); however, the noise median M(D) may go beyond the range of the data D; that is, M(D)∉[l,r]; as for this issue, Inan et al. [50, 51] proposed to adopt the mean instead of the median for numerical data, and the mean can be approximated as the ratio of the sum of noisy counts to the number of the counts, but this method fails to ensure the degree of approximation between the mean and the median.Figure 7
Example of privatekd-tree.As for indexing structure based onkd-tree, Xiao et al. [29, 46] first use privacy budget ε/2 for original data and then construct kd-tree and compute the median by noisy data, finally guaranteeing the privacy of the median.Cormode et al. [30] proposed EM method to judge the median according to exponential mechanism among the kd-tree; EM returns x with Pr[EM(D)=x]∝e-ε|rank(x)-rank(xm)|/2, and rank(x) represents the rank of x in data D. Since the value x is approximately equal to the median xm, the median is guaranteed. After the selection, using privacy budget εmedian for xm, using privacy budget εcount for count computation, and ε=εmedian+εcount, a consideration is that larger value of εmedian leads to more accurate median, but larger count error, while smaller value of εmedian generates more accurate count computation, but larger median error, so how to allocate the budget ε for the count computation and the median computation and balance the errors on the count error and the median error is a concern. The above algorithm based on kd-tree and EM medians is called kd-standard.(2) Data-Independent Decomposition. Cormode et al. [30] proposed the algorithm Quad-opt based on quadtree, which recursively divides the data space into equal quadrants, does not disclosure data information, and belongs to data-independent decomposition. As shown in Figure 8, the data a is divided into four quadrants bi, i∈[1,4], and bi would continue to divide until the predefined tree depth h is reached; h begins with 0. Compared to classical uniform budgeting, that is εi=ε/(h+1), Cormode proposed a novel geometrical budgeting strategy (by a factor of 23), which allocates εi for each level of the tree, thereto, εi=2(h-i)/3ε(23-1)/(2(h+1)/3-1), i=[0,h], ∑i=0hεi=ε; then the least upper bound of error in query Q satisfies ErrQ=Var(Q)≤2h+7/ε2; the query error is the sum of the nodes contained in Q variances. Quad-opt can handle the noisy data through the least square method during postprocessing and further enhance the query accuracy. For example, if the node a’s budget is ε1 and its children’s budget is ε2, in order to optimize the query error Err(Q) when querying the noisy count in node a, we should let Q(a)=(4ε12/4ε12+ε02)x~a+(ε02/(4ε12+ε02))∑i=14x~bi, where x~a is the noisy count in node a itself and x~bi is the noisy count of four children; then Err(Q(a))=Var(Q(a))=8/4ε12+ε02<2/ε12=Var(x~a).Figure 8
Example of private quadtree: the numbers are the actual counts.If allocating all privacy budget to the leaf nodes, the algorithm is equivalent to directly dividing the data space intow×w cells. When the data is very sparse, adding noise to each cell will lead to poor information remaining; inspired by it, Fan et al. [32] proposed Spatial Estimation Algorithm (SEA), which merges similar cells into one group or partition to rise above the sparsity of the data. SEA first models different types of cells dependent on the domain knowledge before split; that is, each cell is sparse or dense, and the partition is called homogeneous if all the cells contained in this partition belong to the same category and need not to split; on the contrary, it is necessary to split until the partition is homogeneous or reaches the predefined tree depth. Then the noisenoise is added to each partition pi after the data splitting has completed, and the cell noise is noise/pi.size(), where pi.size() is the number of cells in the partition pi. Finally, SEA enhances the query accuracy while simultaneously providing very high level privacy guarantee by cells merge operation, essentially by reducing the added noise for cells.The partition based on quadtree orkd-tree is fit for one-dimensional or two-dimensional data; as for multiple-dimensional data, Qardaji et al. [31] proposed method UG based on uniform grid which can be seen as an n-tree especially. There are two sources of error in the grid method: one is noise error introduced by adding random noise followed Laplace distribution; another is nonuniformity error introduced by assuming that the data points are distributed uniformly and nonuniformity error is proportional to the number of data points in the cells that fall on the border of the query rectangle [31]; then the query error Err(Q) refers to the two errors above.UG splits the space data intow×w cells; given a query Q, the query error Err(Q)=2rw/ε+rN/wc0, where N is the number of data points, r is the ratio of the area of the query Q to the area of the whole domain, and c0 is a constant. Note that UG gives the granularity w of the partition, which is the key factor effecting the accuracy of query results, and w is about Nε/c, (c=2c0).UG treats all cells equally whether sparse cells or density cells. When the cell is very sparse, the noise error is too large; on the other hand, when the cell is very dense, the nonuniformity error is too large. Qardaji et al. further proposed the adaptive grids method AG to balance the two errors: when a region is sparse, a finer granularity is needed to reduce the noise error; when a region is dense, a coarse granularity is used to reduce the nonuniformity error.AG first splits the space data intow1×w1 coarse cells. If a cell ci is too dense, ci can be further split into w2×w2 finer cells, and then issuing a count query for each coarse cell and finer cell using privacy budget aε and (1-a)ε is carried out. In order to optimize the data query error, let w1=max10,0.25Nε/c, w2=2x~i(1-α)ε/2c0, where x~i is the noisy count in cell ci. However, UG and AG also lack the adaptive judging criterion whether the cell is sparse or dense. At the same time, it is assumed that the nonuniformity error is proportional to the number of data points in the cells. In this model, the query rectangle is just square, which is not so consistent with the fact because the shape of query may be rectangular, and the query results are influenced severely by the selection of c0. Detailed analysis of tree structure release methods is shown in Table 3.Table 3
Tree structure release methods.
Method name
Strategy
Advantage
Defect
Budgeting
Quad-opt
Strategies2 and 3
Computational efficiency is high; support any range query
Error is large
Geometric budgeting
SEA
Strategy2
Noise error is small
Approximate error is large
Uniform budgeting
k
d-standard
Strategy2
Query accuracy is high
Only fit for low-dimensional data
Median and count use privacy budget together
UG
Strategy1
Support any range query
Neglects the balance between noise error and nonuniformity error
Uniform budgeting
AG
Strategy1
Balance the noise error and the nonuniformity error
Lack of the adaptive judging criterion
Uniform budgetingIn conclusion, there is no privacy risk for tree structure in the data-independent decomposition, but how to reduce the noise error is the key for our special research. In Fan et al.’s data category, there are only sparse data and dense data, and the partition of data category is too coarse, so how to partition the data category based on the variance or information entropy to enhance the query accuracy is one of the research directions in the future. In data-dependent decomposition, some privacy budget is needed to guarantee the privacy forkd-tree itself disclosing the median information; thus, how to balance the allocation of the privacy budget to raise the query accuracy is one of the research directions in the future.


## 4.3. Time Series Release

There are many differential privacy real time data release, such as MHR, GPS, and track. The real time data with higher correlation between time stamps has a timescale, if the length of the time series isT and the noise noiset is added to the data xt at time k, noise~Lap(T/ε), when T is large, the added noise gets large and leads to poor utility of the data.As for time series data, in order to reduce the error, Rastogi and Nath [52] proposed algorithm DFTk based on discrete Fourier transform. For time series D, DFTk first executes the discrete Fourier transform, that is, F=DFT(D), and retains only the first k DEF coefficients; then the Laplace noise is added to those coefficients and the inverse Fourier transform is executed on the noisy coefficients F~, that is D~=IDET(F~). Finally, the perturbed data D~ is released. However, the algorithm DFTk needs to execute the DET() and IDET() operations with the full series, and it is not compatible to real time applications [32].As for real time traffic monitoring data, in order to raise the execution efficiency and query accuracy of the algorithm in the real time environment, Fan et al. [32] proposed Temporal Estimation Algorithm (TEA) based on the time series model. Given the space G, TEA first splits the space into w×w cells and the time span T is discretized into time index, where 0≤k<T. The frequency series Dc of cell c is {xkc∣0≤k<T}, where xkc is the frequency series of c at time stamp k and all frequency series DG in G are {Dc∣c∈G}. Then, the model is constructed dependent on domain knowledge, such as locations, population, and road networks; for each cell c, the process model is xk+1c=xkc+ωc, p(ωc)~N(0,Qc), where Qc represents the degree of variation between neighbor time stamps, and the noise is added to the frequency series of c at time stamp k; that is, x~kc=xkc+noise, noise~Lap(0,1/ε0), where ε0=ε/T and ε is uniform budgeting for the time span T. For estimation purpose, noise is replaced by white Gaussian noise; that is, noise~N(0,R). Finally, the noisy data D~G is released. TEA utilizes the time series model and the educated guess to enhance the query accuracy; meanwhile, the computing complexity is low and time complexity is O(kw2), where k=O(1).For the time spanT, if a real time system has higher sampling rate, larger noise will be introduced to satisfy the differential privacy; on the contrary, the approximate error is larger if the system is with lower sampling rate, so how to select the value of sampling rate is the key. Fan et al. proposed an adaptive sampling algorithm FAST [33, 34] to solve the problem in the subsequent research. FAST can adjust the sampling rate F automatically according to data dynamic and F≤T; the sampling rate is increased when the data changed rapidly and vice versa. The dynamic of current data can be described by the feedback error Ekn, which is defined as |x^kn-x^kn-|/max{x^kn,δ}, where x^kn and x^kn- are the posterior estimate and the prior state estimate for nth (0≤n<F) sampling point at time step kn (0≤kn<T) and δ is a parameter assigned by user and generally δ=1. Because of the data, the sampling frequency is not fixed; in order to achieve the optimal sampling rate in minimal time, FAST uses the PID controller to adjust the rate. Firstly, PID algorithm takes Ekn as the input and gets the output Δ, that is, the PID error, which is defined as follows: Δ=CpEkn+(Ci/Ti)∑j=n-Ti+1nEkj+Cd((Ekn-Ekn-1)/(kn-kn-1)), where Cp, Ci, and Cd are the proportional, integral, and derivative components of PID; then the new sampling rate I′ is max{1,I+θ(1-e(Δ-ξ)/ξ)}, where θ and ξ are parameters specified by user. The adaptive sampling algorithm FAST reduces the noise error from Θ(T) to Θ(F).As for web browsing behavior data, utilizing the rich correlation of the time series, Fan et al. proposed session-level differentially privacy algorithm U-KF [35] based on the user-level framework FAST. U-KF releases the differential privacy aggregates using state-space model in real time and adopts Kalman filter [53] during postprocessing. Given original data {xki,i=1,…,m}, where xki represents the number of sessions browsing pagei at time k. Firstly, in the prediction step, the prior estimate x^ki- is derived from the previous posterior estimate xk-1i, where “^” represents state estimates and the superscript “−” represents variables related to the prior estimate [35]. Then, computing the perturbed value x~ki, that is x~ki=xki+noiseki, noiseki~Lap(0,lmax/ε), where lmax is the query sensitivity. Next, in the correction step, the posterior estimate x^ki is computed according to the perturbed value x~ki and the prior estimate x^ki-, that is, x^ki=x^ki-+Kki(x~ki-x^ki-), where Kki is the Kalman gain [53]. Finally, {x^ki,i=1,…,m} is released. U-KF is a univariate time series algorithm with higher query accuracy and its computing time is proportional to the number of web pages, that is, O(m); however, U-KF only supports the browsing request in the single server, failing to support the request in different servers. Detailed analysis of time series release methods is shown in Table 4.Table 4
Time series release methods.
Method name
Strategy
Advantage
Defect
Budgeting
D
F
T
k
Strategy2
Supports long-range query
Parameter affects query accuracy
Uniform budgeting
TEA
Strategies1 and 2
Computing complexity is low; query accuracy is high
Affected by data type
Uniform budgeting
FAST
Strategies1 and 2
Query accuracy is high; adaptive data changes
Add the cost of feedback control
Uniform budgeting
U-KF
Strategy2
Computing complexity is low; query accuracy is high
Only supports requests in signal server
Uniform budgetingAs for record data, in order to enhance the query accuracy, Xiao et al. [54, 55] proposed Privelet method based on wavelet transform. Privelet does not directly perturb the frequent matrix M of input data, but first transforms the M into the wavelet coefficient matrix C, which is perturbed by Laplace noise; then the noisy coefficient matrix is mapped into noisy frequent matrix M~; finally, M~ is released. It is known then that the differential privacy based on wavelet transform is feasible. As for real time data, such as smart meter, Ferrández-Pastor et al. [56] indicated that using wavelet transform to analyze the behavior of user is feasible, so the time series release combined with wavelet transform is one of the research directions in the future. At the same time, how to split the time span T is the key of time series release methods; the partition granularity of T should be approximate, combined with the features of data, such as the stepped data; how to adaptively spit the data is also one of the research directions in the future for time series.


## 4.4. Graph Release

Nowadays, digital health social network often contains user’s sensitive information, and directly releasing these network data may harm individual privacy, so the network data should be sanitized before the release. Network data is different from general data, and it will be highly sensitive to small changes as the clustering coefficient is larger according to graph theory. For instance, adding random noise to a subgraph counting query for purpose of masking the presence or not of an edge, and larger noise implies poorer utility of the data. In order to enhance the utility of the sanitized data, a series of methods were proposed.Hay et al. [57] first proposed edge differential privacy for networks data or differential privacy for short. Given graphs G1=(V1,E1) and G2=(V2,E2), V1 and V2 are the set of vertices of graphs G1 and G2; E1 and E2 are the set of edges of graph G1 and G2; if V1=V2, E1=E2, and |E1|+1=|E2|, then G1 and G2 are neighbors which are denoted by |G1ΔG2|=1.Definition 8 (edge differential privacy [57]).
LetG1 and G2 be two neighboring datasets which differ on at most one edge, denoted by |G1ΔG2|=1; given a randomized function A:D→R, Range(A) is the set of all possible outputs of A in G1 and G2, and given an arbitrary subset S⊆Range(A), A is said to be ε-edge differential privacy or ε-differential privacy if(8)Pr⁡AD∈S≤exp⁡ε∗Pr⁡AD′∈S.Similarly, edge differential privacy can be expanded to multiple edges; if neighboring datasets differ onk edges, that is, |G1ΔG2|=k, then function A is said to be ε-k edge differential privacy. Furthermore, if neighboring datasets which differ up to all edges connected to one single node, that is, |G1ΔG2|=∀|k|, (ki∈v), then A is said to be ε-node differential privacy, which is the ultimate aim desirable to achieve; however, it will introduce excessive noise and cause the worst utility of the data, in subsequent sections, A satisfies ε-edge differential privacy as the privacy standard.In order to raise the utility of graph under the requested level of privacy, the graph’s structure is needed to be captured first; then it would be converted back into a synthetic graph desired to be the same with original graph after adding noise. Sala et al. [58] proposed Pygmalion method, which captures the graph’s structure according to dK-series graph model [59].d
K can capture the graph’s structure into statistical number called dK-series, which is the number of nodes at different degree distribution for d-node subgraphs. As shown in Figure 9, when d=1, the distribution is the node degree distribution; when d=2, the distribution is the joint degree distribution for 2-node subgraphs; then using a matching generator, a synthetic graph is generated from the dK-series.Figure 9
Example ofdK-series.Pygmalion first captures thedK-series from the original graph and then sorts the dK-series and clusters the dK-series to get a set of subseries. Next, each subseries is perturbed by random noise according to local sensitivity. Finally, a synthetic graph is generated from the perturbed dK-series. However, local sensitivity might reveal sensitive information although it reduces the noise magnitude.Wang and Wu [36] also used dK-series graph model to capture the graph’s structure, in order to strictly achieve differential privacy and avoid revealing the privacy, and adopted the smooth sensitivity. For 2K-graph, Wang and Wu proposed a method DP2K(ε), which satisfies (ε,δ)-differential privacy. DP2K(ε) first uses the parameter (ε,δ) to compute the value of (β,α), where α=ε/2, β=ε/2ln⁡(2/δ), and then obtains the β-smooth sensitivity Sf,β(G) according to β and the sensitivity LSf(G); next, it uses Sf,β(G) to get the random noise which is added to the 2K-graph series; finally, a new graph is generated by perturbed series.Wang et al. [37] proposed another method, that is, LNPP, which uses spectral graph to guarantee the graph data. Spectral graph analysis mainly applies the graph’s adjacent matrix to construct the graph’s topological structure. For example, the adjacent matrix An×n represents the graph G, where Ai×j=1 if there is an edge between nodes i and j; Ai×j=0 if not. LNPP first decomposes matrix A and gets eigenvalues and eigenvectors; then, these values are perturbed based on Laplace mechanism, and the output eigenvectors are postprocessed by the vector orthogonalization technique [60] as the perturbed eigenvectors are no longer orthogonormal [37].Adopting the spectral graph and thedK-graph model to guarantee privacy, the noise introduced by the former is proportional to O(n), and the latter’s sensitivity is O(n), where n is the number of vertices in the input graph. In order to raise the utility of the data, Xiao et al. [38] proposed a novel method hrg-ε1-e-ε2, which is based on hierarchical random graph (HRG) model to reduce the perturbed noise magnitude.Classical graph model is construed by considering the observed edges, and HRG uses the connection probabilities between vertices. In the HRG model, graphG can be represented by a hierarchical structure and the connection probabilities. The hierarchical structure of G is a rooted binary tree which has n leaf nodes corresponding to the n vertices of G [38]. Each internal node r has a probability pr, and any two vertices i and j of G, their connection probability pi,j=pr, pr=er/nLr∗nRr, where r is two vertices’ lowest common ancestor in T, Rr and Lr are the right and left subtrees of internal node r, nLr and nRr are the numbers of leaf nodes in left and right subtrees, and er is the number of edges in G whose endpoints are leaves of the two subtrees of r in T [38]. So, the hierarchical random graph can be defined as (T,{pr}). As shown in Figure 10, original graph G can be represented by dendrogram T1 and dendrogram T2.Figure 10
Example of the HRG model.
(a)
Original graphG
(b)
DendrogramT1
(c)
DendrogramT2For graphG, in order to select a good dendrogram from numerous candidates, the notion likelihood is proposed to estimate how to represent G exactly by the selected dendrogram; that is, L(T,{pr})=∏r∈Tpprer(1-pr)nLr∗nRr-er. In the above instance, firstly, the set of {pr} is calculated for each dendrogram; then the likelihoods of two dendrograms are computed; that is, L(T1)≈0.00165 and L(T2)≈0433; finally, L(T1) is compared to L(T2); one can see that T2 is more exact to represent the original graph as L(T2) is larger.In hrg-ε1-e-ε2, privacy budget ε is divided into two parts; firstly, exponential mechanism is used; a Markov chain Monte Carlo procedure is designed to select a good dendrogram Tsample, in which only one probability would be affected with a single edge change. This step consumes privacy budget, that is, ε1 and score function is log⁡L(T,{pr})=-∑r∈TnLrnRrh(pr), where h(pr)=-prlog⁡pr-1-prlog⁡(1-pr); then, Laplace mechanism is adopted; the set of {pr} of Tsample is perturbed using remaining budget ε2; finally, the sanitized graph G~ is reconstructed by HRG model and is released. The global sensitivity of hrg-ε1-e-ε2 is O(log⁡n) and reduces the added noise magnitude. Detailed analysis of graph release methods is shown in Table 5.Table 5
Time series release methods.
Method name
Strategy
Advantage
Defect
Budgeting
Pygmalion
Strategy2
Reducing the noise by subsection
Having the risk of privacy disclosure using local sensitivity
Uniform budgeting
DP2K(ε)
Strategy2
Guaranteeing the privacy by smooth sensitivity
Noise is large
Uniform budgeting
LNPP
Strategies1 and 2
Enhancing the utility by postprocessing
Noise is large
Uniform budgeting
hrg-ε1-e-ε2
Strategy2
Utility of the data is high
Result affected by different budgeting strategies
Sampling and perturbation use privacy budget togetherTo sum up, directly adding noise to graph will lead to poor utility of the data as high sensitivity of graph, and it requires to project the data to other data types, such as spectral domain,dK-series, and connection probabilities; therefore, how to select a good data type with a lower sensitivity is one of the research directions in the future.


## 4.5. Pattern Mining Release

Frequent pattern is a subset of items and is frequently present in dataset, such as item-set, subsequence, and substructure, and it is the basis of mining tasks, that is, classification, clustering, and so forth. However, it may reveal individual’s privacy during frequent pattern mining, so how to identify the useful patterns in the data while simultaneously guarantee user’s privacy is a new research direction of data mining.Frequent pattern mining algorithm is usually measured by support degree [28, 39, 40], occurrence [61], and stay point [62, 63], given data D={tran1,tran2,…,trann}, trani∈T, where T is the transaction set constituted by all transactions, and each transaction contains some items; that is, trani={item1,item2,…,itemm}, itemm∈I, where I is the item space constituted by all items and itemset itemsetj is the subset of item space I. if transaction trann contains itemset itemsetj, we say that trann supports itemsetj, and the ratio of the number of transactions supporting itemsetj to the total number of transactions is the support degree for itemsetj. Then, it could be said that itemsetj is a frequent itemset if the support degree is more than the giving threshold.In terms of personal location information, in order to mine the useful pattern, for example, people’s interesting geographic location, Ho and Ruan [62] proposed BuildDPQuadTree method based on quadtree and density-based clustering algorithm (DBSCAN). How to define the interesting region when we query the location history database is the focus, and the notion of stay point is proposed. Given the trajectory data trajiki={x1,x2,…,xki}, xj=(Latj,Lonj,tj), where tj is a timestamp, Latj is the latitude, and Lonj is the longitude. If a trajectory stays in a circle region with a ρ radius for at least a time period ΔT, the center (Lat,Lon) of the circle is a stay point; given a set of trajectories TJ={traj1k1,traj2k2,…,trajsks}, the region is called interesting location if it has more than r stay points in it.BuildDPQuadTree first recursively divides the data spaceG into small regions, given stay point set S, threshold Tthreshold, and privacy budget εqt; if |S|+Lap(3Tthreshold/εqt)≤3Tthreshold, stop partition and go to partition if not. After getting the set of spatial partitions, each cluster Gj, which is the set of stay points of the form (Latj,Lonj), is obtained by density-based spatial clustering of application with noise clustering method [64]. Given the threshold r, privacy budget εcg, and εcts, if |Gj|+Lap(Δfctsj/εcts)≥r, where Δfctsj=maxi∈D⁡#{s∈Gj∣sisastaypointforindividuali} and D is the set of all the individuals who have records in the cluster Gj [62], then Gj is called interesting region, and its center location is defined as [∑k=1|Gj|(Latk,Lonk)]/|Gj|+Lap(Δfcgj/εcts), where Δfcgj=max⁡length(pointx,pointy)/2, pointi∈Gj, and ε=∑i=1hεqt+εcg+εcts, where h is the quadtree depth. BuildDPQuadTree provides a novel method identifying the interesting region by stay point; however, its noise magnitude is easily affected by threshold Tthreshold. In the Ho and Ruan’s subsequent research, the algorithm DP-ILD [63] adopting β-smooth sensitivity was proposed and it satisfies (ε,δ)-differential privacy.The sensitivity of itemset query depends on the dimensionality of itemset during Top-k frequent pattern mining. In order to reduce the sensitivity, the data usually is projected into a lower dimensional space. Li et al. [39] proposed PrivBasis method to search Top-k frequent patterns. In the initialization step, PrivBasis tries to reduce the search space by finding the minimal sets of items IB, which contains the top k frequent itemsets [39]; then the supports of all subsets of IB are derived by applying binary itemset support counting [65]; however, the final frequent patterns may be imprecise.In order to raise the utility of the data, Lee and Clifton [40] proposed the NoiseCut method based on the sparse vector technique and FP-tree. NoiseCut first identifies all frequent itemsets L; in this step, sparse vector technique is adopted to reduce consumption of privacy budget, that is, given a noisy threshold τ^ and a count query q, which only pays privacy budget if q(D)+Lap(2k/ε)≥τ^, where τ^=σk+Lap(·), σk is the support of the kth most frequent itemset. It is noted that NoiseCut regards the itemset as frequent if its noisy support (τ+α) is bigger than τ^. Then the noisy FP-tree is built according to L, and the supports of itemsets and Top-k frequent itemsets can be derived from the FP-tree. In NoiseCut, given an itemset whose support is τ+α, its false negative is exp(-αε/2)(αε/2+2)/4; the smaller the false negative is, the higher obtaining correct frequent patterns becomes.As for graph data, Shen and Yu [28] proposed frequent graph pattern mining method Diff-FPM based on Markov chain Monte Carlo random walk technology. Diff-FPM obtains the Top-k frequent subgraph mainly according to random walk; then, the real counts of subgraphs are perturbed by Laplace random noise. The key to Diff-FPM is whether random walk can reach steady state or not. Diff-FPM satisfies ε-differential privacy if steady state is reached; if not, Diff-FPM only satisfies (ε,δ)-differential privacy, in which the security of the data maybe is affected.As for sequential data, such as DNA sequences and trajectories, Luca and Li [61] indicated that there are some disadvantages using support to mine frequent sequential patterns; for example, one pattern may fail to be regarded as frequent pattern if it repetitively occurs in the same transaction, which may issue in a loss of information patterns. In addition, patterns are represented as a subset of an universe of items and may not well describe the sequentiality of important events in reality [61]. In order to successfully mine the frequent sequential patterns from the sequential data, Bonomi et al. proposed the notion of occurrence which can identify repetitive patterns as frequent. Given a pattern p=a0a1⋯an-1, ai∈Σ, and a string x=x0x1⋯xm-1, if there is an integer i(0≤i≤m-n) making xi+j=aj, j=0,…,n-1, it says that the pattern p presents in position i of the string x, and fx(p) represents all number of occurrences of p in x. Given the dataset D={x0,x1,…,xN-1}, FD(p)=∑i=0N-1fxi(p) denotes the number of occurrences of the p in D, and p is called frequent sequential pattern if FD(p) is larger than the giving threshold. Note that adding or removing one string x in the dataset D may affect the count of a pattern up to O(|x|) and lead to higher sensitivity; in order to reduce the sensitivity, it usually uses a prefix tree structure [66, 67] to split the input data and uses the frequency of the prefixes instead of the frequency of the patterns [61]. Detailed analysis of pattern mining release methods is shown in Table 6.Table 6
Pattern mining release methods.
Method name
Strategy
Advantage
Defect
Budgeting
BuildDPQuadTree
Strategy2
Identify the interesting location using stay point
Noise is large
Partition and cluster use the privacy budget together
DP-ILD
Strategy2
Utility of the data is high
Only supports offline data
Uniform budgeting
PrivBasis
Strategy2
Mining speed is fast
The final frequent patterns may be imprecise
Uniform budgeting
NoiseCut
Strategies1 and 2
Utility of the data is high
Results are affected by different budgeting strategies
Privacy budget is allocated for two steps of the algorithm
Diff-FPM
Strategy2
Query accuracy is high
The drop in utility with the increase of the number of outputs [28]
Sampling and perturbation use the privacy budget togetherLuca and Li pointed out the existing differently privacy frequent pattern mining methods mainly based on the exact data; however, the real data usually are noisy, and some patterns may be lost [61]. There are less research about how to mine the frequent patterns in the noisy data, which is a future research direction. At the same time, how to raise the utility of the data while simultaneously providing privacy guarantee is an issue for further research.For different data types, related researchers proposed a series of differential privacy data release methods, and the methods summarized in this paper only are a part of the whole; there are many methods which the paper fails to describe, such as batch query methods based on matrix [68–70] and data release methods based on machine learning [71].


## 4.6. Discussion

Data release methods under different strategies are the main research contents for differential privacy and are the theoretical basis for practical applications. Classification and comparison of the differential privacy data release methods are shown in Table7, from which we can see that there are few research achievements in this new research area, and there still exists many urgent issues to be addressed and some new study directions to be explored.Table 7
Classification and comparison of differential privacy data release methods.
Classification
Advantage
Defect
Representative methods
Typical Applications
Histogram
Supports any range query
The noise is large in high-dimensional data
DPCube [29]NoiseFirst [15] Structure First [15]
Statistical analysis of disease and search history
Tree structure
Supports multiple- dimensional data and data-dependent or data-independent query
The noise is large in high-dimensional data
Quad-opt [30]AG [31]SEA [32]
Location query of user and device, transport planning
Time series
Supports time series query
It is hard to balance the utility and security in high-dimensional data
TEA [32]FAST [33, 34]U-KF [35]
Real time traffic, disease surveillance
Graph
Supports the analysis and query of graph data
Sensitivity is high, and node-differential privacy is difficult to achieve
DP2K(ε) [36]LNPP [37]hrg-ε1-e-ε2 [38]
Relationship analysis of user in health social network
Pattern mining
Supports differential privacy pattern mining, and original data can be constructed by frequent patterns
Long pattern leads to large noise
PrivBasis [39]NoiseCut [40]Diff-FPM [28]
User behavior, DNA sequences, trajectory and disease trend analysis, recommended system(1) Highly Sensitive Problem. As for multiple-dimensional or graph data, whose sensitivity is so high that it may lead to poor utility of the data, how to reduce the sensitivity of function f and enhance the utility require deep-going research.(2) Time Series Problem. As far as time series data is concerned, how to balance the utility and the security when the time T is increasing is a question deserving research, and privacy guarantee for online data is another question worth studying as well.(3) Efficiency Problem. Computational complexity of many differential privacy algorithms is relatively high, so how to ensure privacy while simultaneously improving algorithm efficiency is a question deserving research.(4) New Research Direction for Differential Privacy. Among existing differential privacy data release methods, the data usually are stored in one party; if the data are stored in multiple parties, therefore how to share the data and guarantee user’s privacy between multiple parties is a question deserving further research for distributed differential privacy [72, 73], which is also called security multiparty computation problem. It mainly faces the following difficulties: (1) excessive communication overhead makes the algorithm infeasible if the data and participants are large; (2) how to design an algorithm and make it satisfy differential privacy is another obstacle. So an efficient and safe algorithm with lower communication overhead is a question deserving research, for example, how to design a differential privacy algorithm for such distributed real time streaming data as financial data.(5) The Definition Expansion of Differential Privacy. Kearns et al. [74] introduced the differential privacy into game theory to guarantee player’s privacy. The paper points out that the equilibria of complete information games can be implemented in setting of incomplete information under certain conditions (the number of players is large). Any algorithm that estimates a correlated equilibrium of a complete information game while satisfying a variant of differential privacy is called joint differential privacy. By this time, no group of the players can derive “much” about the type of any player outside the group, even if these players collude in an arbitrary way [74].Definition 9 (joint differential privacy [74]).
Given a randomized functionA:Dn→Rn, let D and D′ be i-neighboring datasets which differ only in their ith coordinate, i∈{1,…,n}; for every event S⊆Rn-1, A is said to be (ε,δ)-joint differential privacy if(9)Pr⁡AD-i∈S≤exp⁡ε∗Pr⁡AD′-i∈S+δ,where A(D)=(r1,…,rn), A(D)i=ri, A(D)-i=(r1,…,ri-1,ri+1,…,rn), and (ε,δ)-joint differential privacy equals ε-joint differential privacy when δ=0.In joint differential privacy, the input date hasn data elements and the output also is a vector of n messages; that is, the input D=(x1,…,xn)∈Dn and the output is r=(r1,…,rn)∈Rn. Each output element ri is corresponding to a input element xi of one player, and it can guarantee ith player’s privacy even if other players collude; that is, they know all information except input xi and output ri of ith player (x1,…,xi-1,xi+1,…,xn and r1,…,ri-1,ri+1,…,rn) but fail to learn much about ith player’s input xi.Joint differential privacy is an appropriate solution concept for problems whose solution can be partitioned amongst then players who provide the privacy data to the algorithm, such as equilibrium computation [74, 75] in game theory and agent’s privacy guarantee in maximum matching problem [76].


## 5. Conclusion and Future Work

Differential privacy has become the de facto standard to guarantee privacy and is one of the hot research topics in the field of healthcare applications. In this paper, the methods of differentially private data releasing in recent years’ literatures are classified, and a series of data release methods are summarized for privacy problem, which provide certain references for differential privacy in further study. In Section4, as for different categories, different research directions are proposed; for example, it is pointed out that time series release combined with wavelet transform is one of the research directions to solve the privacy of real time streaming data. However, there are still some other questions which are worth studying. They are summarized as follows.(1) The Privacy Budgeting for Tree Structure. Privacy budgeting strategy is usually uniform budgeting in tree structure release, and Cormode et al. [30] presented a novel nonuniform budgeting method based on complete quadtree to improve query accuracy. The key of the method is geometric budgeting strategy, and its theoretical analysis is conducted by the total variance of the all node variances with a great theoretical significance, but the effect is not optimal as fewer nodes may be touched in actual queries. Inspired by it, the error of the data query is small if privacy budget properly tilts toward to the below level nodes of the tree, so how to design an optimal privacy budgeting strategy is a great challenge.(2) The Balance of the Noise Error and Nonuniformity Error. As for geospatial data, Qardaji et al. [31] constructed a differentially private synopsis by choosing the right partition granularity over the data domain to balance the noise error and nonuniformity error, which is proportional to the number of data points in the cells that intersect with the border of the query rectangle. However, nonuniformity error is not only connected with the point number, but also refers to the area of the cells that intersect with the border of the query rectangle, as the less area of intersected portion is, the less nonuniformity error will be. Nonuniformity error especially is 0 when the area of intersected portion is 0, so how to choose the optimal partition granularity for geospatial data when nonuniformity error is connected with both point number and area is a great challenge as well.



---

*Source: 259682-2015-10-27.xml*