# Differential Privacy via Haar Wavelet Transform and Gaussian Mechanism for Range Query

Authors: Dong Chen; Yanjuan Li; Jiaquan Chen; Hongbo Bi; Xiajun Ding
Journal: Computational Intelligence and Neuroscience
 (2022)

---

## Abstract

Range query is the hot topic of the privacy-preserving data publishing. To preserve privacy, the large range query means more accumulate noise will be injected into the input data. This study presents a research on differential privacy for range query via Haar wavelet transform and Gaussian mechanism. First, the noise injected into the input data via Laplace mechanism is analyzed, and we conclude that it is difficult to judge the level of privacy protection based on the Haar wavelet transform and Laplace mechanism for range query because the sum of independent random Laplace variables is not a variable of a Laplace distribution. Second, the method of injecting noise into Haar wavelet coefficients via Gaussian mechanism is proposed in this study. Finally, the maximum variance for any range query under the framework of Haar wavelet transform and Gaussian mechanism is given. The analysis shows that using Haar wavelet transform and Gaussian mechanism, we can preserve the differential privacy for each input data and any range query, and the variance of noise is far less than that just using the Gaussian mechanism. In an experimental study on the dataset age extracted from IPUM’s census data of the United States, we confirm that the proposed mechanism has much smaller maximum variance of noises than the Gaussian mechanism for range-count queries.


---

## Body

## 1. Introduction

Over the past ten years, differential privacy has become one of the important methods in the area of privacy-preserving for statistical databases. Differential privacy is a promising scheme for publishing statistical query results of sensitive data, which has a strong privacy guarantee for opponents with arbitrary background knowledge [1–6]. The strong privacy guarantee of differential privacy ensures that any individuals in the data set will not significantly affect the analysis results of the data set. At present, three basic mechanisms are widely used to ensure differential privacy: Laplace mechanism, Gaussian mechanism, and exponential mechanism. Laplacian and Gaussian mechanisms are applicable to numerical queries, and exponential mechanisms are applicable to non-numeric queries [7–9]. Recently, differential privacy is adopted on many research field, such as social network publishing [10–12], crowdsourced data publication [13, 14], and genomic privacy [15–17].Along with a long-range query scope, the accumulation of noise in the range query answered for privacy preserving can affect the usability of the released data [18, 19]. To reduce the accumulation of noise, the method of hierarchical decompositions is usually employed [20]. Zhang et al. proposed a differentially private algorithm for hierarchical decompositions and named it as PrivTree. This histogram construction algorithm eliminates the dependency on a predefined limit parameter. The privacy-preserving range query is adopted in the field of Internet of Things (IoT) in recent years [21–23]. Cai et al. studied the transaction approximate range counting problem of large IoT data. They proposed a sampling-based method to generate approximate counting results. For privacy reasons, these results will be further disturbed and then published. It is theoretically proved that this result achieves unbiasedness, bounded variance and enhances privacy guarantee under differential privacy. Mahdikhani et al. proposed a communication efficient privacy protection range query in the fog-enhanced Internet of things. The feature of this scheme is that it adopts the Paillier homomorphic cryptosystem and the ingenious bloom filter data structure to achieve better privacy and higher count aggregation efficiency in the range query scenario of protecting privacy. Histogram is a representative and popular tool for data publishing and visualization tasks. Nowadays, protecting private data and preventing the leakage of sensitive information have become one of the main challenges faced by histogram [24–26]. Histogram is the result of a group of counting queries. It is the core statistical tool for reporting data distribution. In fact, it is regarded as the basic method of many other statistical analyses, such as range query [27]. The advantage of histogram representation is that it limits the sensitivity to noise. For example, when histograms are used to support range or count queries, adding or deleting a single record will affect at most one box. Therefore, the sensitivity of range or count query on the histogram is equal to 1, and the amount of additional noise per box will be relatively small [28]. For the differential privacy of long-range queries on the histogram, the accumulation of noise is a key issue that needs to be focused.Discrete wavelet transform (DWT) is an important technology in signal and image processing [29–31]. Lifting scheme, also called second generation wavelet, has many advantages comparing with the first generation wavelet, such as in-place computation, integer-to-integer transforms, and speed [32–34]. Wavelet-based privacy preserving is studied in recent years [35–37]. Xiao et al. propose the differential privacy via Haar wavelet transform. They introduce a data publishing technique named Privelet. Privelet not only ensures ε-differential privacy but also provides accurate results for range query by injecting less noise into wavelet coefficients. The mechanism that can be used to build the differential privacy in Privelet is Laplace distribution. The Laplace mechanism, which is used to guarantee differential privacy in Privelet, maybe not a good choice for building the privacy-preserving system based on discrete wavelet. The reason is that the Laplace noise does not have the property of additivity. That is, the sum of two Laplace distributions is not a Laplace distribution. That means we cannot obtain an analyzable noise distribution by wavelet reconstruction where the Laplace noise is injected into the wavelet coefficients.The Gaussian mechanism for differential privacy is proposed by Dwork [38, 39]. The Gaussian noise can be used in the structuring of hierarchical decompositions, such as wavelet transforms. The property of additivity of Gaussian noise is very important for the reconstruction of noise data. On the one hand, additivity can ensure that the reconstructed noise is still Gaussian noise; on the other hand, some noise can be eliminated during reconstruction.In view of the above analysis, we will do some research on differential privacy via Gaussian mechanism and lifting scheme of Haar wavelet transform for range query in this study. In summary, the main contributions of this work are as follows:(1)
Differential privacy using lifting Haar wavelet transform and Laplace mechanism is analyzed in this study. The distribution of noise injected into the input data via wavelet reconstruction is discussed and we conclude that they are not noise of Laplace distribution.(2)
Differential privacy based on lifting Haar wavelet transform and Gaussian mechanism is constructed in this study. For range query, our analysis shows that the noise actually added into a certain range of original data is much less than the sum of noise at each data for the proposed mechanism.(3)
Differential privacy for range query via lifting Haar wavelet and Guassian mechanism is discussed. We give an algorithm to compute the maximum variance of any range query for any given parameterl (suppose the length of input data is 2l). Moreover, we give a coarse estimation of the maximum variance of range query using a function expression. Finally, we give an experimental study using the proposed mechanism, and the results show the proposed mechanism has a much smaller maximum variance of noise than the Gaussian mechanism for range query.The remainder of the study is organized as follows: Section2 introduces the fundamental definitions and theorems about the differential privacy and its implement mechanism. Section 3 gives the theorems for how to inject Gaussian noise into the Haar wavelet coefficients. Section 4 analysis the noise of range query under the framework of Gaussian mechanism and Haar wavelet. First, the computing method for the variance of range query is given. Second, the algorithm of computing maximum variance for any range query is introduced, and how to get the interval of the range query when obtaining the maximum variance is introduced in detail. Finally, the coarse estimation of the maximum variance of range query is given as a function expression. Section 5 introduces the experimental verification of the computing of maximum variance for the range query based on Gaussian mechanism and lifting Haar wavelet. Conclusions is given in Section 6.


## 2. Preliminaries

In this section, the fundamental definitions and theorems about the differential privacy and its implement mechanism are introduced first. Furthermore, the method of injecting Laplace noise into the Haar wavelet coefficients is given. They are the basis of the other sections.


### 2.1. Differential Privacy

Definition 1 ((ε, δ)-Differential privacy [38, 39]).
A randomized mechanismM with domain Nχ⟶Rd is (ε, δ)-differential privacy if for all S⊆RangeM and for all x,y∈Nχ such that x−y1≤1.(1)PrMx∈S≤expεPrMy∈S+δ,where the symbol x1 denotes the l1-norm of a database x, x1=∑xi, and x−y1 denotes the l1-distance between two databases x and y.


### 2.2. Laplace Mechanism

Definition 2 (l1-sensitivity [39]).
LetNχ⟶Rd be an arbitrary d-dimensional function, then define the l1-sensitivity of function f as follows:(2)Δ1f=maxx,y∈Nχx−y1=1fx−fy1.Definition 3.
(Laplace distribution,Lap(λ)). The Laplace distribution with mean zero and scale λ is the distribution with probability density function:(3)Lapx|λ=12λexp−xλ.
In Definition3, the variance of this distribution is σ2=2λ2. We write Lap(λ) to denote the Laplace distribution with mean zero and scale λ in this study.Theorem 1 (Laplace mechanism [39]).
Letf is a function with l1-sensitivity, the Laplace mechanism, which adds independently random drawn noise distributed as LapΔ1f/ε into each of the d components of the output, preserves ε,0-differential privacy.Remark 1.
Throughout the study, we use the term “noise” to refer to a random variable with a zero mean.


### 2.3. Gaussian Mechanism

Definition 4 (l2-sensitivity [39]).
Letf:Nχ⟶Rd be an arbitrary d-dimensional function, then define the l2-sensitivity of function f as follows:(4)Δ2f=maxx,y∈Nχx−y2=1fx−fy2,where the symbol x2 denotes the l2-norm of a database x, x2=∑xi2, and fx−fy2 denotes the l2-distance between fx and fy.Definition 5 (Gaussian distribution, Gauss(σ2)).
The Gaussian distribution with mean zero and varianceσ2 is the distribution with probability density function:(5)Gaussx|σ2=12πσexp−x2/2σ2.
In Definition5, the variance of this distribution is σ2. We write Gauss (σ2) to denote the Gaussian distribution with mean zero and variance σ2.Theorem 2 (Gaussian mechanism [38, 39]).
Letf be a function with l2-sensitivity and let ε∈0,1 be arbitrary. For σ≥Δ2f⋅2ln1.25/δ/ε, the Gaussian mechanism, which adds independently drawn random noise distributed as Gaussσ2 into each of the d components of the output, ensures (ε, δ)-differential privacy.
In Theorem2, to ensure (ε, δ)-differential privacy, we can inject the Gaussian noise with σ2=2ln1.25/δ⋅Δ2f/ε2 into the input data directly.


### 2.4. Injecting Noise into the Input Data via Lifting Haar Wavelet

#### 2.4.1. Lifting Scheme of Haar Wavelet

The lifting scheme of Haar wavelet transform is shown in Figure1. In Figure 1, x(z) is the input data, xo (z) and xe (z) denote the odd indexed samples and even indexed samples, respectively. a (z) and d (z) are the approximate coefficients and detail coefficients, respectively. For lifting scheme of Haar wavelet, we have p (z) = −1 and u (z) = 1/2.Figure 1
Lifting scheme of Haar wavelet transform.In Figure1, we have(6)xz=∑i=0n−1xi⋅z−i=∑x2k⋅z2−k+z−1⋅∑x2k+1⋅z2−k=xez2+z−1xoz2.Therefore, the approximate coefficientsa (z) and detail coefficients d (z) can be given as follows:(7)az=12xez+xoz,(8)dz=12xez−xoz.In Figure1, the lifting structure has the reconstruction property, that is(9)xo′z=xoz,xe′z=xez,x^z=xz.Figure1 shows one-level decomposition and reconstruction via lifting Haar wavelet transform. The wavelet transform usually consists of many decomposition levels. We can apply the same procedure to the approximate coefficients a (z) to get the multilevel Haar wavelet decomposition, as shown in Figure 2.Figure 2
Multilevel lifting Haar wavelet transform.In Figure2, the top decomposition level is 3 (l = 3), c3,0 is the approximate coefficient, ck,i (i≠0) denotes the ith wavelet coefficient in kth decomposition level, and xmm∈0,7 denotes the input data. In Figure 2, we observe that the number of wavelet coefficients in kth decomposition level is 2l−k.In Figure2, given the Haar wavelet coefficients, any entry xm can be easily reconstructed as follows:(10)xm=cl,0+∑ck,i∈C\cl,0ck,i⋅gk,i,where cl,0 is the approximate coefficient, ck,i(i≠0) denotes the ith wavelet coefficient in kth decomposition level, and gk,i equals 1 (−1) if xm is in the left (right) subtree of ck,i, equals 0 if xm is not in any subtree of ck,i. For example,(11)x1=3=c3,0+c3,1+c2,1−c1,1.In Figure2, if we inject the noise into the approximate coefficients and detail coefficients, then we can obtain the reconstruction data with noise.


#### 2.4.2. Injecting Noise into Haar Wavelet Coefficients

For the noise injected into Haar wavelet coefficients, the tree structure of noise can be obtained by changing the symbol “c” and “x” to n in Figure 2 because they use the same decomposition of multilevel lifting Haar wavelet transform.Referring to equation (10), the noise nm that injected into data xm can be given as follows:(12)nm=nl,0+∑nk,i∈N\nl,0nk,i⋅gk,i,where nl,0 is the noise injected into approximate coefficient, nk,i (i≠0) denotes the noise injected into the ith wavelet coefficient in kth decomposition level, and gk,i equals 1 (−1) if nm is in the left (right) subtree of nk,i and equals 0 if nm is not in any subtree of nk,i.The range sum of these noise has a special property; that is, some subnoise items can be eliminated when computing some sum of range count. For example, referring to Figure2 and equation (12), we have(13)∑i=02l−1ni=∑i=07ni=8⋅n3,0.In the above equation, the other subnoise items exceptn3,0 have been eliminated. This gives us the inspiration to apply this property to range query for differential privacy.


#### 2.4.3. Getting Input Data with Noise

Based on the above two sections, we reconstruct the input data with noise by using the multilevel lifting Haar wavelet transform. Considering Figure2, the input data with noise is shown in Figure 3.Figure 3
Getting input data with noise.In Figure3, xmm∈0,7 denotes the input data reconstructed, nm is the noise injected into data xm. xm+nm denotes the input data with noise. Referring to equations (10) and (12), we have(14)xm+nm=cl,0+∑ck,i∈C\cl,0ck,i⋅gk,i+nl,0+∑nk,i∈N\nl,0nk,i⋅gk,i=cl,0+nl,0+∑ck,i∈C\cl,0nk,i∈N\nl,0ck,i+nk,i⋅gk,i,where the meanings of the symbols cl,0, nl,0, ck,i, nk,i, and gk,i are as stated before.Based on the analysis of above, we conclude that the input data with noised can be obtained by injecting the noise, such as Laplace noise or Gaussian noise, into the approximate and detail coefficients. Moreover, the noise injected into each input data is the sum of the noise injected into approximate and detail coefficients.


#### 2.4.4. Injecting Noise via Haar Wavelet and Laplace Mechanism

In equation (12), we set nk,i as the noise with the Laplace distribution, as given in Definition 3. We have(15)nk,i∼Lapλ2k,where λ is the scale parameter of Laplace distribution and k denotes the kth decomposition level of lifting Haar wavelet transform.According to equations (12) and (15), there is(16)nm∼Lapλ2l+∑nk,i∈N\nl,0Lapλ2k⋅gk,i,where the symbols of nm, nk,i, nl,0, and gk,i are the same as those in equation (12).Using equations (12) and (16), we can describe the Laplace noise injected into Haar wavelet coefficients, as listed in Table 1.Table 1
Laplace noise injected into Haar wavelet coefficients.
n0=n3, 0+n3, 1+n2, 1+n1, 1n1=n3, 0+n3, 1+n2, 1−n1, 1n2=n3, 0+n3, 1−n2, 1+n1, 2n3=n3, 0+n3, 1−n2, 1−n1, 2n4=n3, 0−n3, 1+n2, 2+n1, 3n5=n3, 0−n3, 1+n2, 2−n1, 3n6=n3, 0−n3, 1−n2, 2+n1, 4n7=n3, 0−n3, 1−n2, 2−n1, 4nk,i ∼Lap (λ/23)Lap (λ/23)Lap (λ/22)Lap (λ/21)According to Table1, letting the range of the range query is n0 to n7, we have(17)∑i=02l−1ni=∑i=07ni=8⋅n3,0∼Lap8⋅λ23=Lapλ.That means the sum of all noise injected into the input data is a noise with Laplace distribution with mean zero and scaleλ.Lettingλ=Δ1f/ε, then ε=Δ1f/λ, according to Theorem 1, we conclude the ε,0-differential privacy is preserved for the range query from n0 to n7 using Laplace mechanism.According to Table1, letting the range of the range query is n1 to n3, we have(18)n1+n2+n3=3⋅n3,0+3⋅n3,1−n2,1−n1,1.Therefore,(19)n1+n2+n3∼Lap3⋅λ23+Lap3⋅λ23−Lapλ22−Lapλ21.As we know, the sum of independent random Laplace variables is not a variable of Laplace distribution, so the compositive noise of range query ofn1+n2+n3 that injected into input data x1+x2+x3 is not a noise with Laplace distribution. Therefore, we conclude that it is difficult to judge the level of differential privacy protection based on the Haar wavelet transform and Laplace mechanism.To solve this problem, we consider adopting the Gaussian mechanism for the differential privacy via Haar wavelet transform in the next section.


## 2.1. Differential Privacy

Definition 1 ((ε, δ)-Differential privacy [38, 39]).
A randomized mechanismM with domain Nχ⟶Rd is (ε, δ)-differential privacy if for all S⊆RangeM and for all x,y∈Nχ such that x−y1≤1.(1)PrMx∈S≤expεPrMy∈S+δ,where the symbol x1 denotes the l1-norm of a database x, x1=∑xi, and x−y1 denotes the l1-distance between two databases x and y.


## 2.2. Laplace Mechanism

Definition 2 (l1-sensitivity [39]).
LetNχ⟶Rd be an arbitrary d-dimensional function, then define the l1-sensitivity of function f as follows:(2)Δ1f=maxx,y∈Nχx−y1=1fx−fy1.Definition 3.
(Laplace distribution,Lap(λ)). The Laplace distribution with mean zero and scale λ is the distribution with probability density function:(3)Lapx|λ=12λexp−xλ.
In Definition3, the variance of this distribution is σ2=2λ2. We write Lap(λ) to denote the Laplace distribution with mean zero and scale λ in this study.Theorem 1 (Laplace mechanism [39]).
Letf is a function with l1-sensitivity, the Laplace mechanism, which adds independently random drawn noise distributed as LapΔ1f/ε into each of the d components of the output, preserves ε,0-differential privacy.Remark 1.
Throughout the study, we use the term “noise” to refer to a random variable with a zero mean.


## 2.3. Gaussian Mechanism

Definition 4 (l2-sensitivity [39]).
Letf:Nχ⟶Rd be an arbitrary d-dimensional function, then define the l2-sensitivity of function f as follows:(4)Δ2f=maxx,y∈Nχx−y2=1fx−fy2,where the symbol x2 denotes the l2-norm of a database x, x2=∑xi2, and fx−fy2 denotes the l2-distance between fx and fy.Definition 5 (Gaussian distribution, Gauss(σ2)).
The Gaussian distribution with mean zero and varianceσ2 is the distribution with probability density function:(5)Gaussx|σ2=12πσexp−x2/2σ2.
In Definition5, the variance of this distribution is σ2. We write Gauss (σ2) to denote the Gaussian distribution with mean zero and variance σ2.Theorem 2 (Gaussian mechanism [38, 39]).
Letf be a function with l2-sensitivity and let ε∈0,1 be arbitrary. For σ≥Δ2f⋅2ln1.25/δ/ε, the Gaussian mechanism, which adds independently drawn random noise distributed as Gaussσ2 into each of the d components of the output, ensures (ε, δ)-differential privacy.
In Theorem2, to ensure (ε, δ)-differential privacy, we can inject the Gaussian noise with σ2=2ln1.25/δ⋅Δ2f/ε2 into the input data directly.


## 2.4. Injecting Noise into the Input Data via Lifting Haar Wavelet

### 2.4.1. Lifting Scheme of Haar Wavelet

The lifting scheme of Haar wavelet transform is shown in Figure1. In Figure 1, x(z) is the input data, xo (z) and xe (z) denote the odd indexed samples and even indexed samples, respectively. a (z) and d (z) are the approximate coefficients and detail coefficients, respectively. For lifting scheme of Haar wavelet, we have p (z) = −1 and u (z) = 1/2.Figure 1
Lifting scheme of Haar wavelet transform.In Figure1, we have(6)xz=∑i=0n−1xi⋅z−i=∑x2k⋅z2−k+z−1⋅∑x2k+1⋅z2−k=xez2+z−1xoz2.Therefore, the approximate coefficientsa (z) and detail coefficients d (z) can be given as follows:(7)az=12xez+xoz,(8)dz=12xez−xoz.In Figure1, the lifting structure has the reconstruction property, that is(9)xo′z=xoz,xe′z=xez,x^z=xz.Figure1 shows one-level decomposition and reconstruction via lifting Haar wavelet transform. The wavelet transform usually consists of many decomposition levels. We can apply the same procedure to the approximate coefficients a (z) to get the multilevel Haar wavelet decomposition, as shown in Figure 2.Figure 2
Multilevel lifting Haar wavelet transform.In Figure2, the top decomposition level is 3 (l = 3), c3,0 is the approximate coefficient, ck,i (i≠0) denotes the ith wavelet coefficient in kth decomposition level, and xmm∈0,7 denotes the input data. In Figure 2, we observe that the number of wavelet coefficients in kth decomposition level is 2l−k.In Figure2, given the Haar wavelet coefficients, any entry xm can be easily reconstructed as follows:(10)xm=cl,0+∑ck,i∈C\cl,0ck,i⋅gk,i,where cl,0 is the approximate coefficient, ck,i(i≠0) denotes the ith wavelet coefficient in kth decomposition level, and gk,i equals 1 (−1) if xm is in the left (right) subtree of ck,i, equals 0 if xm is not in any subtree of ck,i. For example,(11)x1=3=c3,0+c3,1+c2,1−c1,1.In Figure2, if we inject the noise into the approximate coefficients and detail coefficients, then we can obtain the reconstruction data with noise.


### 2.4.2. Injecting Noise into Haar Wavelet Coefficients

For the noise injected into Haar wavelet coefficients, the tree structure of noise can be obtained by changing the symbol “c” and “x” to n in Figure 2 because they use the same decomposition of multilevel lifting Haar wavelet transform.Referring to equation (10), the noise nm that injected into data xm can be given as follows:(12)nm=nl,0+∑nk,i∈N\nl,0nk,i⋅gk,i,where nl,0 is the noise injected into approximate coefficient, nk,i (i≠0) denotes the noise injected into the ith wavelet coefficient in kth decomposition level, and gk,i equals 1 (−1) if nm is in the left (right) subtree of nk,i and equals 0 if nm is not in any subtree of nk,i.The range sum of these noise has a special property; that is, some subnoise items can be eliminated when computing some sum of range count. For example, referring to Figure2 and equation (12), we have(13)∑i=02l−1ni=∑i=07ni=8⋅n3,0.In the above equation, the other subnoise items exceptn3,0 have been eliminated. This gives us the inspiration to apply this property to range query for differential privacy.


### 2.4.3. Getting Input Data with Noise

Based on the above two sections, we reconstruct the input data with noise by using the multilevel lifting Haar wavelet transform. Considering Figure2, the input data with noise is shown in Figure 3.Figure 3
Getting input data with noise.In Figure3, xmm∈0,7 denotes the input data reconstructed, nm is the noise injected into data xm. xm+nm denotes the input data with noise. Referring to equations (10) and (12), we have(14)xm+nm=cl,0+∑ck,i∈C\cl,0ck,i⋅gk,i+nl,0+∑nk,i∈N\nl,0nk,i⋅gk,i=cl,0+nl,0+∑ck,i∈C\cl,0nk,i∈N\nl,0ck,i+nk,i⋅gk,i,where the meanings of the symbols cl,0, nl,0, ck,i, nk,i, and gk,i are as stated before.Based on the analysis of above, we conclude that the input data with noised can be obtained by injecting the noise, such as Laplace noise or Gaussian noise, into the approximate and detail coefficients. Moreover, the noise injected into each input data is the sum of the noise injected into approximate and detail coefficients.


### 2.4.4. Injecting Noise via Haar Wavelet and Laplace Mechanism

In equation (12), we set nk,i as the noise with the Laplace distribution, as given in Definition 3. We have(15)nk,i∼Lapλ2k,where λ is the scale parameter of Laplace distribution and k denotes the kth decomposition level of lifting Haar wavelet transform.According to equations (12) and (15), there is(16)nm∼Lapλ2l+∑nk,i∈N\nl,0Lapλ2k⋅gk,i,where the symbols of nm, nk,i, nl,0, and gk,i are the same as those in equation (12).Using equations (12) and (16), we can describe the Laplace noise injected into Haar wavelet coefficients, as listed in Table 1.Table 1
Laplace noise injected into Haar wavelet coefficients.
n0=n3, 0+n3, 1+n2, 1+n1, 1n1=n3, 0+n3, 1+n2, 1−n1, 1n2=n3, 0+n3, 1−n2, 1+n1, 2n3=n3, 0+n3, 1−n2, 1−n1, 2n4=n3, 0−n3, 1+n2, 2+n1, 3n5=n3, 0−n3, 1+n2, 2−n1, 3n6=n3, 0−n3, 1−n2, 2+n1, 4n7=n3, 0−n3, 1−n2, 2−n1, 4nk,i ∼Lap (λ/23)Lap (λ/23)Lap (λ/22)Lap (λ/21)According to Table1, letting the range of the range query is n0 to n7, we have(17)∑i=02l−1ni=∑i=07ni=8⋅n3,0∼Lap8⋅λ23=Lapλ.That means the sum of all noise injected into the input data is a noise with Laplace distribution with mean zero and scaleλ.Lettingλ=Δ1f/ε, then ε=Δ1f/λ, according to Theorem 1, we conclude the ε,0-differential privacy is preserved for the range query from n0 to n7 using Laplace mechanism.According to Table1, letting the range of the range query is n1 to n3, we have(18)n1+n2+n3=3⋅n3,0+3⋅n3,1−n2,1−n1,1.Therefore,(19)n1+n2+n3∼Lap3⋅λ23+Lap3⋅λ23−Lapλ22−Lapλ21.As we know, the sum of independent random Laplace variables is not a variable of Laplace distribution, so the compositive noise of range query ofn1+n2+n3 that injected into input data x1+x2+x3 is not a noise with Laplace distribution. Therefore, we conclude that it is difficult to judge the level of differential privacy protection based on the Haar wavelet transform and Laplace mechanism.To solve this problem, we consider adopting the Gaussian mechanism for the differential privacy via Haar wavelet transform in the next section.


## 2.4.1. Lifting Scheme of Haar Wavelet

The lifting scheme of Haar wavelet transform is shown in Figure1. In Figure 1, x(z) is the input data, xo (z) and xe (z) denote the odd indexed samples and even indexed samples, respectively. a (z) and d (z) are the approximate coefficients and detail coefficients, respectively. For lifting scheme of Haar wavelet, we have p (z) = −1 and u (z) = 1/2.Figure 1
Lifting scheme of Haar wavelet transform.In Figure1, we have(6)xz=∑i=0n−1xi⋅z−i=∑x2k⋅z2−k+z−1⋅∑x2k+1⋅z2−k=xez2+z−1xoz2.Therefore, the approximate coefficientsa (z) and detail coefficients d (z) can be given as follows:(7)az=12xez+xoz,(8)dz=12xez−xoz.In Figure1, the lifting structure has the reconstruction property, that is(9)xo′z=xoz,xe′z=xez,x^z=xz.Figure1 shows one-level decomposition and reconstruction via lifting Haar wavelet transform. The wavelet transform usually consists of many decomposition levels. We can apply the same procedure to the approximate coefficients a (z) to get the multilevel Haar wavelet decomposition, as shown in Figure 2.Figure 2
Multilevel lifting Haar wavelet transform.In Figure2, the top decomposition level is 3 (l = 3), c3,0 is the approximate coefficient, ck,i (i≠0) denotes the ith wavelet coefficient in kth decomposition level, and xmm∈0,7 denotes the input data. In Figure 2, we observe that the number of wavelet coefficients in kth decomposition level is 2l−k.In Figure2, given the Haar wavelet coefficients, any entry xm can be easily reconstructed as follows:(10)xm=cl,0+∑ck,i∈C\cl,0ck,i⋅gk,i,where cl,0 is the approximate coefficient, ck,i(i≠0) denotes the ith wavelet coefficient in kth decomposition level, and gk,i equals 1 (−1) if xm is in the left (right) subtree of ck,i, equals 0 if xm is not in any subtree of ck,i. For example,(11)x1=3=c3,0+c3,1+c2,1−c1,1.In Figure2, if we inject the noise into the approximate coefficients and detail coefficients, then we can obtain the reconstruction data with noise.


## 2.4.2. Injecting Noise into Haar Wavelet Coefficients

For the noise injected into Haar wavelet coefficients, the tree structure of noise can be obtained by changing the symbol “c” and “x” to n in Figure 2 because they use the same decomposition of multilevel lifting Haar wavelet transform.Referring to equation (10), the noise nm that injected into data xm can be given as follows:(12)nm=nl,0+∑nk,i∈N\nl,0nk,i⋅gk,i,where nl,0 is the noise injected into approximate coefficient, nk,i (i≠0) denotes the noise injected into the ith wavelet coefficient in kth decomposition level, and gk,i equals 1 (−1) if nm is in the left (right) subtree of nk,i and equals 0 if nm is not in any subtree of nk,i.The range sum of these noise has a special property; that is, some subnoise items can be eliminated when computing some sum of range count. For example, referring to Figure2 and equation (12), we have(13)∑i=02l−1ni=∑i=07ni=8⋅n3,0.In the above equation, the other subnoise items exceptn3,0 have been eliminated. This gives us the inspiration to apply this property to range query for differential privacy.


## 2.4.3. Getting Input Data with Noise

Based on the above two sections, we reconstruct the input data with noise by using the multilevel lifting Haar wavelet transform. Considering Figure2, the input data with noise is shown in Figure 3.Figure 3
Getting input data with noise.In Figure3, xmm∈0,7 denotes the input data reconstructed, nm is the noise injected into data xm. xm+nm denotes the input data with noise. Referring to equations (10) and (12), we have(14)xm+nm=cl,0+∑ck,i∈C\cl,0ck,i⋅gk,i+nl,0+∑nk,i∈N\nl,0nk,i⋅gk,i=cl,0+nl,0+∑ck,i∈C\cl,0nk,i∈N\nl,0ck,i+nk,i⋅gk,i,where the meanings of the symbols cl,0, nl,0, ck,i, nk,i, and gk,i are as stated before.Based on the analysis of above, we conclude that the input data with noised can be obtained by injecting the noise, such as Laplace noise or Gaussian noise, into the approximate and detail coefficients. Moreover, the noise injected into each input data is the sum of the noise injected into approximate and detail coefficients.


## 2.4.4. Injecting Noise via Haar Wavelet and Laplace Mechanism

In equation (12), we set nk,i as the noise with the Laplace distribution, as given in Definition 3. We have(15)nk,i∼Lapλ2k,where λ is the scale parameter of Laplace distribution and k denotes the kth decomposition level of lifting Haar wavelet transform.According to equations (12) and (15), there is(16)nm∼Lapλ2l+∑nk,i∈N\nl,0Lapλ2k⋅gk,i,where the symbols of nm, nk,i, nl,0, and gk,i are the same as those in equation (12).Using equations (12) and (16), we can describe the Laplace noise injected into Haar wavelet coefficients, as listed in Table 1.Table 1
Laplace noise injected into Haar wavelet coefficients.
n0=n3, 0+n3, 1+n2, 1+n1, 1n1=n3, 0+n3, 1+n2, 1−n1, 1n2=n3, 0+n3, 1−n2, 1+n1, 2n3=n3, 0+n3, 1−n2, 1−n1, 2n4=n3, 0−n3, 1+n2, 2+n1, 3n5=n3, 0−n3, 1+n2, 2−n1, 3n6=n3, 0−n3, 1−n2, 2+n1, 4n7=n3, 0−n3, 1−n2, 2−n1, 4nk,i ∼Lap (λ/23)Lap (λ/23)Lap (λ/22)Lap (λ/21)According to Table1, letting the range of the range query is n0 to n7, we have(17)∑i=02l−1ni=∑i=07ni=8⋅n3,0∼Lap8⋅λ23=Lapλ.That means the sum of all noise injected into the input data is a noise with Laplace distribution with mean zero and scaleλ.Lettingλ=Δ1f/ε, then ε=Δ1f/λ, according to Theorem 1, we conclude the ε,0-differential privacy is preserved for the range query from n0 to n7 using Laplace mechanism.According to Table1, letting the range of the range query is n1 to n3, we have(18)n1+n2+n3=3⋅n3,0+3⋅n3,1−n2,1−n1,1.Therefore,(19)n1+n2+n3∼Lap3⋅λ23+Lap3⋅λ23−Lapλ22−Lapλ21.As we know, the sum of independent random Laplace variables is not a variable of Laplace distribution, so the compositive noise of range query ofn1+n2+n3 that injected into input data x1+x2+x3 is not a noise with Laplace distribution. Therefore, we conclude that it is difficult to judge the level of differential privacy protection based on the Haar wavelet transform and Laplace mechanism.To solve this problem, we consider adopting the Gaussian mechanism for the differential privacy via Haar wavelet transform in the next section.


## 3. Injecting Noise into Haar Wavelet Coefficients via Gaussian Mechanism

To inject Gaussian noise into Haar wavelet coefficients in Figure3, we can set nk,i as the noise with the Gaussian distribution, as given in Definition 5.Let(20)nk,i∼Gauss3σ24k,where 3σ2/4k is the variance of Gaussian distribution.According to equations (12) and (20), we have(21)nm∼Gauss3σ24l+∑nk,i∈N\nl,0Gauss3σ24k⋅gk,i,where the symbols of nm, nk,i, nl,0, and gk,i are same as those in equation (12).Using equations (20) and (21), we can describe the Gaussian noise injected into Haar wavelet coefficients, as listed in Table 2.Table 2
Gaussian noise injected into wavelet coefficients.
n0=n3, 0+n3, 1+n2, 1+n1, 1n1=n3, 0+n3, 1+n2, 1−n1, 1n2=n3, 0+n3, 1−n2, 1+n1, 2n3=n3, 0+n3, 1−n2, 1−n1, 2n4=n3, 0−n3, 1+n2, 2+n1, 3n5=n3, 0−n3, 1+n2, 2−n1, 3n6=n3, 0−n3, 1−n2, 2+n1, 4n7=n3, 0−n3, 1−n2, 2−n1, 4nk,i∼Gauss (3σ2/43)Gauss (3σ2/43)Gauss (3σ2/42)Gauss (3σ2/41)Theorem 3.
Suppose thatX1 and X2 are independent random variables, and Xi has Gaussian distribution with mean zero and variance σi2 for i∈1,2. Then, X1 ± X2 is Gaussian distribution with mean zero and variance σ12+σ22; kX1 is Gaussian distribution with mean zero and variance kσ12.The proof of Theorem3 will not be given because it is a basic property of Gaussian distribution.According to Table2 and Theorem 3, there is(22)∑i=02l−1ni=∑i=07ni=8⋅n3,0=Gauss82⋅3σ243=Gauss3σ2.That means the sum of all noise injected into the input data is a noise with Gaussian distribution. We analyze the distribution of the noise injected into each input data as follows.Theorem 4.
Injecting Gaussian noise with varianceσk2=3σ2/4k into the Haar wavelet coefficients in the kth decomposition level (the maximum decomposition level is l, as shown in Figure 3), the noise injected into each input data via Haar wavelet reconstruction is Gaussian noise with variance (1 + 2/4l) σ2.Proof.
According to Definition5, Theorem 3, Table 2, and equation (21), we have(23)nm∼Gauss3σ24l±∑i=l1Gauss3σ24i,∼Gauss14l+∑i=1l1/4i⋅3σ2,∼Gauss1+24l⋅σ2.
The proof is completed.
Using Theorems2 and 4, we can obtain the ε,δ-differential privacy with variance (1 + 2/4l) σ2 for each input data under the framework of Gaussian mechanism via Haar wavelet transform.Theorem 5 (Differential privacy using Gaussian mechanism and Haar wavelet).
Letf be a function with l2-sensitivity, let ε∈0,1 be arbitrary, and let σ=Δ2f⋅2ln1.25/δ/ε. The mechanism adopting Gaussian and Haar wavelet, which adds Gaussian noise with variance σk2=3σ2/4k into the Haar wavelet coefficients in the kth decomposition level (Figure 3), ensures ε,δ-differential privacy.Proof.
In Theorem4, if the Gaussian noise with variance σk2=3σ2/4kis injected into the wavelet coefficients, the reconstructed data will be the one with the Gaussian noise with variance 1+2/4lσ. According to Theorem 2, the condition of 1+2/4lσ≥Δ2f⋅2ln1.25/δ/ε should be satisfied. Therefore, letting σ=Δ2f⋅2ln1.25/δ/ε, the condition is met and the proof is completed.
We simulate the process of injecting Gaussian noise with = 12 into wavelet coefficients with 15-level decomposition using Theorem4 and injecting Gaussian noise into input data directly and draw the noise-count figures as follows.
Figure4(a) shows the count of the noise injected into input data by injecting the Gaussian noise with σ = 12 into Haar wavelet coefficients with 15-level decomposition using equation (20); Figure 4(b) denotes the noise count by injecting Gaussian noise with mean zero and variance (1 + 2/4l) σ2 into the input data directly. In Figure 4(c), we draw the two curves together and we find that they are almost overlapped. Figure 4(c) shows that the method injecting Gaussian noise into Haar wavelet coefficients has the same level of differential privacy protection as the method injecting Gaussian noise into the input data directly. In this study, we will focus on the application of range query.
According to Theorems3−5, we find that the distribution of noise for the range query using Gaussian mechanism and Haar wavelet is a Gaussian distribution. Therefore, we can calculate the variance of noise easily, for example, as listed in Table 2, we have(24)n1+n2+n3=n3,0+n3,1+n2,1−n1,1+n3,0+n3,1−n2,1+n1,2+n3,0+n3,1−n2,1−n1,2=3n3,0+3n3,1−n2,1−n1,1,∼3Gauss3σ243+3Gauss4σ243−Gauss3σ242−Gauss3σ241,∼Gauss32⋅3σ243+32⋅3σ243+3σ242+3σ241,∼Gauss5732σ2.
From this example, we find that some noises (such asn2,1 and −n2,1, n1,2 and −n1,2) are eliminated by the operation of addition. According to Theorem 4, the variance of noise injected into each input data should be 1+2/43σ2 for l = 3. The total noise variance is 3∗1+2/43σ2=99/32∗σ2. Compared with equation (24), we conclude that, for the range query, the noise actually added into a certain range of the original data is much less than the sum of the noise at each data. Therefore, it is a very important property for Gaussian mechanism to be used on range query.Figure 4
Comparison between injecting Gaussian noise into wavelet coefficients using Theorem4 and injecting Gaussian noise into input data directly.
(a)(b)(c)


## 4. Noise of Range Query under the Framework of Haar Wavelet and Gaussian Mechanism

In this section, we discuss how to compute the noise of the range query under the framework of Haar wavelet transform and Gaussian mechanism. First, we give the computing method for the variance of range query in detail. Second, the interval of the range query when obtaining the maximum variance is introduced. Third, to speed up the computing of maximum variance, we observe the results of the range-count interval when getting the maximum variance and give a speed computing method. Finally, we give a coarse estimation of the maximum variance of range query as a function expression.


### 4.1. Computing Method for the Variance of Range Query

In Figure3, we choose the Gaussian noise and inject them into the approximate coefficient and each wavelet coefficient. The variance of Gaussian noise injected into approximate coefficient is 3σ2/43. The variance of Gaussian noise injected into each wavelet coefficient is 3σ2/4k for level kk∈1,3. The relationship between decomposition level and variance of noise is listed in Table 3.Table 3
Noise variance and decomposition levelk.
kVariance of noiseNumber of wavelet coefficients33σ2/4323 − 323σ2/4223 − 213σ2/4123 − 1The noise-sum of range query via Haar wavelet transform for intervalS can be given by the following equation (Figure 3):(25)nsum=S⋅nl,0+∑nk,i∈N\nl,0nk,i⋅αnk,i−βnk,i,where S is the interval of any range query, nk,i presents the ith noise injected into wavelet coefficient in kth decomposition level, αnk,i denotes the number of left leaves in the left subtree of nk,i that are contained in S, and βnk,i denotes the number of right leaves in the right subtree of nk,i that are contained in S (Figure 3).Now we analyze the noise variance of range query. According to equation (20), we know that the noise injected into approximate coefficient is nl,0 and its variance is 3σ2/4l; the noise injected into wavelet coefficient is nk,i and its variance is 3σ2/4k. Therefore, according to Theorem 3, we can compute the noise-variance of range query by replacing nl,0 and nk,i with 3σ2/4l and 3σ2/4k in equation (25), respectively.(26)σsum2=S2⋅3σ24l+∑nk,i∈N\nl,03σ24kαnk,i−βnk,i2=S2⋅14l+∑nk,i∈N\nl,014kαnk,i−βnk,i2⋅3σ2.To compute the value ofσsum2, we need to calculate the values of αnk,i and βnk,i firstly. In Figure 3, the length of interval of leaves in the subtree of nk,i is 2k. The left point of this interval has the subscript i−1⋅2k and the right point of this interval has the subscript i⋅2k−1. Therefore, the subtree of nk,i has the subscript interval of leaves.(27)Snk,i=i−1⋅2k,i⋅2k−1.For example, the wavelet coefficientn2,2 in Figure 3 has the subscript interval of leaves [4, 7].According to equation (27), we can obtain the left-half interval αL,αRand right-half interval βL,βR of S_nk,i:(28)αL,αR=i−1⋅2k,i⋅2k−2k−1−1,βL,βR=i⋅2k−2k−1,i⋅2k−1.Therefore,αnk,i and βnk,i can be given by computing the number of intersection between S and αL,αR, S and βL,βR, respectively.(29)αnk,i=S∩αL,αR,βnk,i=S∩βL,βR.LetS=SL,SR, where SL and SR denote the left and right points of the given range query interval, respectively. Therefore, we have(30)αnk,i=SL,SR∩αL,αR,(31)βnk,i=SL,SR∩βL,βR,where k∈1,l and i∈1,2l−k (Figure 3).


### 4.2. Maximum Variance of Range Query

The aim of this study is to obtain the maximum value of range query for any fixed maximum decomposition levell (the number of input data is 2l). According to equation (26), we have(32)σsumMax2=maxS2⋅14l+∑nk,i∈N\nl,014kαnk,i−βnk,i2⋅3σ2.In equation (32), the given parameter is l. To compute the value of σsumMax2, we need to calculate any range query interval S=SL,SR in all data and obtain the count αck,i and βck,i using equations (30) and (31). We give the pseudocode of computing σsumMax2 as follows:Algorithm 1: Compute σ2sumMaxfor fix l (l ≥ 2).
Input: the maximum decomposition level lOutput:σ2sumMax, SL and SR (for σ2sumMax)(1)
σ2sumMax = 0(2)
ForSL = 0 to 2l−1(3)
ForSR = SL to 2l−1(4)
sum = 0(5)
Fork = 1 to l(6)
Fori = 1 to 2l−k(7)
ComputeαL, αR, βL, βR of nk, i using equations (38) and (39)(8)
IfSR < αL or SL > αR then α (nk, i) = 0(9)
ElseifSL ≥ αL and SR ≤ αR then α (nk, i) = SR − SL + 1(10)
ElseifSL < αL and SR > αR then α (nk, i) = αR − αL + 1(11)
ElseifSL < αL and αL ≤ SR ≤ αR then α (nk, i) = SR − αL + 1(12)
ElseifSR > αR and αL ≤ SL ≤ αR then α (nk, i) = αR − SL + 1(13)
End If(14)
IfSR < βL or SL > βR then β (nk, i) = 0(15)
ElseifSL ≥ βL and SR ≤ βR then β (nk, i) = SR − SL + 1(16)
ElseifSL < βL and SR > βR then β (nk, i) = βR − βL + 1(17)
ElseifSL < βL and βL ≤ SR ≤ βR then β (nk, i) = SR − βL + 1(18)
ElseifSR > βR and βL ≤ SL ≤ βR then β (nk, i) = βR − SL + 1(19)
End If(20)
Computesum = sum + (1/4k) (α (nk, i) − β (nk, i))2(21)
End For(22)
End For(23)
Computeσ2sum using sum and (26)(24)
Ifσ2sum > σ2sumMax(25)
σ2sumMax = σ2sum(26)
End IF(27)
End For(28)
End For(29)
Importσ2sumMax, SL and SR.Algorithm 1 illustrates the details of the algorithm of computingσ2sumMax for fix l (l ≥ 2). Step 1 is the initialization of σ2sumMax. Steps 2 to 3 are the range loop of SL and SR. Step 5 is the loop of the subscript of decomposition level k. Step 6 is the loop of the subscript of the wavelet coefficient in kth decomposition level. Step 7 is the computation of the αL, αR, βL, and βR of nk, i. Steps 8 to 13 denote the computation of α (nk, i). Steps 14 to 19 denote the computation of β (nk, i). Step 20 is the computation of right part of σ2sum using equation (26). Step 23 is the computation of σ2sum using equation (26). Steps 24 to 26 denote the computation of σ2sumMax using equation (34). Step 29 denotes the output of Algorithm 1.According to Algorithm 1, we calculate the values ofσ2sumMax, SL, and SR, as listed in Table 4.Table 4
Max-variance of range query via Haar wavelet and Gaussian mechanism (l from 2 to 14).
lσ2sumMax (∗σ2)SLSRSR − SL + 123.00000003433.56250016644.2656251141454.9101563282665.5869145585476.2482911111610686.9175422123421497.58290143468426108.25021785938854118.91655817118761706129.583388341375434141310.249973683750868261410.91668013651501813654In Table4, SR − SL + 1 denotes the length of interval for the σ2sumMax. It will take a very long time to compute the σ2sumMax using Algorithm 1 when l>14, so we need to find some method to speed up Algorithm 1.


### 4.3. Speeding Algorithm for Computing the Maximum Variance of Range Query

Observing the values ofSL and SR in Table 4, we give some statistical rules to compute them directly in Table 5.Table 5
Statistic results ofSL and SR.
lSLSR203310 × 2 + 163 × 2411 × 2 − 1146 × 2 + 2531 × 2 + 12814 × 2653 × 2 − 15828 × 2 + 27115 × 2 + 111658 × 282111 × 2 − 1234116 × 2 + 294321 × 2 + 1468234 × 2108543 × 2 − 1938468 × 2 + 21117185 × 2 + 11876938 × 212341171 × 2 − 137541876 × 2 + 213683341 × 2 + 175083754 × 2141365683 × 2 − 1150187508 × 2 + 2According to Table5, we can compute σ2sumMax using the following algorithm:Algorithm 2: Compute σ2sumMax,l for any l (l ≥ 2).
Input:Output: l, σ2sumMax,l, SL and SR (for l and σ2sumMax,l)(1)
SL = 0, SR = 3 (for l = 2)(2)
Forl = 3 to 30(3)
Ifl is odd then(4)
SL = SL× 2 + 1, SR = SR× 2(5)
Elseifl is even then(6)
SL = SL× 2 − 1, SR = SR× 2 + 2(7)
End If(8)
σ2sumMax,l = 0(9)
sum = 0(10)
Fork = 1 to l(11)
Fori = 1 to 2l−k(12)
ComputeαL, αR, βL, βR of nk, i using equations (38) and (39)(13)
IfSR < αL or SL > αR then α (nk, i) = 0(14)
ElseifSL ≥ αL and SR ≤ αR then α (nk, i) = SR − SL + 1(15)
ElseifSL < αL and SR > αR then α (nk, i) = αR − αL + 1(16)
ElseifSL < αL and αL ≤ SR ≤ αR then α (nk, i) = SR − αL + 1(17)
ElseifSR > αR and αL ≤ SL≤ αR then α (nk, i) = αR − SL + 1(18)
End If(19)
IfSR < βL or SL > βR then β (nk, i) = 0(20)
ElseifSL ≥ βL and SR ≤ βR then β (nk, i) = SR − SL + 1(21)
ElseifSL < βL and SR > βR then β (nk, i) = βR − βL + 1(22)
ElseifSL < βL and βL ≤ SR ≤ βR then β (nk, i) = SR − βL + 1(23)
ElseifSR > βR and βL ≤ SL ≤ βR then β (nk, i) = βR − SL + 1(24)
End If(25)
Computesum = sum + (1/4k) (α (nk, i) − β (nk, i))2(26)
End For(27)
End For(28)
Computeσ2sum using sum and (26)(29)
σ2sumMax,l = σ2sum(30)
Importl, σ2sumMax,l, SL and SR(31)
End For.Algorithm 2 illustrates the details of the algorithm of computingσ2sumMax,l for any l (l ≥ 2). Step 1 is the initialization of SL and SR. Step 2 is the loop of the maximum decomposition level l. Steps 3 to 7 denote the computation of SL and SR according to the maximum decomposition level l. Step 10 is the loop of the subscript of decomposition level k. Step 11 is the loop of the subscript of the wavelet coefficient in kth decomposition level. Step 12 is the computation of the αL, αR, βL, and βR of nk, i. Steps 13 to 18 denote the computation of α (nk, i). Steps 19 to 24 denote the computation of β (nk, i). Step 25 is the computation of right part of σ2sum using equation (26). Step 28 is the computation of σ2sum using equation (26). Step 30 denotes the output of Algorithm 2 for any l.SL and SR can also be given directly by simplifying the results in Table 5.Ifl is an even number,(33)SL=2l−2−13,SR=11×2l−2−23.Ifl is an odd number,(34)SL=2l−2+13,SR=11×2l−2−43.Therefore, we give the values ofσ2sumMax, SL, SR, and SR − SL + 1 for l from 2 to 30 in Table 6.Table 6
Max-variance of range query via Haar wavelet and Gaussian mechanism (anyl).
lσ2sumMax (∗σ2)SLSRSR − SL + 123.00000003433.56250016644.2656251141454.9101563282665.5869145585476.2482911111610686.9175422123421497.58290143468426108.25021785938854118.91655817118761706129.583388341375434141310.249973683750868261410.916680136515018136541511.583327273130036273061612.250003546160074546141712.916665109231201481092261813.583334218452402982184541914.250000436914805964369062014.916667873819611948738142115.583333174763192238817476262216.250000349525384477834952542316.916667699051768955669905062417.583333139810115379114139810142518.250000279620330758228279620262618.916667559240561516458559240542719.583333111848111230329161118481062820.250000223696212460658342236962142920.916667447392434921316684473924263021.58333389478485984263338894784854In Table6, SL and SR denote the left and right points of the range query interval when the σ2sumMax is met. SR − SL + 1 denotes the length of interval for the σ2sumMax. In Table 6, we observe that σ2sumMax will increase about (2/3) σ2 if the parameter l increases 1.


### 4.4. Coarse Estimation of the Maximum Variance of Range Query

In previous sections, the maximum variance of range queries via Gaussian mechanism and Haar wavelet transform is given for anyl. But it is obtained using a computer program, not from a function expression. In this section, the coarse estimation of the maximum variance is given in Theorem 6, and it is a function expression with parameters l and σ2.Theorem 6 (Coarse estimation of the maximum variance).
LetN be a set of independent Gaussian noise nk,i∈N with a variance 3σ2/4k, which is injected into one-dimensional Haar wavelet coefficients and approximate coefficient (Figure 3). Suppose l=log2N, that means the number of Gaussian noise injected into Haar wavelet coefficients and approximate coefficient is 2l (the number of input data is also 2l). Let M be the noisy data reconstructed from C + N (C is the set of one-dimensional Haar wavelet coefficients of the input data, refer to Figure 2). Then, for any range query answered using M, the variance of noise in the answer is at most 6l+9/4σ2.Proof.
Referring to Figure3 and equation (26), we observe that for any noise nk,i, if none of the leaves under nk,i is contained in S, then there is αnk,i=βnk,i=0. On the other hand, if all leaves under nk,i are covered by S, then αnk,i=βnk,i=2k−1. Therefore, αnk,i−βnk,i≠0, if and only if the left or right subtree of nk,i partially intersects S. At any level of the decomposition tree except for the lth level, there exist at most two such noises. At the level l, at most one such noise that letting the condition αnk,i−βnk,i≠0 be sufficient.
Considering a noisenk,i at level k (k∈1,l), such that αnk,i−βnk,i≠0. Since the left (right) subtree of nk,i contains at most 2k−1 leaves, we have αnk,i,βnk,i∈0,2k−1. So, there is αnk,i−βnk,i≤2k−1. Therefore, the variance of the range query about the noise nk,ik∈1,l at most is(35)αnk,i−βnk,i2⋅3σ24k≤4k−1⋅3σ24k=3σ2/4.
On the other hand, the noise in the approximate coefficient (nl,0) has a variance at most:(36)2l2⋅3σ24l=4l⋅3σ24l=3σ2.
Therefore, the total variance injected into wavelet coefficients of 1 tol − 1 level is 2⋅l−1⋅3σ2/4, and the variance injected into wavelet coefficients of level l is 1⋅3σ2/4. According to equation (26), the variance of noise at most is(37)3σ2+2•l−1⋅3σ24+1•3σ24=6l+94σ2,which completes the proof.
This conclusion in Theorem6 can also be obtained by observing Table 2. Now, we give the intuitive explanation of Theorem 6.
According to Table2, we can give a coarse estimation of the maximum variance of range query. In Table 2, we insert a row at the bottom to calculate the maximum variance sum for each column. The new table is shown as follows.
In Table7, each value of the last row is given by calculating the maximum sum of variance of some continued parts for each column according to Theorem 3. For example, the value of column 2 in the last row, 3σ2, is calculated by range from n0 to n7:(38)8n3,0∼8Gauss3σ243=Gauss82⋅3σ243=Gauss3σ2.
The value of column 3 in the last row, 3σ2/4, is calculated by range from n0 to n3 or from n4 to n7:(39)±4n3,1∼4Gauss3σ243=Gauss42⋅3σ243=Gauss3σ24.
The value of column 4 in the last row, 3σ2/2, is calculated by range from n2 to n5:(40)−2n2,1+2n2,2∼2Gauss3σ242+2Gauss3σ242,∼Gauss22⋅3σ242+Gauss22⋅3σ242,∼Gauss2⋅22⋅3σ242,∼Gauss3σ22.
The value of column 5 in the last row, 3σ2/2, is calculated by range from n1 to n2 or from n3 to n4 or from n5 to n6:(41)−n1,1+n1,2∼Gauss3σ2/4+3σ2/4=Gauss3σ2/2−n1,2+n1,3∼Gauss3σ2/4+3σ2/4=Gauss3σ2/2−n1,3+n1,4∼Gauss3σ2/4+3σ2/4=Gauss3σ2/2.
Therefore, we can obtain an estimation of the maximum variance of range query as follows:(42)σsumMaxEstim2=3σ2+34σ2+32σ2+32σ2=274σ2=6∗3+94σ2.
In Table7, the wavelet decomposition level is 3 (the number of input data is 23). Supposing that the decomposition level is l, then we can give an estimation of the maximum variance of range query:(43)σsumMaxEstim2=6l+94σ2.
Note that equation (43) gives the same result with the conclusion in Theorem 6.
Comparing the estimation maximum variances (equation (43)) with the real maximum variances (Table 6), we find that(44)σsumMax2≪σsumMaxEstim2.
σsumMaxEstim2 provides a function expression using parameters l and σ2 for the maximum variance of range query via Haar wavelet transform, but it has a very large error comparing the real maximum variance, comparing equation (43) with Table 6. Therefore, for the analysis of the practical applications, we prefer to use the maximum variance σ2sumMax, as listed in Table 6.Table 7
Coarse estimation of max-variance for range query.
n0=n3, 0+n3, 1+n2, 1+n1, 1n1=n3, 0+n3, 1+n2, 1−n1, 1n2=n3, 0+n3, 1−n2, 1+n1, 2n3=n3, 0+n3, 1−n2, 1−n1, 2n4=n3, 0−n3, 1+n2, 2+n1, 3n5=n3, 0−n3, 1+n2, 2−n1, 3n6=n3, 0−n3, 1−n2, 2+n1, 4n7=n3, 0−n3, 1−n2, 2−n1, 4nk,i∼Gauss (3σ2/43)Gauss (3σ2/43)Gauss (3σ2/42)Gauss (3σ2/41)σ2sumMax=3σ2+3σ2/4+3σ2/2+3σ2/2


## 4.1. Computing Method for the Variance of Range Query

In Figure3, we choose the Gaussian noise and inject them into the approximate coefficient and each wavelet coefficient. The variance of Gaussian noise injected into approximate coefficient is 3σ2/43. The variance of Gaussian noise injected into each wavelet coefficient is 3σ2/4k for level kk∈1,3. The relationship between decomposition level and variance of noise is listed in Table 3.Table 3
Noise variance and decomposition levelk.
kVariance of noiseNumber of wavelet coefficients33σ2/4323 − 323σ2/4223 − 213σ2/4123 − 1The noise-sum of range query via Haar wavelet transform for intervalS can be given by the following equation (Figure 3):(25)nsum=S⋅nl,0+∑nk,i∈N\nl,0nk,i⋅αnk,i−βnk,i,where S is the interval of any range query, nk,i presents the ith noise injected into wavelet coefficient in kth decomposition level, αnk,i denotes the number of left leaves in the left subtree of nk,i that are contained in S, and βnk,i denotes the number of right leaves in the right subtree of nk,i that are contained in S (Figure 3).Now we analyze the noise variance of range query. According to equation (20), we know that the noise injected into approximate coefficient is nl,0 and its variance is 3σ2/4l; the noise injected into wavelet coefficient is nk,i and its variance is 3σ2/4k. Therefore, according to Theorem 3, we can compute the noise-variance of range query by replacing nl,0 and nk,i with 3σ2/4l and 3σ2/4k in equation (25), respectively.(26)σsum2=S2⋅3σ24l+∑nk,i∈N\nl,03σ24kαnk,i−βnk,i2=S2⋅14l+∑nk,i∈N\nl,014kαnk,i−βnk,i2⋅3σ2.To compute the value ofσsum2, we need to calculate the values of αnk,i and βnk,i firstly. In Figure 3, the length of interval of leaves in the subtree of nk,i is 2k. The left point of this interval has the subscript i−1⋅2k and the right point of this interval has the subscript i⋅2k−1. Therefore, the subtree of nk,i has the subscript interval of leaves.(27)Snk,i=i−1⋅2k,i⋅2k−1.For example, the wavelet coefficientn2,2 in Figure 3 has the subscript interval of leaves [4, 7].According to equation (27), we can obtain the left-half interval αL,αRand right-half interval βL,βR of S_nk,i:(28)αL,αR=i−1⋅2k,i⋅2k−2k−1−1,βL,βR=i⋅2k−2k−1,i⋅2k−1.Therefore,αnk,i and βnk,i can be given by computing the number of intersection between S and αL,αR, S and βL,βR, respectively.(29)αnk,i=S∩αL,αR,βnk,i=S∩βL,βR.LetS=SL,SR, where SL and SR denote the left and right points of the given range query interval, respectively. Therefore, we have(30)αnk,i=SL,SR∩αL,αR,(31)βnk,i=SL,SR∩βL,βR,where k∈1,l and i∈1,2l−k (Figure 3).


## 4.2. Maximum Variance of Range Query

The aim of this study is to obtain the maximum value of range query for any fixed maximum decomposition levell (the number of input data is 2l). According to equation (26), we have(32)σsumMax2=maxS2⋅14l+∑nk,i∈N\nl,014kαnk,i−βnk,i2⋅3σ2.In equation (32), the given parameter is l. To compute the value of σsumMax2, we need to calculate any range query interval S=SL,SR in all data and obtain the count αck,i and βck,i using equations (30) and (31). We give the pseudocode of computing σsumMax2 as follows:Algorithm 1: Compute σ2sumMaxfor fix l (l ≥ 2).
Input: the maximum decomposition level lOutput:σ2sumMax, SL and SR (for σ2sumMax)(1)
σ2sumMax = 0(2)
ForSL = 0 to 2l−1(3)
ForSR = SL to 2l−1(4)
sum = 0(5)
Fork = 1 to l(6)
Fori = 1 to 2l−k(7)
ComputeαL, αR, βL, βR of nk, i using equations (38) and (39)(8)
IfSR < αL or SL > αR then α (nk, i) = 0(9)
ElseifSL ≥ αL and SR ≤ αR then α (nk, i) = SR − SL + 1(10)
ElseifSL < αL and SR > αR then α (nk, i) = αR − αL + 1(11)
ElseifSL < αL and αL ≤ SR ≤ αR then α (nk, i) = SR − αL + 1(12)
ElseifSR > αR and αL ≤ SL ≤ αR then α (nk, i) = αR − SL + 1(13)
End If(14)
IfSR < βL or SL > βR then β (nk, i) = 0(15)
ElseifSL ≥ βL and SR ≤ βR then β (nk, i) = SR − SL + 1(16)
ElseifSL < βL and SR > βR then β (nk, i) = βR − βL + 1(17)
ElseifSL < βL and βL ≤ SR ≤ βR then β (nk, i) = SR − βL + 1(18)
ElseifSR > βR and βL ≤ SL ≤ βR then β (nk, i) = βR − SL + 1(19)
End If(20)
Computesum = sum + (1/4k) (α (nk, i) − β (nk, i))2(21)
End For(22)
End For(23)
Computeσ2sum using sum and (26)(24)
Ifσ2sum > σ2sumMax(25)
σ2sumMax = σ2sum(26)
End IF(27)
End For(28)
End For(29)
Importσ2sumMax, SL and SR.Algorithm 1 illustrates the details of the algorithm of computingσ2sumMax for fix l (l ≥ 2). Step 1 is the initialization of σ2sumMax. Steps 2 to 3 are the range loop of SL and SR. Step 5 is the loop of the subscript of decomposition level k. Step 6 is the loop of the subscript of the wavelet coefficient in kth decomposition level. Step 7 is the computation of the αL, αR, βL, and βR of nk, i. Steps 8 to 13 denote the computation of α (nk, i). Steps 14 to 19 denote the computation of β (nk, i). Step 20 is the computation of right part of σ2sum using equation (26). Step 23 is the computation of σ2sum using equation (26). Steps 24 to 26 denote the computation of σ2sumMax using equation (34). Step 29 denotes the output of Algorithm 1.According to Algorithm 1, we calculate the values ofσ2sumMax, SL, and SR, as listed in Table 4.Table 4
Max-variance of range query via Haar wavelet and Gaussian mechanism (l from 2 to 14).
lσ2sumMax (∗σ2)SLSRSR − SL + 123.00000003433.56250016644.2656251141454.9101563282665.5869145585476.2482911111610686.9175422123421497.58290143468426108.25021785938854118.91655817118761706129.583388341375434141310.249973683750868261410.91668013651501813654In Table4, SR − SL + 1 denotes the length of interval for the σ2sumMax. It will take a very long time to compute the σ2sumMax using Algorithm 1 when l>14, so we need to find some method to speed up Algorithm 1.


## 4.3. Speeding Algorithm for Computing the Maximum Variance of Range Query

Observing the values ofSL and SR in Table 4, we give some statistical rules to compute them directly in Table 5.Table 5
Statistic results ofSL and SR.
lSLSR203310 × 2 + 163 × 2411 × 2 − 1146 × 2 + 2531 × 2 + 12814 × 2653 × 2 − 15828 × 2 + 27115 × 2 + 111658 × 282111 × 2 − 1234116 × 2 + 294321 × 2 + 1468234 × 2108543 × 2 − 1938468 × 2 + 21117185 × 2 + 11876938 × 212341171 × 2 − 137541876 × 2 + 213683341 × 2 + 175083754 × 2141365683 × 2 − 1150187508 × 2 + 2According to Table5, we can compute σ2sumMax using the following algorithm:Algorithm 2: Compute σ2sumMax,l for any l (l ≥ 2).
Input:Output: l, σ2sumMax,l, SL and SR (for l and σ2sumMax,l)(1)
SL = 0, SR = 3 (for l = 2)(2)
Forl = 3 to 30(3)
Ifl is odd then(4)
SL = SL× 2 + 1, SR = SR× 2(5)
Elseifl is even then(6)
SL = SL× 2 − 1, SR = SR× 2 + 2(7)
End If(8)
σ2sumMax,l = 0(9)
sum = 0(10)
Fork = 1 to l(11)
Fori = 1 to 2l−k(12)
ComputeαL, αR, βL, βR of nk, i using equations (38) and (39)(13)
IfSR < αL or SL > αR then α (nk, i) = 0(14)
ElseifSL ≥ αL and SR ≤ αR then α (nk, i) = SR − SL + 1(15)
ElseifSL < αL and SR > αR then α (nk, i) = αR − αL + 1(16)
ElseifSL < αL and αL ≤ SR ≤ αR then α (nk, i) = SR − αL + 1(17)
ElseifSR > αR and αL ≤ SL≤ αR then α (nk, i) = αR − SL + 1(18)
End If(19)
IfSR < βL or SL > βR then β (nk, i) = 0(20)
ElseifSL ≥ βL and SR ≤ βR then β (nk, i) = SR − SL + 1(21)
ElseifSL < βL and SR > βR then β (nk, i) = βR − βL + 1(22)
ElseifSL < βL and βL ≤ SR ≤ βR then β (nk, i) = SR − βL + 1(23)
ElseifSR > βR and βL ≤ SL ≤ βR then β (nk, i) = βR − SL + 1(24)
End If(25)
Computesum = sum + (1/4k) (α (nk, i) − β (nk, i))2(26)
End For(27)
End For(28)
Computeσ2sum using sum and (26)(29)
σ2sumMax,l = σ2sum(30)
Importl, σ2sumMax,l, SL and SR(31)
End For.Algorithm 2 illustrates the details of the algorithm of computingσ2sumMax,l for any l (l ≥ 2). Step 1 is the initialization of SL and SR. Step 2 is the loop of the maximum decomposition level l. Steps 3 to 7 denote the computation of SL and SR according to the maximum decomposition level l. Step 10 is the loop of the subscript of decomposition level k. Step 11 is the loop of the subscript of the wavelet coefficient in kth decomposition level. Step 12 is the computation of the αL, αR, βL, and βR of nk, i. Steps 13 to 18 denote the computation of α (nk, i). Steps 19 to 24 denote the computation of β (nk, i). Step 25 is the computation of right part of σ2sum using equation (26). Step 28 is the computation of σ2sum using equation (26). Step 30 denotes the output of Algorithm 2 for any l.SL and SR can also be given directly by simplifying the results in Table 5.Ifl is an even number,(33)SL=2l−2−13,SR=11×2l−2−23.Ifl is an odd number,(34)SL=2l−2+13,SR=11×2l−2−43.Therefore, we give the values ofσ2sumMax, SL, SR, and SR − SL + 1 for l from 2 to 30 in Table 6.Table 6
Max-variance of range query via Haar wavelet and Gaussian mechanism (anyl).
lσ2sumMax (∗σ2)SLSRSR − SL + 123.00000003433.56250016644.2656251141454.9101563282665.5869145585476.2482911111610686.9175422123421497.58290143468426108.25021785938854118.91655817118761706129.583388341375434141310.249973683750868261410.916680136515018136541511.583327273130036273061612.250003546160074546141712.916665109231201481092261813.583334218452402982184541914.250000436914805964369062014.916667873819611948738142115.583333174763192238817476262216.250000349525384477834952542316.916667699051768955669905062417.583333139810115379114139810142518.250000279620330758228279620262618.916667559240561516458559240542719.583333111848111230329161118481062820.250000223696212460658342236962142920.916667447392434921316684473924263021.58333389478485984263338894784854In Table6, SL and SR denote the left and right points of the range query interval when the σ2sumMax is met. SR − SL + 1 denotes the length of interval for the σ2sumMax. In Table 6, we observe that σ2sumMax will increase about (2/3) σ2 if the parameter l increases 1.


## 4.4. Coarse Estimation of the Maximum Variance of Range Query

In previous sections, the maximum variance of range queries via Gaussian mechanism and Haar wavelet transform is given for anyl. But it is obtained using a computer program, not from a function expression. In this section, the coarse estimation of the maximum variance is given in Theorem 6, and it is a function expression with parameters l and σ2.Theorem 6 (Coarse estimation of the maximum variance).
LetN be a set of independent Gaussian noise nk,i∈N with a variance 3σ2/4k, which is injected into one-dimensional Haar wavelet coefficients and approximate coefficient (Figure 3). Suppose l=log2N, that means the number of Gaussian noise injected into Haar wavelet coefficients and approximate coefficient is 2l (the number of input data is also 2l). Let M be the noisy data reconstructed from C + N (C is the set of one-dimensional Haar wavelet coefficients of the input data, refer to Figure 2). Then, for any range query answered using M, the variance of noise in the answer is at most 6l+9/4σ2.Proof.
Referring to Figure3 and equation (26), we observe that for any noise nk,i, if none of the leaves under nk,i is contained in S, then there is αnk,i=βnk,i=0. On the other hand, if all leaves under nk,i are covered by S, then αnk,i=βnk,i=2k−1. Therefore, αnk,i−βnk,i≠0, if and only if the left or right subtree of nk,i partially intersects S. At any level of the decomposition tree except for the lth level, there exist at most two such noises. At the level l, at most one such noise that letting the condition αnk,i−βnk,i≠0 be sufficient.
Considering a noisenk,i at level k (k∈1,l), such that αnk,i−βnk,i≠0. Since the left (right) subtree of nk,i contains at most 2k−1 leaves, we have αnk,i,βnk,i∈0,2k−1. So, there is αnk,i−βnk,i≤2k−1. Therefore, the variance of the range query about the noise nk,ik∈1,l at most is(35)αnk,i−βnk,i2⋅3σ24k≤4k−1⋅3σ24k=3σ2/4.
On the other hand, the noise in the approximate coefficient (nl,0) has a variance at most:(36)2l2⋅3σ24l=4l⋅3σ24l=3σ2.
Therefore, the total variance injected into wavelet coefficients of 1 tol − 1 level is 2⋅l−1⋅3σ2/4, and the variance injected into wavelet coefficients of level l is 1⋅3σ2/4. According to equation (26), the variance of noise at most is(37)3σ2+2•l−1⋅3σ24+1•3σ24=6l+94σ2,which completes the proof.
This conclusion in Theorem6 can also be obtained by observing Table 2. Now, we give the intuitive explanation of Theorem 6.
According to Table2, we can give a coarse estimation of the maximum variance of range query. In Table 2, we insert a row at the bottom to calculate the maximum variance sum for each column. The new table is shown as follows.
In Table7, each value of the last row is given by calculating the maximum sum of variance of some continued parts for each column according to Theorem 3. For example, the value of column 2 in the last row, 3σ2, is calculated by range from n0 to n7:(38)8n3,0∼8Gauss3σ243=Gauss82⋅3σ243=Gauss3σ2.
The value of column 3 in the last row, 3σ2/4, is calculated by range from n0 to n3 or from n4 to n7:(39)±4n3,1∼4Gauss3σ243=Gauss42⋅3σ243=Gauss3σ24.
The value of column 4 in the last row, 3σ2/2, is calculated by range from n2 to n5:(40)−2n2,1+2n2,2∼2Gauss3σ242+2Gauss3σ242,∼Gauss22⋅3σ242+Gauss22⋅3σ242,∼Gauss2⋅22⋅3σ242,∼Gauss3σ22.
The value of column 5 in the last row, 3σ2/2, is calculated by range from n1 to n2 or from n3 to n4 or from n5 to n6:(41)−n1,1+n1,2∼Gauss3σ2/4+3σ2/4=Gauss3σ2/2−n1,2+n1,3∼Gauss3σ2/4+3σ2/4=Gauss3σ2/2−n1,3+n1,4∼Gauss3σ2/4+3σ2/4=Gauss3σ2/2.
Therefore, we can obtain an estimation of the maximum variance of range query as follows:(42)σsumMaxEstim2=3σ2+34σ2+32σ2+32σ2=274σ2=6∗3+94σ2.
In Table7, the wavelet decomposition level is 3 (the number of input data is 23). Supposing that the decomposition level is l, then we can give an estimation of the maximum variance of range query:(43)σsumMaxEstim2=6l+94σ2.
Note that equation (43) gives the same result with the conclusion in Theorem 6.
Comparing the estimation maximum variances (equation (43)) with the real maximum variances (Table 6), we find that(44)σsumMax2≪σsumMaxEstim2.
σsumMaxEstim2 provides a function expression using parameters l and σ2 for the maximum variance of range query via Haar wavelet transform, but it has a very large error comparing the real maximum variance, comparing equation (43) with Table 6. Therefore, for the analysis of the practical applications, we prefer to use the maximum variance σ2sumMax, as listed in Table 6.Table 7
Coarse estimation of max-variance for range query.
n0=n3, 0+n3, 1+n2, 1+n1, 1n1=n3, 0+n3, 1+n2, 1−n1, 1n2=n3, 0+n3, 1−n2, 1+n1, 2n3=n3, 0+n3, 1−n2, 1−n1, 2n4=n3, 0−n3, 1+n2, 2+n1, 3n5=n3, 0−n3, 1+n2, 2−n1, 3n6=n3, 0−n3, 1−n2, 2+n1, 4n7=n3, 0−n3, 1−n2, 2−n1, 4nk,i∼Gauss (3σ2/43)Gauss (3σ2/43)Gauss (3σ2/42)Gauss (3σ2/41)σ2sumMax=3σ2+3σ2/4+3σ2/2+3σ2/2


## 5. Experimental Verification

This section introduces the experimental verification of the proposed framework, that is, the computing of maximum variance for range query based on Gaussian mechanism and lifting Haar wavelet. We use the dataset age, which contains census records of individuals from the United States. The age has 107, 974, and 787 records, each of which corresponds to the age of an individual, extracted from the IPUM’s census data of the United States [40]. The ages range from 0 to 135 and just have 128 values (ages 121, 123, 127, 128, 131, 132, 133, and 134 are empty). We count the number of each age and give the histogram of age as the input file of our experiments. Given a query length L, we test all the possible range queries with length L and report the maximum variance of the range query for input data.The noise injected into the input data via Gaussian mechanism is Gaussian noise. The variance of Gaussian noise is the sample variance. Therefore, the sample variance is adopted in this study and is computed by the following equation:(45)Varn=1m−1∑i=1mni−1m∑j=1mnj2,where ni (or nj) is the noise injected into the input data and m is the number of the input data.We research the maximum variance of the range query of noise whenε chosen in the set {0.5, 0.75, 1.0, 1.25} and δ chosen in the set {0.1, 0.01, 0.001}. For each special ε, we draw the maximum variance of the range count of noise using Gaussian mechanism and Gaussian mechanism with Haar wavelet transform when δ is equal to 0.1, 0.01, and 0.001.For anyε and δ, we can calculate the σ of Gaussian noise using the equation σ=2ln1.25/δ/ε in Theorem 5, and the results are given in Table 8.Table 8
σ for some ε and δ.
εδσ0.50.14.49510.50.016.21500.50.0017.55300.750.12.99670.750.014.14330.750.0015.03531.00.12.24751.00.013.10751.00.0013.77651.250.11.79801.250.012.48601.250.0013.0212To compute the variance, we inject the Gaussian noise into the input data or the Haar wavelet coefficients 10000 times. To compute the maximum variance of the range query with fixedε and δ, each variance of the range query for range size k needs to be computed firstly. Then, the maximum value of variance for range size k can be given by comparing all the variance of the k-range queries.For input data with length 128 (such as 128 histogram), we can draw the maximum variance diagram of the range query using Gaussian mechanism and Gaussian mechanism with Haar wavelet transform for any range sizes, as shown in Figure5.Figure 5
Maximum variance of range query using Gaussian mechanism and Gaussian mechanism with Haar wavelet on age (the United States). (a)ε = 0.5. (b) ε = 0.75. (c) ε = 1.0. (d) ε = 1.25.
(a)(b)(c)(d)In Figure5, “Gauss” means injecting noise into each histogram data via Gaussian mechanism directly and then gets the noise of range query by the operation of addition. First, “GaussWave” denotes injecting noise into the lifting Haar wavelet coefficients using Theorem 5. Second, the noise injected into each histogram is obtained by the inverse wavelet transform. Finally, the range query for any range size is obtained by injecting the noise together.In Figure5, we observe that the maximum variance is increasing linearly with the “range size” for “Gauss.” In Figure 5, for any ε and δ, the maximum variance of the noise using “GaussWave” method is far less than the noise using “Gauss” method.To observe the variation tendency of “GaussWave” in Figure5, we just draw the maximum variance diagram of the range query using Gaussian mechanism with Haar wavelet transform, as shown in Figure 6.Figure 6
Maximum variance of range query using Gaussian mechanism with Haar wavelet on age (the United States). (a)ε = 0.5. (b) ε = 0.75. (c) ε = 1.0. (d) ε = 1.25.
(a)(b)(c)(d)In Figure6, for any ε and δ, the maximum variance of the noise using “GaussWave” method increases with the increase of range size before it gets the maximum value, and it will decrease with the increase of range size after it has gotten the maximum value.In Table6, we observe that the max-variance of range query via Gaussian mechanism with Haar wavelet is 6.248291 ∗ σ2 when l = 7 (27 = 128) and the length of interval is 106. Considering the value of σ in Table 8, we give the comparison of maximum value between experimental result and theoretical analysis for range query in Table 9.Table 9
Comparison of maximum value between experimental result and theoretical analysis for range 1 to 128.
εδRange sizeMax-valueσ2sumMaxDifference0.50.1106126.093366126.252493−0.1591270.50.01106240.611130241.347894−0.7367640.50.001106358.354318356.4513121.9030060.750.110656.95774056.11097100.8467690.750.01106109.807594107.2640052.5435890.750.001106161.471355158.4207083.0506471.00.110631.52139231.5617190−0.0403271.00.0110659.63794260.336974−0.6990321.00.00110686.00754889.112828−3.1052801.250.110620.46627920.1995000.2667791.250.0110638.35102138.615663−0.2646421.250.00110657.67823657.0322100.646026In Table9, the column “max-value” presents the experimental result of the maximum value of maximum variance for range query. The column “σ2sumMax” presents the result of theoretical analysis and computed using the formula σ2sumMax = 6.248291 ∗ σ2. The last column “difference” is the difference of columns “max-value” and “σ2sumMax.” In Table 9, we find that the results of experiment and theoretical analysis are in substantial agreement.This section gives the experimental verification of the framework of the maximum variance computing for range query. This framework on privacy preserving is built using Gaussian mechanism and Haar wavelet. In Figure6, for any ε and δ, the maximum variance of the noise increases with the increase of range size before it gets the maximum value of 106, and it will decrease with the increase of range size after it has gotten the maximum value. In Table 9, the experimental value and the theoretical value of maximum variance for range count are compared, and the results show that they are in substantial agreement.


## 6. Conclusions

In this study, we proposed a new differential privacy framework via Haar wavelet transform and Gaussian mechanism for the range query. The theorems for how to inject Gaussian noise into the Haar wavelet coefficients are given. The noise of range query under the theoretical framework of Haar wavelet and Gaussian mechanism is analyzed. The algorithm to compute the maximum variance of any range query for any given parameterl is introduced. A coarse estimation of the maximum variance of range query using a function expression is given. The experimental results show that the maximum variance of the noise using Gaussian mechanism and Haar wavelet is far less than the noise using Gaussian mechanism. The experimental verification of the computing of maximum variance for range query based on lifting Haar wavelet and Gaussian mechanism is proposed, and the results show the experimental value and the theoretical value of maximum variance for range count are substantial agreement. For future work, we plan to apply our method to the privacy protection of histogram publication. Furthermore, we want to investigate how to assemble our method and machine learning algorithm, such as the decision tree and random forest.



---

*Source: 8139813-2022-09-12.xml*