# PLDP: Personalized Local Differential Privacy for Multidimensional Data Aggregation

Authors: Zixuan Shen; Zhihua Xia; Peipeng Yu
Journal: Security and Communication Networks
 (2021)

---

## Abstract

The collection of multidimensional crowdsourced data has caused a public concern because of the privacy issues. To address it, local differential privacy (LDP) is proposed to protect the crowdsourced data without much loss of usage, which is popularly used in practice. However, the existing LDP protocols ignore users’ personal privacy requirements in spite of offering good utility for multidimensional crowdsourced data. In this paper, we consider the personality of data owners in protection and utilization of their multidimensional data by introducing the notion of personalized LDP (PLDP). Specifically, we design personalized multiple optimized unary encoding (PMOUE) to perturb data owners’ data, which satisfiesϵtotal-PLDP. Then, the aggregation algorithm for frequency estimation on multidimensional data under PLDP is developed, which is described in two situations. Experiments are conducted on four real datasets, and the results show that the proposed aggregation algorithm yields high utility. Moreover, case studies with four real datasets demonstrate the efficiency and superiority of the proposed scheme.


---

## Body

## 1. Introduction

In big data era, companies and institutions have noticed the big value of the data and are highly motivated to collect high-dimensional crowdsourced data to make data-driven decisions. The collection and analysis of data are beneficial to companies as well as the society; however, the data owners’ privacy makes the biggest concern. In recent years, local differential privacy (LDP) [1, 2] has been found practical value in collection and utilization of data owners’ data with the privacy preserved. In an LDP scheme, the data owners perturb their sensitive data before data outsourcing and then report the perturbed data to the server. In this way, the server cannot infer the owners’ actual data with strong confidence, however, can still make the accurate estimation of data distribution as it was inferred from the unperturbed data. Considering the desirable properties of LDP, it has been adopted in practice and performs excellently. For example, Apple Inc. collects users’ emoji records to discover the popular emojis [3] under LDP. Microsoft also designs the LDP scheme to collect application telemetry to improve user experience [4].Although the existing LDP schemes are good solutions for data distribution estimation with privacy protected, they ignore data owners’ personal privacy requirements. Specifically, in most existing LDP schemes [5, 6], all the owners perturb their different dimensions of data with the same privacy budget, which is set by the server, while it is the truth that different data have a different importance to each owner. In the real world, data owners must have different privacy requirements for their data. Furthermore, if the privacy protection level provided by the server is lower than an owner’s need, the owner may be reluctant to share the data. Therefore, it is worth designing the LDP scheme with the personalized privacy allocation mechanism.In this paper, we propose a multidimensional joint distribution estimation scheme with the personalized local differential privacy (PLDP), in which each data owner has his personal privacy requirement for each dimension of data. Specifically, the server sets an average privacy budgetɛaverage to all of its data owners O = o1,o2,…,oN, and the owner oi can split and allocate mi×ɛaverage to each dimension of his mi-dimensional data personally. Then, the data of different dimensions of the owner oi will be perturbed with the different privacy budgets. The data owners need not to report their privacy allocation to the server, i.e., the server only holds data owners’ perturbed data and their total privacy budgets. Thus, a PLDP scheme provides stronger privacy assurance than the normal LDP scheme.Moreover, a single data owner may not have the data of all the dimensions required by the server. In our scheme, an owner is allowed to report the data in a part of the dimensions. But, in this way, it is likely that the record of some high-dimensional data could not exist. Then, it is difficult for the server to estimate such dimensions of data. To address it, an aggregation algorithm is developed for joint distribution estimation on multidimensional data under PLDP. The contributions can be summarized as follows:(1)
We propose a new privacy notion called personalized local differential privacy (PLDP), which allows personalized privacy protection for different inputs than LDP. It has higher security and is more personalized than traditional LDP.(2)
We design a perturbed mechanism personalized multiple optimized unary encoding (PMOUE) and develop the aggregation algorithm for frequency estimation on multidimensional data under PLDP to estimate the joint distribution of multidimensional data.(3)
We proposeɛw to measure the personalized privacy protection level of multidimensional data for a single data owner oi.(4)
Experiments on four real datasets validate the efficiency and superiority of PLDP. Compared with LoPub, PLDP outperforms it with high security, high privacy protection, considerable data utility, and low time consumption.


### 1.1. Roadmap

In Section2, we review previous work related to LDP. Then, we give the preliminaries of LDP in Section 3. In Section 4, we describe the problem statement, define the new notion PLDP, and compare it to the traditional LDP. Then, we design the perturbation mechanism PMOUE and develop the aggregation algorithm to estimate the joint distribution of multidimensional data under PLDP. Experimental results are shown in Section 5. Finally, we present the conclusions of this paper in Section 6.


## 1.1. Roadmap

In Section2, we review previous work related to LDP. Then, we give the preliminaries of LDP in Section 3. In Section 4, we describe the problem statement, define the new notion PLDP, and compare it to the traditional LDP. Then, we design the perturbation mechanism PMOUE and develop the aggregation algorithm to estimate the joint distribution of multidimensional data under PLDP. Experimental results are shown in Section 5. Finally, we present the conclusions of this paper in Section 6.


## 2. Related Work

Differential privacy is a rigorous mathematical definition of privacy for securely sharing the statistic of a dataset on a server [7]. When a requester requests a statistic value of a dataset, the server will calculate the value and then send a disturbed but usable value to the requester. An algorithm is said to be differentially private if the requester cannot infer any single data in the dataset by analyzing the statistic values. In a DP scheme, the server is supposed to be trusted and has all data owners’ raw data. However, in the big data era, the data on the server are collected from users. The collection of data provides much useful information to the public; however, the data owners’ privacy becomes the big concern as the server generally cannot be fully trusted in the real world. Accordingly, the local differential privacy (LDP) schemes are proposed, in which the owners perturb their data locally and then send the perturbed version to the server. With the perturbed data from data owners, the server can still estimate the distribution of the data.As the first application of LDP to a real-world problem, Erlingsson et al. [8] proposed RAPPOR to securely estimate the character frequency in a set of strings. Specifically, each data owner uses k hash functions to hash his string onto k Bloom filters [9]. Then, two randomized response (RR) mechanisms, i.e., permanent randomized response and instantaneous randomized response, are proposed to perturb the bits in k Bloom filters. After receiving the perturbed data from the data owners, the server combines the mapping matrix with the LASSO regression [10] to estimate the character frequency. Kim et al. [11] also used randomized response mechanism to collect indoor position records for estimating the density of the specified indoor area. Several fixed points are selected in the indoor area, and each position is represented by its nearest point and denoted as a binary string. Then, the binary string is perturbed by the RR mechanism and then reported. Some researchers tried to reduce the communication cost by reporting a randomly selected bit from the binary string. The bit is also perturbed by RR mechanism. Then, the maximum likelihood estimation [12] and LASSO regression [13] are utilized to the data frequency.The schemes mentioned above are designed for one-dimensional data. Considering the multidimensional data generally contains more valuable information, several LDP schemes for the multidimensional data are proposed recently. Ren et al. proposed an LDP scheme, named LoPub [14], to synthesize the high-dimensional dataset with the similar distribution to the real dataset. The data are encoded by Bloom filters and perturbed by RR mechanism as in [8]. In order to decrease the computation complexity, the authors tried to calculate the joint distribution of the small set of attributes at first and then calculate the joint distribution of the all attributes by multiplication. Specifically, the attributes with high mutual correlation are clustered together, generating the attribute clusters. The attribute clusters are considered to be independent of each other. Then, the joint attribute distribution within the clusters is calculated by the expectation-maximization algorithm [15] and LASSO regression. The joint distribution of all attributes is obtained by multiplying the distribution of all clusters. Zhang et al. proposed an LDP scheme, named CALM [16], to estimate marginal tables of multidimensional data. Instead of directly generating all marginal tables, the authors constructed many subsets of attributes and chose the randomization algorithm according to the marginal sizes. Expectation-maximization algorithm is used to estimate the marginal distribution. Since some attributes should exist in different subsets, the authors considered the marginal distributions to provide more accurate estimation.Some researchers considered that different data would have different privacy requirements. Gu et al. proposed an input-discriminative LDP scheme, in which the server sets different privacy budgets to attribute values. An input-discriminative unary encoding is designed to perturb the attribute value with the specified budgets. In [17, 18], the server provides several privacy budgets and owner can choose one budget for himself to perturb his data. Then, both the perturbed data and the selected budget are reported to the server. The server will estimate the distributions by grouping the data according to the budget. In [19], it is the data owner who decides the privacy budget for his own data; however, it still needs to report the privacy budget to the server for frequency estimation. The schemes [17–19] have tried to consider the personal privacy requirement, but all of them are designed for one-dimensional data. In addition, the server needs to know the privacy budgets that are applied to the disturbed data to estimate the data distribution, which would also expose privacy to the server.To sum up, there is still a gap in the research on the LDP schemes that support the personalized privacy requirement for multidimensional data. Our goal is to design a scheme where the data owners can choose and perturb their data personally and the server can make a good distribution estimation with such perturbed data.


## 3. Preliminaries

### 3.1. Differential Privacy

Differential privacy (DP) is a rigorous mathematical definition of privacy for securely sharing the statistic of a dataset on a server [7]. In a DP scheme, the data owners report their raw data to the trusted server. Then, the server sends a perturbed query result to the requester by adding noise, such as Laplace noise [20]. In this way, the requester is unable to infer much about any single data in the dataset. A formal definition of DP is presented as follows.Definition 1.
differential privacy (DP) [7]). For a given privacy budget ɛ∈R+, a randomized mechanism M satisfies ϵ-DP if and only if any neighboring dataset D, D′ differs in at most one record and all subsets Y ⊆ range (M) and it has(1)PrMD∈YPrMD′∈Y≤eɛ.


### 3.2. Local Differential Privacy

In DP schemes, the server is fully trusted and can hardly apply to the case of privacy-aware crowdsourced systems. Accordingly, the local differential privacy (LDP) scheme is proposed, in which the data owners perturb their data locally and then send the perturbed version to the server. After receiving the perturbed data from owners, the server can still estimate the distribution of the data without knowing much about the data of the single owner. The formal definition of DP can be described as follows.Definition 2.
local differential privacy (LDP) [2]). For a given privacy budget ɛ∈R+, a randomized mechanism M satisfies ɛ-LDP if and only if for any pair of inputs x, x′and any possible output y∈Range (M), it has(2)PrMx=yPrMx′=y≤eɛ.Theorem 1.
Sequential composition of LDP [21]). If the randomized mechanism Mi satisfies ɛi-LDP, for the given privacy budgets ɛi∈Ri+, i = 1, 2, ⋯, k. Then, their sequential combination M = M1,M2,…,Mk satisfies ∑i=1kɛi-LDP.Proof.
For any inputsx, x′, and output y, we have(3)PrMx=y=PrM1x1=y1PrM2x2=y2,…,PrMkxk=yk≤eɛ1PrM1x1′=y1eɛ2PrM2x2′=y2,…,eɛkPrMkxk′=yk=e∑i=1kɛiPrMx′=y.
According to Theorem1, a given total privacy budget ɛtotal can be split into ɛi with ɛtotal = ∑i=1kɛi, where each ϵi denotes the privacy budget of a randomized mechanism Mi.


### 3.3. Optimized Unary Encoding

#### 3.3.1. Randomized Response

Randomized response (RR) [22, 23] is a mainstream perturbation mechanism for LDP. The main idea is to give a random answer to a sensitive question. Accordingly, RR will disturb an input x to an output y as(4)Py|x=x,w.p.p,x′,w.p.1−p.Specifically, the interviewee gives the genuine answerx with probability p and gives the opposite answer x′ with probability 1-p. In this way, RR satisfies lnp/1−p-LDP.Considering RR only works for binary data, some perturbation mechanisms generalize and optimize it, such as direct encoding (DE) [24], histogram encoding (HE) [25], unary encoding (UE) [8, 26], and local hashing (LH) [6, 27].In UE, an inputx is encoded as a length-l binary vector, with only the bit corresponding to x set to 1. Then, the binary vector will be perturbed bit by bit with probability p and q as follows:(5)PrUExi=1=xi=1,w.p.p,xi=0,w.p.q.If UE usesp+q=1, it becomes symmetric unary encoding (SUE) [8]. If UE uses optimized choices of p and q, it becomes optimized unary encoding (OUE) [26].


#### 3.3.2. Optimized Unary Encoding

Optimized unary encoding (OUE) [26] converts the input x = i into a binary vector v = (0, …, 0, 1, 0 …, 0) with length-l, where the i-th bit is 1. Then, v is perturbed as follows:(6)Pryi=1|vi=1=p=12,Pryi=0|vi=1=1−p=12,Pryi=1|vi=0=q=1eɛ+1,Pryi=0|vi=0=1−q=eɛeɛ+1.In this way, OUE satisfiesϵ-LDP.Proof.
For any pair of inputsx and x′, we denote their corresponding vector as v and v′, respectively, and denote the output vector as y. Then, we have θ = Pry|v/Pry|v′ = ∏i=1lPryi|vi/Pryi|v′i. According to the OUE, there is only one ‘1’ bit in both the v and v′. Let us assume that v[s] = v′[t] = 1, and there are four different cases for θ since the vector y could have four different possible values, which is listed as follows:(7)θ=θ1=Prys=0|vs=1Pryt=0|vt=0Prys=0|v′s=0Pryt=0|v′t=1,ifys=0,yt=0,θ2=Prys=0|vs=1Pryt=1|vt=0Prys=0|v′s=0Pryt=1|v′t=1,ifys=0,yt=1,θ3=Prys=1|vs=1Pryt=0|vt=0Prys=1|v′s=0Pryt=0|v′t=1,ifys=1,yt=0,θ4=Prys=1|vs=1|Pryt=1|vt=0Prys=1|v′s=0Pryt=1|v′t=1,ifys=1,yt=1.
Then, according to Formula (6), we have(8)θ=θ1=1−p1−q1−q1−p=1,θ2=1−pq1−qp=q1−q,θ3=p1−qq1−p=1−qq,θ4=pqqp=1,and q=1/eɛ+1. Since ϵ is definitely a positive number, we have q<1/2. Then, it is derived that(9)θ≤θ3=1−qq=eɛ,which demonstrates that OUE satisfies ϵ-LDP.


### 3.4. Least Absolute Shrinkage and Selection Operator Regression

For real multidimensional data, its joint distribution may be sparse. To estimate the joint distribution of real multidimensional data, the least absolute shrinkage and selection operator (LASSO) regression is usually used. Since when solving a multivariate objective function as follows,(10)β^=minβy−Xβ22,where y is the label, X is the vector of an input sample, and β = (β1, β2, …, βm) is the vector of regression coefficients; the overfitting problem may occur. To address it, LASSO regression adds L1-norm as a penalty term after the objective function. Then, constructing a penalty function as follows,(11)β∗=minβy−Xβ22+λβ1,where λ is a data dependent parameter.In this way, when updating the regression coefficientβi to βi∗ with learning rate η, βi∗ = βi - η∂β∗/∂βi. Since ∂λβ1/∂βi = λ or -λ, the updated βi∗ is likely to be zero. In this way, LASSO regression forces the sum of the absolute value of the regression coefficients to be less than a fixed value, which keeps certain coefficients to be set to zero and accordingly results in a simpler model that does not include those zero coefficients. As a result, LASSO regression is quite suitable to solve the sparse linear regression because it can compress the coefficients of variables and make some regression coefficients become zero.


## 3.1. Differential Privacy

Differential privacy (DP) is a rigorous mathematical definition of privacy for securely sharing the statistic of a dataset on a server [7]. In a DP scheme, the data owners report their raw data to the trusted server. Then, the server sends a perturbed query result to the requester by adding noise, such as Laplace noise [20]. In this way, the requester is unable to infer much about any single data in the dataset. A formal definition of DP is presented as follows.Definition 1.
differential privacy (DP) [7]). For a given privacy budget ɛ∈R+, a randomized mechanism M satisfies ϵ-DP if and only if any neighboring dataset D, D′ differs in at most one record and all subsets Y ⊆ range (M) and it has(1)PrMD∈YPrMD′∈Y≤eɛ.


## 3.2. Local Differential Privacy

In DP schemes, the server is fully trusted and can hardly apply to the case of privacy-aware crowdsourced systems. Accordingly, the local differential privacy (LDP) scheme is proposed, in which the data owners perturb their data locally and then send the perturbed version to the server. After receiving the perturbed data from owners, the server can still estimate the distribution of the data without knowing much about the data of the single owner. The formal definition of DP can be described as follows.Definition 2.
local differential privacy (LDP) [2]). For a given privacy budget ɛ∈R+, a randomized mechanism M satisfies ɛ-LDP if and only if for any pair of inputs x, x′and any possible output y∈Range (M), it has(2)PrMx=yPrMx′=y≤eɛ.Theorem 1.
Sequential composition of LDP [21]). If the randomized mechanism Mi satisfies ɛi-LDP, for the given privacy budgets ɛi∈Ri+, i = 1, 2, ⋯, k. Then, their sequential combination M = M1,M2,…,Mk satisfies ∑i=1kɛi-LDP.Proof.
For any inputsx, x′, and output y, we have(3)PrMx=y=PrM1x1=y1PrM2x2=y2,…,PrMkxk=yk≤eɛ1PrM1x1′=y1eɛ2PrM2x2′=y2,…,eɛkPrMkxk′=yk=e∑i=1kɛiPrMx′=y.
According to Theorem1, a given total privacy budget ɛtotal can be split into ɛi with ɛtotal = ∑i=1kɛi, where each ϵi denotes the privacy budget of a randomized mechanism Mi.


## 3.3. Optimized Unary Encoding

### 3.3.1. Randomized Response

Randomized response (RR) [22, 23] is a mainstream perturbation mechanism for LDP. The main idea is to give a random answer to a sensitive question. Accordingly, RR will disturb an input x to an output y as(4)Py|x=x,w.p.p,x′,w.p.1−p.Specifically, the interviewee gives the genuine answerx with probability p and gives the opposite answer x′ with probability 1-p. In this way, RR satisfies lnp/1−p-LDP.Considering RR only works for binary data, some perturbation mechanisms generalize and optimize it, such as direct encoding (DE) [24], histogram encoding (HE) [25], unary encoding (UE) [8, 26], and local hashing (LH) [6, 27].In UE, an inputx is encoded as a length-l binary vector, with only the bit corresponding to x set to 1. Then, the binary vector will be perturbed bit by bit with probability p and q as follows:(5)PrUExi=1=xi=1,w.p.p,xi=0,w.p.q.If UE usesp+q=1, it becomes symmetric unary encoding (SUE) [8]. If UE uses optimized choices of p and q, it becomes optimized unary encoding (OUE) [26].


### 3.3.2. Optimized Unary Encoding

Optimized unary encoding (OUE) [26] converts the input x = i into a binary vector v = (0, …, 0, 1, 0 …, 0) with length-l, where the i-th bit is 1. Then, v is perturbed as follows:(6)Pryi=1|vi=1=p=12,Pryi=0|vi=1=1−p=12,Pryi=1|vi=0=q=1eɛ+1,Pryi=0|vi=0=1−q=eɛeɛ+1.In this way, OUE satisfiesϵ-LDP.Proof.
For any pair of inputsx and x′, we denote their corresponding vector as v and v′, respectively, and denote the output vector as y. Then, we have θ = Pry|v/Pry|v′ = ∏i=1lPryi|vi/Pryi|v′i. According to the OUE, there is only one ‘1’ bit in both the v and v′. Let us assume that v[s] = v′[t] = 1, and there are four different cases for θ since the vector y could have four different possible values, which is listed as follows:(7)θ=θ1=Prys=0|vs=1Pryt=0|vt=0Prys=0|v′s=0Pryt=0|v′t=1,ifys=0,yt=0,θ2=Prys=0|vs=1Pryt=1|vt=0Prys=0|v′s=0Pryt=1|v′t=1,ifys=0,yt=1,θ3=Prys=1|vs=1Pryt=0|vt=0Prys=1|v′s=0Pryt=0|v′t=1,ifys=1,yt=0,θ4=Prys=1|vs=1|Pryt=1|vt=0Prys=1|v′s=0Pryt=1|v′t=1,ifys=1,yt=1.
Then, according to Formula (6), we have(8)θ=θ1=1−p1−q1−q1−p=1,θ2=1−pq1−qp=q1−q,θ3=p1−qq1−p=1−qq,θ4=pqqp=1,and q=1/eɛ+1. Since ϵ is definitely a positive number, we have q<1/2. Then, it is derived that(9)θ≤θ3=1−qq=eɛ,which demonstrates that OUE satisfies ϵ-LDP.


## 3.3.1. Randomized Response

Randomized response (RR) [22, 23] is a mainstream perturbation mechanism for LDP. The main idea is to give a random answer to a sensitive question. Accordingly, RR will disturb an input x to an output y as(4)Py|x=x,w.p.p,x′,w.p.1−p.Specifically, the interviewee gives the genuine answerx with probability p and gives the opposite answer x′ with probability 1-p. In this way, RR satisfies lnp/1−p-LDP.Considering RR only works for binary data, some perturbation mechanisms generalize and optimize it, such as direct encoding (DE) [24], histogram encoding (HE) [25], unary encoding (UE) [8, 26], and local hashing (LH) [6, 27].In UE, an inputx is encoded as a length-l binary vector, with only the bit corresponding to x set to 1. Then, the binary vector will be perturbed bit by bit with probability p and q as follows:(5)PrUExi=1=xi=1,w.p.p,xi=0,w.p.q.If UE usesp+q=1, it becomes symmetric unary encoding (SUE) [8]. If UE uses optimized choices of p and q, it becomes optimized unary encoding (OUE) [26].


## 3.3.2. Optimized Unary Encoding

Optimized unary encoding (OUE) [26] converts the input x = i into a binary vector v = (0, …, 0, 1, 0 …, 0) with length-l, where the i-th bit is 1. Then, v is perturbed as follows:(6)Pryi=1|vi=1=p=12,Pryi=0|vi=1=1−p=12,Pryi=1|vi=0=q=1eɛ+1,Pryi=0|vi=0=1−q=eɛeɛ+1.In this way, OUE satisfiesϵ-LDP.Proof.
For any pair of inputsx and x′, we denote their corresponding vector as v and v′, respectively, and denote the output vector as y. Then, we have θ = Pry|v/Pry|v′ = ∏i=1lPryi|vi/Pryi|v′i. According to the OUE, there is only one ‘1’ bit in both the v and v′. Let us assume that v[s] = v′[t] = 1, and there are four different cases for θ since the vector y could have four different possible values, which is listed as follows:(7)θ=θ1=Prys=0|vs=1Pryt=0|vt=0Prys=0|v′s=0Pryt=0|v′t=1,ifys=0,yt=0,θ2=Prys=0|vs=1Pryt=1|vt=0Prys=0|v′s=0Pryt=1|v′t=1,ifys=0,yt=1,θ3=Prys=1|vs=1Pryt=0|vt=0Prys=1|v′s=0Pryt=0|v′t=1,ifys=1,yt=0,θ4=Prys=1|vs=1|Pryt=1|vt=0Prys=1|v′s=0Pryt=1|v′t=1,ifys=1,yt=1.
Then, according to Formula (6), we have(8)θ=θ1=1−p1−q1−q1−p=1,θ2=1−pq1−qp=q1−q,θ3=p1−qq1−p=1−qq,θ4=pqqp=1,and q=1/eɛ+1. Since ϵ is definitely a positive number, we have q<1/2. Then, it is derived that(9)θ≤θ3=1−qq=eɛ,which demonstrates that OUE satisfies ϵ-LDP.


## 3.4. Least Absolute Shrinkage and Selection Operator Regression

For real multidimensional data, its joint distribution may be sparse. To estimate the joint distribution of real multidimensional data, the least absolute shrinkage and selection operator (LASSO) regression is usually used. Since when solving a multivariate objective function as follows,(10)β^=minβy−Xβ22,where y is the label, X is the vector of an input sample, and β = (β1, β2, …, βm) is the vector of regression coefficients; the overfitting problem may occur. To address it, LASSO regression adds L1-norm as a penalty term after the objective function. Then, constructing a penalty function as follows,(11)β∗=minβy−Xβ22+λβ1,where λ is a data dependent parameter.In this way, when updating the regression coefficientβi to βi∗ with learning rate η, βi∗ = βi - η∂β∗/∂βi. Since ∂λβ1/∂βi = λ or -λ, the updated βi∗ is likely to be zero. In this way, LASSO regression forces the sum of the absolute value of the regression coefficients to be less than a fixed value, which keeps certain coefficients to be set to zero and accordingly results in a simpler model that does not include those zero coefficients. As a result, LASSO regression is quite suitable to solve the sparse linear regression because it can compress the coefficients of variables and make some regression coefficients become zero.


## 4. PLDP: Personalized Local Differential Privacy

### 4.1. System and Threat Model

In the existing multidimensional LDP schemes, the server sets a fixed privacy budget to each attribute to facilitate the estimation of the joint distribution. Since the same attributes of all owners are assigned the same amount of privacy budget, it ignores the personal privacy requirement of owners. However, in real life, the privacy levels of attributes could be distinct to the data owners, i.e., each owner has his personal privacy requirements for his data record. Therefore, it could be a better way to assign different budgets, which are personally decided by the data owner, to each attribute. In this paper, we proposed a multidimensional LDP scheme where the data owner can assign the personal privacy budget to the data he plans to upload according to his personal privacy requirement.


#### 4.1.1. System Model

This paper considers a server that would like to collect a set of data records withd attributes from various data owners. The attributes are denoted as {A1, A2, …, Ad}. To preserve the privacy, the owners are allowed to perturb the data according to his personal privacy requirement before uploading the data. Our goal is to enable the server to estimate the joint distribution of attributes from the perturbed data to benefit the public. Specifically, our system model involves a server and a set of data owners O = {o1, o2, …, oN}, where the owner oi submits a perturbed data record Xi = xi1,xi2,…,xid to the server. In practice, a data owner does not have to possess or be willing to upload the all of d-dimensions of data. Thus, our scheme allows the owner to upload his record with some dimensions of data empty. After receiving the data records, the server puts the owners that report the same dimensions of data into the same group. Then, the joint distribution of data will be conducted within the group or by aggregating several groups. The system model of the proposed scheme can be illustrated in Figure 1.Figure 1
The architecture of the system model.


#### 4.1.2. Threat Model

We assume that the server is untrusted, since the server may leak the data owners’ privacy, such as being hacked, or selling owners’ data to a third party for profit. In this way, the adversary is assumed to possess a perturbed database withd attributes collected by the server, the principle of the perturbation mechanism, and the total privacy budgets of all owners.


### 4.2. Definition of PLDP and Its Relationships with LDP

In this paper, we propose a new LDP notion, named personalized local differential privacy (PLDP). In a PLDP scheme, the server sets an average privacy budgetɛaverage for all of the data owners. If an owner plans to report a data record with m elements unemptied, the owner will hold a total amount of privacy budget ɛtotal = m × ɛaverage. Then, the owner can personally allocate ɛtotal to m elements according to his privacy requirement. In addition, the privacy budget allocation will not be reported to the server, which enhances the security of the users’ data.Definition 3.
personalized local differential privacy (PLDP)). For a given average privacy budgetɛaverage∈R+, each data owner allocates the total privacy budget ɛtotal = m × ɛaverage personally to his data record with m unemptied elements. Denote the m separate privacy budgets as ϵi> 0, i = 1, …, m, and it definitely has ɛtotal = ∑ɛi. Then, a randomized mechanism M satisfies ɛtotal-PLDP if and only if for any pair of records x′, x″ with the same unemptied elements, and any output y∈RangeM, we have(12)PrMx′=yPrMx″=y≤eɛ1′+ɛ2′+⋯+ɛm′=eɛ1″+ɛ2″+⋯+ɛm″=eɛtotal,where ɛi′ and ɛi″ are the privacy budgets allocated to x′ and x″, respectively.


#### 4.2.1. Relationships with LDP

In a multidimensional data scenario, if the privacy budgets for each attribute are the same, i.e.,ɛ1′ + ɛ2′ + ⋯ + ɛm′ = ɛ1″ + ɛ2″ + ⋯ + ɛm″, the PLDP becomes LDP. It means PLDP is a generalized version of LDP. The relationship between LDP and PLDP can be specified by the following two theorems.Theorem 2.
For any pair of recordsx′, x″ with m attributes, if a perturbation mechanism M satisfies ɛ-LDP, it also satisfies ɛtotal-PLDP with ɛtotal = ɛ.Proof.
In a common LDP scheme without considering the personal privacy requirement of data owner, the privacy budget of each attribute equals toɛ/m. It can be considered as having all the ɛi equal to ɛ/m in ɛtotal-PLDP with ɛtotal = ∑i=1mɛi = ɛ.
Theorem2 indicates that LDP is a special case of PLDP. The PLDP can be considered as a generalization of LDP.Theorem 3.
For any pair of recordsx′, x″ with m attributes, if a perturbation mechanism M satisfies ɛtotal-PLDP, it also satisfies ɛ-LDP with ɛ = m × min ɛi≤ɛtotal, i = 1, …, m, where ɛi denotes the privacy budget of i-th attribute.Proof.
In a common LDP scheme for the multidimensional data record, each attribute is put on the same privacy budget. To guarantee the privacy, we should put the smallest privacy budget minɛi to all of the attributes to get an LDP scheme with ɛ = m × min ɛi≤ɛtotal under the same perturbation mechanism.


#### 4.2.2. Security Comparison

In a PLDP scheme, the privacy budget allocation is also a kind of privacy and thus not reported to the server. In addition, in a PLDP scheme, the owner can freely allocate his privacy budget to the attributes. When a small budget is put on an attribute, it means the attribute is very sensitive to the data owner and the privacy budget on this attribute also weighs a lot. Nevertheless, if a large budget is put on an attribute, it means the attributes are not so important and the privacy budget on this attribute may not weigh much. Here, we definite a notion to quantize the amount of weighted privacy budget, which can be regarded as the real privacy budget to a data owner in the PLDP scheme.Definition 4.
(weighted privacy budgetɛw). With a given total privacy budget ϵtotal = m×ɛaverage from the server, the data owner splits it into m parts denoted as ɛi, i = 1, …, m. Then, the weighted privacy budget of the data owner can be calculated as(13)ɛw=∑i=1mɛiwi,where wi = 1−ɛi−ɛmin/ɛtotal and ϵmin = min{ɛ1, ɛ2, …, ɛm}. It means that an ɛi will be multiplied by a smaller weight if ɛi is larger than ɛmin. Generally, the weighted privacy budget is smaller than ϵtotal, which indicates a PLDP scheme provides better privacy protection than an LDP scheme. The illustration of personalized privacy budget is shown in Figure 2.Figure 2
Illustration of personalized privacy budget.


### 4.3. Perturbation Mechanism for PLDP

In this section, we adapt the OUE to generate a perturbation mechanism for PLDP, which we name as personalized multiple optimized unary encoding (PMOUE), since there are multiple attributes in our scenario and the privacy budget can be personally allocated. We denote a data record withm unemptied attributes as X = {x1, x2, …, xm}, and the attribute xi has li candidate values. According to OUE, the attribute xi = k is encoded to be a binary vector vi = (0, …, 0, 1, 0, …, 0) with the length li. The k-th bit in vi is set to be 1, and the remaining bits are set to be 0. In order to protect the owner’s data record, the bits in vi are randomly flipped according to Algorithm 1, generating the perturbed element yi. The parameters p and q in formula (6) depend on the privacy budget ϵi that are allocated to the element xi. Finally, the data owner concatenates all of the yi to be Y = {y1, y2, …, ym} and sends Y to the server. The specific perturbation mechanism is described in Algorithm 1.Algorithm 1: Personalized multiple optimized unary encoding (PMOUE).
(i)
Input:X = {x1, x2, …, xm}: the raw data record with m unemptied attributesɛi: the privacy budget that allocated to attribute xii=1,2,…,mli: the number of the candidate values of each attribute i=1,2,…,mOutput:Y = {y1, y2, …, ym}: the perturbed data record with m attributes(1)
Encoding:vi=Encodexi,li,i=1,2,…,m(2)
Perturbation:yi=Pryij=1|vij=1=pi=1/2,Pryij=0|vij=1=1−pi=1/2,Pryij=1|vij=0=qi=1/eɛ+1,Pryij=0|vij=0=1−qi=eɛ/eɛ+1,j=1,2,…,li;i=1,2,…,m,(3)
returnY = y1,y2,…,ym.Theorem 4.
The perturbation mechanism PMOUE satisfiesϵtotal-PLDP, where ϵtotal = m×ɛaverage.Proof.
For any inputsx′, x″ with the same m unemptied attributes denoted by xi′ and xi″, which are encoded to vi′ and vi″, and the output y with m valid elements denoted by yi, i = 1, …, m, we have θ = Pry|x′/Pry|x″ = ∏i=1mPryi|xi′/Pryi|xi″ = ∏i=1m∏j=1liPryij|vi′j/Pryij|vi″j.
According to formula (9), we have(14)θ≤∏i=1mPryisi=1|vi′si=1Pryiti=0|vi′ti=0Pryisi=1|vi″si=0Pryiti=0|vi″ti=1=∏i=1mpi′1−qi′qi″1−pi″=∏i=1m1−qi′qi″=∏i=1meɛi′eɛi″+1eɛi′+1=e∑i=1mɛi′∏i=1meɛi″+1eɛi′+1=eɛtotal∑i=1mσi″+1∑i=1mσi′+1,where ∑i=1mσi′ and ∑i=1mσi″ are the m elementary symmetric polynomials about the variables eɛ1′, eɛ2′, ⋯, eɛm′ and eɛ1″, eɛ2″, ⋯, eɛm″ separately, i.e., σ1′ = eɛ1′ + eɛ2′ + ⋯ + eɛm′, σ2′ = eɛ1′eɛ2′ + eɛ1′eɛ3′ + ⋯ + eɛm−1′eɛm′, ⋯, σm′ = eɛ1′eɛ2′,…,eɛm′ [28].
Becauselimx⟶0ex = x + 1, so Pry|x/Pry|x′(15)≤eɛtotal∑i=1mɛi″+1+∑j=1m∑i=1,i≠jmɛi″+ɛj″+1+⋯+∑i=1mɛi″+1+1∑i=1mɛi′+1+∑j=1m∑i=1,i≠jmɛi′+ɛj′+1+⋯+∑i=1mɛi′+1+1=eɛtotalɛtotal+m+m−1ɛtotal+m+⋯+ɛtotal+1+1ɛtotal+m+m−1ɛtotal+m+⋯+ɛtotal+1+1=eɛtotal.


### 4.4. Estimation of the Joint Distribution

After receivingY = {y1, y2, …, ym} from each data owner, the server can estimate the joint distribution of multidimensional data. Here, we describe the estimation in two situations: (1) the frequency estimation for k-dimensional data that is included in some records, and (2) the frequency estimation for k-dimensional data that is not included in any records.


#### 4.4.1. Situation 1

Since thek dimensions of data are included in some records, we group these records together for the frequency estimation. As presented in Section 3.3, the k dimensions of data are encoded to be the binary vector with the length t = ∑i=1kli, where li is the number of candidate values of the i-th attribute. Assuming there are s records that have these k dimensions, the frequency will be estimated from a binary matrix denoted as C^s×t. Firstly, the server counts the number of ‘1’ in each column, generating a vector c^1,c^2,…,c^t. Then, to obtain an unbiased estimation, maximum likelihood estimation [29] is used to calibrate c^i as follows:(16)ci=c^i−Gqp−q=c^i−s/eɛaverage+11/2−s/eɛaverage+1,where ci denotes the occurrence number of each candidate value, indicating the individual distribution of the attributes. G is the total number of records.With the distribution of each dimension of data, the joint distribution of thek-dimensional data is estimated by LASSO regression. Firstly, the server encodes the candidate values of attributes to be binary string according to OUE. Next, the candidate values of different attributes are connected by Cartesian product and then transposed, resulting in the candidate matrix Mt×r, where t = ∑i=1kli is the bit length of the candidate value of the k-dimensional data and r = ∏i=1kli is the total number of candidate values. Ensemble the candidate value frequencies of the k-dimensional data to be a vector P = p1,p2,…,prT, and we have(17)MP=C,where C = c1,c2,…,ctT. Since the candidate value matrix Mt×r and the vector Ct×1 are both known, it seems that the unknown regression coefficient vector Pr×1 can be derived easily. In fact, the total number of joint candidate values r could be very large, but the occurrence frequencies of some candidate values are very small or even close to 0. That is to say, Pr×1 could be quite sparse.As presented in Section3.4, LASSO regression is quite suitable to solve the sparse linear regression. In this paper, the solution of frequency vector P in formula (17) is considered as a sparse linear regression problem where a shrunken vector is preferred. Thus, LASSO is used to obtain the frequency vector P. In Figure 3, we illustrate the whole process to estimate the frequency of the k-dimensional data in Situation 1.Figure 3
Illustration of LASSO scheme. (a) Attribute encoding. (b) Data encoding and perturbing. (c) Frequency estimation.As shown in Figure3, we consider an example with two attributes, i.e. gender and hobby, which, respectively, have two and three candidate values. Firstly, the candidate values are encoded to be the 2-bit and 3-bit binary vectors. The binary vectors of different candidate values are connected by Cartesian product, resulting in a matrix M′ which then is transposed to be the candidate matrix M. Next, the data owners encode their data according to the encoding strategy and then perturb and upload the data to the server. In Situation 1, the considered k dimensions of data are included in some records. The server groups these records together to estimate the distribution of the frequency estimation. After receiving the perturbed data, the server counts the ‘1’ bit in each column, resulting in a vector. The server calibrates the vector that indicates the frequencies of attribute values. Finally, the frequency vector P is calculated by LASSO regression algorithm with the M and C.


#### 4.4.2. Situation 2

In this situation, the server wants to estimate the joint distribution ofk attributes, denoted as A = a1,a2,…,ak, but there is no record containing all of these k attribute values. Accordingly, we divide the k attributes into two parts, i.e., A1 and A2, so that each part of the attributes is contained by some records. The A1 and A2 are considered as two multidimensional attributes with the domains Ω1 and Ω2, respectively. Then, we can estimate the distributions of A1 and A2 by LASSO regression algorithm as in Situation 1 separately and synthesize two distributions together.The first step is to choose a division strategy and here we prefer the unbalanced one. That is to say, we prefer to letA1 have the most attributes in A and let A2 only have a small part of attributes. The second step is to allocate the attributes into A1 and A2. Intuitively, we hope A1 and A2 are as independent as possible. Then, the joint distribution of A1 and A2 can be calculated by direct multiplication. Information entropy [30] is a usual method to measure the amount of information and can also be used to identify the independency of the variable. Generally, a larger amount of information means larger independence. Based on the points above, we calculate the joint distribution of k attributes as described in Algorithm 2 and show its illustration in Figure 4.Algorithm 2: Information entropy-based multidimensional joint distribution estimation.
(i)
Input: A: the set of k attributes for which the sever wantsto estimate the joint distribution andXi is the setof data records with Xi = xi1,xi2,…,xid, where xij could be empty.Output: HD: the joint distribution of A(1)
forr = 1 to k/2do(2)
Initialize a result list,listR=∅;(3)
DividedA into two parts: A1 and A2, where A1  = k - r and A2 = r, and there are n = kr different divisions;(4)
fori = 1 to ndo(5)
For the i-th division, if there are enough records that have all the attributes inA1 and A2, the sever estimatesthe joint distributions of A1 and A2 by LASSO regression algorithm, respectively. Denote the domains of candidate values of A1 and A2 as Ω1 andΩ2, respectively, and then the estimated joint distribution can be denoted as P′ = p1′,p2′,…,pΩ1′ and P′′  = p1′′,p2′′,…,pΩ2′′.(6)
CalculateH′ = ∑i=1Ω1pi′logpi′, H″ = ∑i=1Ω2pi″logpi″, and then the total information entropy in this division Hi = H′ + H″.(7)
Finally, add the triplet<P′, P″,Hi> into listR;(8)
end for(9)
IflistR≠∅Break;(10)
end for(11)
Choose the triplet with the largestHi and calculate the joint distribution with the corresponding P′, P″ by the multiplication principle.Figure 4
Illustration of information entropy-based scheme. (a) AB and C. (b) AC and B. (c) BC and A.
(a)(b)(c)


## 4.1. System and Threat Model

In the existing multidimensional LDP schemes, the server sets a fixed privacy budget to each attribute to facilitate the estimation of the joint distribution. Since the same attributes of all owners are assigned the same amount of privacy budget, it ignores the personal privacy requirement of owners. However, in real life, the privacy levels of attributes could be distinct to the data owners, i.e., each owner has his personal privacy requirements for his data record. Therefore, it could be a better way to assign different budgets, which are personally decided by the data owner, to each attribute. In this paper, we proposed a multidimensional LDP scheme where the data owner can assign the personal privacy budget to the data he plans to upload according to his personal privacy requirement.


### 4.1.1. System Model

This paper considers a server that would like to collect a set of data records withd attributes from various data owners. The attributes are denoted as {A1, A2, …, Ad}. To preserve the privacy, the owners are allowed to perturb the data according to his personal privacy requirement before uploading the data. Our goal is to enable the server to estimate the joint distribution of attributes from the perturbed data to benefit the public. Specifically, our system model involves a server and a set of data owners O = {o1, o2, …, oN}, where the owner oi submits a perturbed data record Xi = xi1,xi2,…,xid to the server. In practice, a data owner does not have to possess or be willing to upload the all of d-dimensions of data. Thus, our scheme allows the owner to upload his record with some dimensions of data empty. After receiving the data records, the server puts the owners that report the same dimensions of data into the same group. Then, the joint distribution of data will be conducted within the group or by aggregating several groups. The system model of the proposed scheme can be illustrated in Figure 1.Figure 1
The architecture of the system model.


### 4.1.2. Threat Model

We assume that the server is untrusted, since the server may leak the data owners’ privacy, such as being hacked, or selling owners’ data to a third party for profit. In this way, the adversary is assumed to possess a perturbed database withd attributes collected by the server, the principle of the perturbation mechanism, and the total privacy budgets of all owners.


## 4.1.1. System Model

This paper considers a server that would like to collect a set of data records withd attributes from various data owners. The attributes are denoted as {A1, A2, …, Ad}. To preserve the privacy, the owners are allowed to perturb the data according to his personal privacy requirement before uploading the data. Our goal is to enable the server to estimate the joint distribution of attributes from the perturbed data to benefit the public. Specifically, our system model involves a server and a set of data owners O = {o1, o2, …, oN}, where the owner oi submits a perturbed data record Xi = xi1,xi2,…,xid to the server. In practice, a data owner does not have to possess or be willing to upload the all of d-dimensions of data. Thus, our scheme allows the owner to upload his record with some dimensions of data empty. After receiving the data records, the server puts the owners that report the same dimensions of data into the same group. Then, the joint distribution of data will be conducted within the group or by aggregating several groups. The system model of the proposed scheme can be illustrated in Figure 1.Figure 1
The architecture of the system model.


## 4.1.2. Threat Model

We assume that the server is untrusted, since the server may leak the data owners’ privacy, such as being hacked, or selling owners’ data to a third party for profit. In this way, the adversary is assumed to possess a perturbed database withd attributes collected by the server, the principle of the perturbation mechanism, and the total privacy budgets of all owners.


## 4.2. Definition of PLDP and Its Relationships with LDP

In this paper, we propose a new LDP notion, named personalized local differential privacy (PLDP). In a PLDP scheme, the server sets an average privacy budgetɛaverage for all of the data owners. If an owner plans to report a data record with m elements unemptied, the owner will hold a total amount of privacy budget ɛtotal = m × ɛaverage. Then, the owner can personally allocate ɛtotal to m elements according to his privacy requirement. In addition, the privacy budget allocation will not be reported to the server, which enhances the security of the users’ data.Definition 3.
personalized local differential privacy (PLDP)). For a given average privacy budgetɛaverage∈R+, each data owner allocates the total privacy budget ɛtotal = m × ɛaverage personally to his data record with m unemptied elements. Denote the m separate privacy budgets as ϵi> 0, i = 1, …, m, and it definitely has ɛtotal = ∑ɛi. Then, a randomized mechanism M satisfies ɛtotal-PLDP if and only if for any pair of records x′, x″ with the same unemptied elements, and any output y∈RangeM, we have(12)PrMx′=yPrMx″=y≤eɛ1′+ɛ2′+⋯+ɛm′=eɛ1″+ɛ2″+⋯+ɛm″=eɛtotal,where ɛi′ and ɛi″ are the privacy budgets allocated to x′ and x″, respectively.


### 4.2.1. Relationships with LDP

In a multidimensional data scenario, if the privacy budgets for each attribute are the same, i.e.,ɛ1′ + ɛ2′ + ⋯ + ɛm′ = ɛ1″ + ɛ2″ + ⋯ + ɛm″, the PLDP becomes LDP. It means PLDP is a generalized version of LDP. The relationship between LDP and PLDP can be specified by the following two theorems.Theorem 2.
For any pair of recordsx′, x″ with m attributes, if a perturbation mechanism M satisfies ɛ-LDP, it also satisfies ɛtotal-PLDP with ɛtotal = ɛ.Proof.
In a common LDP scheme without considering the personal privacy requirement of data owner, the privacy budget of each attribute equals toɛ/m. It can be considered as having all the ɛi equal to ɛ/m in ɛtotal-PLDP with ɛtotal = ∑i=1mɛi = ɛ.
Theorem2 indicates that LDP is a special case of PLDP. The PLDP can be considered as a generalization of LDP.Theorem 3.
For any pair of recordsx′, x″ with m attributes, if a perturbation mechanism M satisfies ɛtotal-PLDP, it also satisfies ɛ-LDP with ɛ = m × min ɛi≤ɛtotal, i = 1, …, m, where ɛi denotes the privacy budget of i-th attribute.Proof.
In a common LDP scheme for the multidimensional data record, each attribute is put on the same privacy budget. To guarantee the privacy, we should put the smallest privacy budget minɛi to all of the attributes to get an LDP scheme with ɛ = m × min ɛi≤ɛtotal under the same perturbation mechanism.


### 4.2.2. Security Comparison

In a PLDP scheme, the privacy budget allocation is also a kind of privacy and thus not reported to the server. In addition, in a PLDP scheme, the owner can freely allocate his privacy budget to the attributes. When a small budget is put on an attribute, it means the attribute is very sensitive to the data owner and the privacy budget on this attribute also weighs a lot. Nevertheless, if a large budget is put on an attribute, it means the attributes are not so important and the privacy budget on this attribute may not weigh much. Here, we definite a notion to quantize the amount of weighted privacy budget, which can be regarded as the real privacy budget to a data owner in the PLDP scheme.Definition 4.
(weighted privacy budgetɛw). With a given total privacy budget ϵtotal = m×ɛaverage from the server, the data owner splits it into m parts denoted as ɛi, i = 1, …, m. Then, the weighted privacy budget of the data owner can be calculated as(13)ɛw=∑i=1mɛiwi,where wi = 1−ɛi−ɛmin/ɛtotal and ϵmin = min{ɛ1, ɛ2, …, ɛm}. It means that an ɛi will be multiplied by a smaller weight if ɛi is larger than ɛmin. Generally, the weighted privacy budget is smaller than ϵtotal, which indicates a PLDP scheme provides better privacy protection than an LDP scheme. The illustration of personalized privacy budget is shown in Figure 2.Figure 2
Illustration of personalized privacy budget.


## 4.2.1. Relationships with LDP

In a multidimensional data scenario, if the privacy budgets for each attribute are the same, i.e.,ɛ1′ + ɛ2′ + ⋯ + ɛm′ = ɛ1″ + ɛ2″ + ⋯ + ɛm″, the PLDP becomes LDP. It means PLDP is a generalized version of LDP. The relationship between LDP and PLDP can be specified by the following two theorems.Theorem 2.
For any pair of recordsx′, x″ with m attributes, if a perturbation mechanism M satisfies ɛ-LDP, it also satisfies ɛtotal-PLDP with ɛtotal = ɛ.Proof.
In a common LDP scheme without considering the personal privacy requirement of data owner, the privacy budget of each attribute equals toɛ/m. It can be considered as having all the ɛi equal to ɛ/m in ɛtotal-PLDP with ɛtotal = ∑i=1mɛi = ɛ.
Theorem2 indicates that LDP is a special case of PLDP. The PLDP can be considered as a generalization of LDP.Theorem 3.
For any pair of recordsx′, x″ with m attributes, if a perturbation mechanism M satisfies ɛtotal-PLDP, it also satisfies ɛ-LDP with ɛ = m × min ɛi≤ɛtotal, i = 1, …, m, where ɛi denotes the privacy budget of i-th attribute.Proof.
In a common LDP scheme for the multidimensional data record, each attribute is put on the same privacy budget. To guarantee the privacy, we should put the smallest privacy budget minɛi to all of the attributes to get an LDP scheme with ɛ = m × min ɛi≤ɛtotal under the same perturbation mechanism.


## 4.2.2. Security Comparison

In a PLDP scheme, the privacy budget allocation is also a kind of privacy and thus not reported to the server. In addition, in a PLDP scheme, the owner can freely allocate his privacy budget to the attributes. When a small budget is put on an attribute, it means the attribute is very sensitive to the data owner and the privacy budget on this attribute also weighs a lot. Nevertheless, if a large budget is put on an attribute, it means the attributes are not so important and the privacy budget on this attribute may not weigh much. Here, we definite a notion to quantize the amount of weighted privacy budget, which can be regarded as the real privacy budget to a data owner in the PLDP scheme.Definition 4.
(weighted privacy budgetɛw). With a given total privacy budget ϵtotal = m×ɛaverage from the server, the data owner splits it into m parts denoted as ɛi, i = 1, …, m. Then, the weighted privacy budget of the data owner can be calculated as(13)ɛw=∑i=1mɛiwi,where wi = 1−ɛi−ɛmin/ɛtotal and ϵmin = min{ɛ1, ɛ2, …, ɛm}. It means that an ɛi will be multiplied by a smaller weight if ɛi is larger than ɛmin. Generally, the weighted privacy budget is smaller than ϵtotal, which indicates a PLDP scheme provides better privacy protection than an LDP scheme. The illustration of personalized privacy budget is shown in Figure 2.Figure 2
Illustration of personalized privacy budget.


## 4.3. Perturbation Mechanism for PLDP

In this section, we adapt the OUE to generate a perturbation mechanism for PLDP, which we name as personalized multiple optimized unary encoding (PMOUE), since there are multiple attributes in our scenario and the privacy budget can be personally allocated. We denote a data record withm unemptied attributes as X = {x1, x2, …, xm}, and the attribute xi has li candidate values. According to OUE, the attribute xi = k is encoded to be a binary vector vi = (0, …, 0, 1, 0, …, 0) with the length li. The k-th bit in vi is set to be 1, and the remaining bits are set to be 0. In order to protect the owner’s data record, the bits in vi are randomly flipped according to Algorithm 1, generating the perturbed element yi. The parameters p and q in formula (6) depend on the privacy budget ϵi that are allocated to the element xi. Finally, the data owner concatenates all of the yi to be Y = {y1, y2, …, ym} and sends Y to the server. The specific perturbation mechanism is described in Algorithm 1.Algorithm 1: Personalized multiple optimized unary encoding (PMOUE).
(i)
Input:X = {x1, x2, …, xm}: the raw data record with m unemptied attributesɛi: the privacy budget that allocated to attribute xii=1,2,…,mli: the number of the candidate values of each attribute i=1,2,…,mOutput:Y = {y1, y2, …, ym}: the perturbed data record with m attributes(1)
Encoding:vi=Encodexi,li,i=1,2,…,m(2)
Perturbation:yi=Pryij=1|vij=1=pi=1/2,Pryij=0|vij=1=1−pi=1/2,Pryij=1|vij=0=qi=1/eɛ+1,Pryij=0|vij=0=1−qi=eɛ/eɛ+1,j=1,2,…,li;i=1,2,…,m,(3)
returnY = y1,y2,…,ym.Theorem 4.
The perturbation mechanism PMOUE satisfiesϵtotal-PLDP, where ϵtotal = m×ɛaverage.Proof.
For any inputsx′, x″ with the same m unemptied attributes denoted by xi′ and xi″, which are encoded to vi′ and vi″, and the output y with m valid elements denoted by yi, i = 1, …, m, we have θ = Pry|x′/Pry|x″ = ∏i=1mPryi|xi′/Pryi|xi″ = ∏i=1m∏j=1liPryij|vi′j/Pryij|vi″j.
According to formula (9), we have(14)θ≤∏i=1mPryisi=1|vi′si=1Pryiti=0|vi′ti=0Pryisi=1|vi″si=0Pryiti=0|vi″ti=1=∏i=1mpi′1−qi′qi″1−pi″=∏i=1m1−qi′qi″=∏i=1meɛi′eɛi″+1eɛi′+1=e∑i=1mɛi′∏i=1meɛi″+1eɛi′+1=eɛtotal∑i=1mσi″+1∑i=1mσi′+1,where ∑i=1mσi′ and ∑i=1mσi″ are the m elementary symmetric polynomials about the variables eɛ1′, eɛ2′, ⋯, eɛm′ and eɛ1″, eɛ2″, ⋯, eɛm″ separately, i.e., σ1′ = eɛ1′ + eɛ2′ + ⋯ + eɛm′, σ2′ = eɛ1′eɛ2′ + eɛ1′eɛ3′ + ⋯ + eɛm−1′eɛm′, ⋯, σm′ = eɛ1′eɛ2′,…,eɛm′ [28].
Becauselimx⟶0ex = x + 1, so Pry|x/Pry|x′(15)≤eɛtotal∑i=1mɛi″+1+∑j=1m∑i=1,i≠jmɛi″+ɛj″+1+⋯+∑i=1mɛi″+1+1∑i=1mɛi′+1+∑j=1m∑i=1,i≠jmɛi′+ɛj′+1+⋯+∑i=1mɛi′+1+1=eɛtotalɛtotal+m+m−1ɛtotal+m+⋯+ɛtotal+1+1ɛtotal+m+m−1ɛtotal+m+⋯+ɛtotal+1+1=eɛtotal.


## 4.4. Estimation of the Joint Distribution

After receivingY = {y1, y2, …, ym} from each data owner, the server can estimate the joint distribution of multidimensional data. Here, we describe the estimation in two situations: (1) the frequency estimation for k-dimensional data that is included in some records, and (2) the frequency estimation for k-dimensional data that is not included in any records.


### 4.4.1. Situation 1

Since thek dimensions of data are included in some records, we group these records together for the frequency estimation. As presented in Section 3.3, the k dimensions of data are encoded to be the binary vector with the length t = ∑i=1kli, where li is the number of candidate values of the i-th attribute. Assuming there are s records that have these k dimensions, the frequency will be estimated from a binary matrix denoted as C^s×t. Firstly, the server counts the number of ‘1’ in each column, generating a vector c^1,c^2,…,c^t. Then, to obtain an unbiased estimation, maximum likelihood estimation [29] is used to calibrate c^i as follows:(16)ci=c^i−Gqp−q=c^i−s/eɛaverage+11/2−s/eɛaverage+1,where ci denotes the occurrence number of each candidate value, indicating the individual distribution of the attributes. G is the total number of records.With the distribution of each dimension of data, the joint distribution of thek-dimensional data is estimated by LASSO regression. Firstly, the server encodes the candidate values of attributes to be binary string according to OUE. Next, the candidate values of different attributes are connected by Cartesian product and then transposed, resulting in the candidate matrix Mt×r, where t = ∑i=1kli is the bit length of the candidate value of the k-dimensional data and r = ∏i=1kli is the total number of candidate values. Ensemble the candidate value frequencies of the k-dimensional data to be a vector P = p1,p2,…,prT, and we have(17)MP=C,where C = c1,c2,…,ctT. Since the candidate value matrix Mt×r and the vector Ct×1 are both known, it seems that the unknown regression coefficient vector Pr×1 can be derived easily. In fact, the total number of joint candidate values r could be very large, but the occurrence frequencies of some candidate values are very small or even close to 0. That is to say, Pr×1 could be quite sparse.As presented in Section3.4, LASSO regression is quite suitable to solve the sparse linear regression. In this paper, the solution of frequency vector P in formula (17) is considered as a sparse linear regression problem where a shrunken vector is preferred. Thus, LASSO is used to obtain the frequency vector P. In Figure 3, we illustrate the whole process to estimate the frequency of the k-dimensional data in Situation 1.Figure 3
Illustration of LASSO scheme. (a) Attribute encoding. (b) Data encoding and perturbing. (c) Frequency estimation.As shown in Figure3, we consider an example with two attributes, i.e. gender and hobby, which, respectively, have two and three candidate values. Firstly, the candidate values are encoded to be the 2-bit and 3-bit binary vectors. The binary vectors of different candidate values are connected by Cartesian product, resulting in a matrix M′ which then is transposed to be the candidate matrix M. Next, the data owners encode their data according to the encoding strategy and then perturb and upload the data to the server. In Situation 1, the considered k dimensions of data are included in some records. The server groups these records together to estimate the distribution of the frequency estimation. After receiving the perturbed data, the server counts the ‘1’ bit in each column, resulting in a vector. The server calibrates the vector that indicates the frequencies of attribute values. Finally, the frequency vector P is calculated by LASSO regression algorithm with the M and C.


### 4.4.2. Situation 2

In this situation, the server wants to estimate the joint distribution ofk attributes, denoted as A = a1,a2,…,ak, but there is no record containing all of these k attribute values. Accordingly, we divide the k attributes into two parts, i.e., A1 and A2, so that each part of the attributes is contained by some records. The A1 and A2 are considered as two multidimensional attributes with the domains Ω1 and Ω2, respectively. Then, we can estimate the distributions of A1 and A2 by LASSO regression algorithm as in Situation 1 separately and synthesize two distributions together.The first step is to choose a division strategy and here we prefer the unbalanced one. That is to say, we prefer to letA1 have the most attributes in A and let A2 only have a small part of attributes. The second step is to allocate the attributes into A1 and A2. Intuitively, we hope A1 and A2 are as independent as possible. Then, the joint distribution of A1 and A2 can be calculated by direct multiplication. Information entropy [30] is a usual method to measure the amount of information and can also be used to identify the independency of the variable. Generally, a larger amount of information means larger independence. Based on the points above, we calculate the joint distribution of k attributes as described in Algorithm 2 and show its illustration in Figure 4.Algorithm 2: Information entropy-based multidimensional joint distribution estimation.
(i)
Input: A: the set of k attributes for which the sever wantsto estimate the joint distribution andXi is the setof data records with Xi = xi1,xi2,…,xid, where xij could be empty.Output: HD: the joint distribution of A(1)
forr = 1 to k/2do(2)
Initialize a result list,listR=∅;(3)
DividedA into two parts: A1 and A2, where A1  = k - r and A2 = r, and there are n = kr different divisions;(4)
fori = 1 to ndo(5)
For the i-th division, if there are enough records that have all the attributes inA1 and A2, the sever estimatesthe joint distributions of A1 and A2 by LASSO regression algorithm, respectively. Denote the domains of candidate values of A1 and A2 as Ω1 andΩ2, respectively, and then the estimated joint distribution can be denoted as P′ = p1′,p2′,…,pΩ1′ and P′′  = p1′′,p2′′,…,pΩ2′′.(6)
CalculateH′ = ∑i=1Ω1pi′logpi′, H″ = ∑i=1Ω2pi″logpi″, and then the total information entropy in this division Hi = H′ + H″.(7)
Finally, add the triplet<P′, P″,Hi> into listR;(8)
end for(9)
IflistR≠∅Break;(10)
end for(11)
Choose the triplet with the largestHi and calculate the joint distribution with the corresponding P′, P″ by the multiplication principle.Figure 4
Illustration of information entropy-based scheme. (a) AB and C. (b) AC and B. (c) BC and A.
(a)(b)(c)


## 4.4.1. Situation 1

Since thek dimensions of data are included in some records, we group these records together for the frequency estimation. As presented in Section 3.3, the k dimensions of data are encoded to be the binary vector with the length t = ∑i=1kli, where li is the number of candidate values of the i-th attribute. Assuming there are s records that have these k dimensions, the frequency will be estimated from a binary matrix denoted as C^s×t. Firstly, the server counts the number of ‘1’ in each column, generating a vector c^1,c^2,…,c^t. Then, to obtain an unbiased estimation, maximum likelihood estimation [29] is used to calibrate c^i as follows:(16)ci=c^i−Gqp−q=c^i−s/eɛaverage+11/2−s/eɛaverage+1,where ci denotes the occurrence number of each candidate value, indicating the individual distribution of the attributes. G is the total number of records.With the distribution of each dimension of data, the joint distribution of thek-dimensional data is estimated by LASSO regression. Firstly, the server encodes the candidate values of attributes to be binary string according to OUE. Next, the candidate values of different attributes are connected by Cartesian product and then transposed, resulting in the candidate matrix Mt×r, where t = ∑i=1kli is the bit length of the candidate value of the k-dimensional data and r = ∏i=1kli is the total number of candidate values. Ensemble the candidate value frequencies of the k-dimensional data to be a vector P = p1,p2,…,prT, and we have(17)MP=C,where C = c1,c2,…,ctT. Since the candidate value matrix Mt×r and the vector Ct×1 are both known, it seems that the unknown regression coefficient vector Pr×1 can be derived easily. In fact, the total number of joint candidate values r could be very large, but the occurrence frequencies of some candidate values are very small or even close to 0. That is to say, Pr×1 could be quite sparse.As presented in Section3.4, LASSO regression is quite suitable to solve the sparse linear regression. In this paper, the solution of frequency vector P in formula (17) is considered as a sparse linear regression problem where a shrunken vector is preferred. Thus, LASSO is used to obtain the frequency vector P. In Figure 3, we illustrate the whole process to estimate the frequency of the k-dimensional data in Situation 1.Figure 3
Illustration of LASSO scheme. (a) Attribute encoding. (b) Data encoding and perturbing. (c) Frequency estimation.As shown in Figure3, we consider an example with two attributes, i.e. gender and hobby, which, respectively, have two and three candidate values. Firstly, the candidate values are encoded to be the 2-bit and 3-bit binary vectors. The binary vectors of different candidate values are connected by Cartesian product, resulting in a matrix M′ which then is transposed to be the candidate matrix M. Next, the data owners encode their data according to the encoding strategy and then perturb and upload the data to the server. In Situation 1, the considered k dimensions of data are included in some records. The server groups these records together to estimate the distribution of the frequency estimation. After receiving the perturbed data, the server counts the ‘1’ bit in each column, resulting in a vector. The server calibrates the vector that indicates the frequencies of attribute values. Finally, the frequency vector P is calculated by LASSO regression algorithm with the M and C.


## 4.4.2. Situation 2

In this situation, the server wants to estimate the joint distribution ofk attributes, denoted as A = a1,a2,…,ak, but there is no record containing all of these k attribute values. Accordingly, we divide the k attributes into two parts, i.e., A1 and A2, so that each part of the attributes is contained by some records. The A1 and A2 are considered as two multidimensional attributes with the domains Ω1 and Ω2, respectively. Then, we can estimate the distributions of A1 and A2 by LASSO regression algorithm as in Situation 1 separately and synthesize two distributions together.The first step is to choose a division strategy and here we prefer the unbalanced one. That is to say, we prefer to letA1 have the most attributes in A and let A2 only have a small part of attributes. The second step is to allocate the attributes into A1 and A2. Intuitively, we hope A1 and A2 are as independent as possible. Then, the joint distribution of A1 and A2 can be calculated by direct multiplication. Information entropy [30] is a usual method to measure the amount of information and can also be used to identify the independency of the variable. Generally, a larger amount of information means larger independence. Based on the points above, we calculate the joint distribution of k attributes as described in Algorithm 2 and show its illustration in Figure 4.Algorithm 2: Information entropy-based multidimensional joint distribution estimation.
(i)
Input: A: the set of k attributes for which the sever wantsto estimate the joint distribution andXi is the setof data records with Xi = xi1,xi2,…,xid, where xij could be empty.Output: HD: the joint distribution of A(1)
forr = 1 to k/2do(2)
Initialize a result list,listR=∅;(3)
DividedA into two parts: A1 and A2, where A1  = k - r and A2 = r, and there are n = kr different divisions;(4)
fori = 1 to ndo(5)
For the i-th division, if there are enough records that have all the attributes inA1 and A2, the sever estimatesthe joint distributions of A1 and A2 by LASSO regression algorithm, respectively. Denote the domains of candidate values of A1 and A2 as Ω1 andΩ2, respectively, and then the estimated joint distribution can be denoted as P′ = p1′,p2′,…,pΩ1′ and P′′  = p1′′,p2′′,…,pΩ2′′.(6)
CalculateH′ = ∑i=1Ω1pi′logpi′, H″ = ∑i=1Ω2pi″logpi″, and then the total information entropy in this division Hi = H′ + H″.(7)
Finally, add the triplet<P′, P″,Hi> into listR;(8)
end for(9)
IflistR≠∅Break;(10)
end for(11)
Choose the triplet with the largestHi and calculate the joint distribution with the corresponding P′, P″ by the multiplication principle.Figure 4
Illustration of information entropy-based scheme. (a) AB and C. (b) AC and B. (c) BC and A.
(a)(b)(c)


## 5. Evaluation

In this section, we perform the experiments on four real datasets. The experimental results show the efficiency and superiority of our proposed notion PLDP in the aspect of accuracy and efficiency.


### 5.1. Experimental Setup

#### 5.1.1. Environment

All the experiments were performed on a machine with Intel Core i5 CPU 2.50 GHz and 8 GB RAM, using Windows 10 and Python 3.5.2.


#### 5.1.2. Datasets

We performed experiments on the following four real datasets, whose parameters are presented in Table1. Abalone [31] contains the size of the abalone through physical measurements. Adult [31] is extracted by Barry Becker from the 1994 Census database. It contains personal information, such as “age,” “relationship,” and “money.” Bank marketing [32] is related with direct marketing campaigns, which are based on phone calls, of a Portuguese banking institution. Car evaluation [31] contains several basic parameters of the car, which is derived from a simple hierarchical decision model. In order to simplify the experiments, we bucket the continuous and nonnumerical data into the discretized ones.Table 1
Datasets.
DatasetsAttribute characteristics#.Records (N)#.Attributes (d)AdultCategorical, integer4884215AbaloneCategorical, integer, real41779Bank marketingReal4521117Car evaluationCategorical17287


#### 5.1.3. Evaluation Metrics

The performance of PLDP is measured by the accuracy of the distribution estimation and the time consumption during the estimation. The time consumption contains CPU time and IO cost. As in much previous work, we used the average variant distance (AVD) [33] to evaluate the estimation accuracy, which is defined as(18)AVDP,Q=∑ω∈ΩPω−Qω2,where Ω is the domain of the multidimensional variable, P (ω) denotes the real joint distribution, and Q (ω) denotes the estimated distribution.


#### 5.1.4. Setting of Privacy Budget

This paper considers the personalized privacy allocation. Here, we use a random function to assign the total privacy budgetɛtotal = m×ɛaverage randomly to the m valid elements for each data owner.


### 5.2. Comparison with LoPub on Adult Dataset

In LoPub [14], the data owners report their whole data with m attributes in their perturbed version. They perturb each dimension of data with a fixed privacy budget which is predefined by the server. After receiving the perturbed data, the server tried to estimate the joint distribution of k attributes 1≤k≤m by using EM-based approach (LoPub-1), Lasso-based approach (LoPub-2), and a hybrid approach (LoPub-3). Please note that EM-based approach (LoPub-1) is not used in the case of k = 1 since the distribution of one attribute can be estimated directly by maximum likelihood estimation. In [14], the authors set a fixed privacy budget ɛ = 2 for each dimension of data, and each owner reports a 4-dimensional perturbed data. When the server estimates the joint distribution of k attributes, the total privacy budget equals to ɛ×k = 2k. In our experiments, we test our scheme with three different settings to make a full comparison with LoPub [14].


#### 5.2.1. Setting#1

Each data owneroi reports an mi-dimensional data perturbed with the total privacy budget ɛtotal = mi×ɛaverage, ɛaverage = 2, and 1 ≤mi≤ 4. Setting#1 is the normal setting of the proposed scheme, where the privacy budgets allocated on the attributes are uncertain. Accordingly, the joint distribution of k = 1, 2, 3, 4 attribute(s) could be estimated in both Situation 1 and Situation 2. The AVDs in Setting#1 are averaged from 10 estimations.


#### 5.2.2. Setting#2

Each owner chooses two dimensions of his data randomly and then perturbed the data with a total privacy budgetɛtotal = 2 ×ɛaverage = 2 × 2 = 4. Then, the joint distribution of k = 1, 2, 3, 4 attribute(s) is estimated. In Setting#2, the privacy budget allocated on the k attributes is equal to that in LoPub. In this way, the estimations of 1 and 2 attribute(s) follow the Situation 1 and the estimations of 3 and 4 attributes follow the Situation 2. The AVDs in Setting#2 are averaged from 10 estimations.


#### 5.2.3. Setting#3

Here, each owner still chooses two dimensions of his data randomly to perturb and upload but sets differentɛaverage when a different number of attributes are considered for distribution estimation. Specifically, the ɛaverage is set to be k when the joint distribution of k attributes is estimated.Figure5(a) shows that our scheme achieves comparable accuracy to LoPub-3 despite that the privacy budgets are personally allocated to the attributes. Figure 5(b) shows that our scheme achieves better efficiency than LoPub, as our method needs not to iteratively scan the data owners’ records. To sum up, the proposed scheme can provide personalized privacy allocation for each owner, which means a less weighted privacy budget. Accordingly, compared with LoPub, our scheme has higher security, lower time consumption, and comparable estimation accuracy. Note that, the results with regard to LoPub are directly taken from [14]. The test for LoPub-1 with k = 4 is not presented in [14] as it consumes too much time.Figure 5
The comparison of the proposed scheme and LoPub on adult dataset. (a) AVD. (b) Computation time.
(a)(b)


### 5.3. Results on Other Three Datasets

In this section, we test our scheme on four real-word datasets under Setting#1 and Setting#2 that are the same as that in Section5.2. Figure 6 shows that, besides the dataset Adult, our scheme achieves similar accuracy on other three datasets. Our scheme allowed the data owner to only share a part of his data. Thus, the joint distribution of the high-dimensional data can only be obtained by synthesizing that of the low-dimensional data. We divide the attributes into two parts and decide the division by maximizing the sum of information entropies of the two parts. Finally, we synthesize the joint distribution by multiplication principle with the assumption that the two divided parts are independent of each other. This could decrease the estimation accuracy of our scheme.Figure 6
Accuracy vs. (k) (ɛaverage = 2). (a) Adult. (b) Abalone. (c) Bank marketing. (d) Car evaluation.
(a)(b)(c)(d)Table2 shows the experimental results of aggregating five-dimensional data. The settings of S#1 and S#2 are similar to the settings of Setting#1 and Setting#2. In S#1, each data owner oi reports an mi-dimensional data perturbed with the total privacy budget ɛtotal = mi×ɛaverage, ɛaverage = 2, and 1 ≤mi≤ 5. In S#2, each owner chooses three dimensions of his data randomly and then perturbed the data with a total privacy budget ɛtotal = 3 ×ɛaverage = 3 × 2 = 6. Then, the joint distribution of k = 1, 2, 3, 4, 5 attribute(s) is estimated.Table 2
Accuracy vs.k (ɛaverage = 2).
Datasets (settings)k = 1k = 2k = 3k = 4k = 5Adult (S#1)0.290.280.470.540.54Adult (S#2)0.290.270.430.480.51Abalone (S#1)0.360.360.420.530.53Abalone (S#2)0.360.360.390.450.49Bank marketing (S#1)0.360.360.420.480.53Bank marketing (S#2)0.360.360.410.430.45Car evaluation (S#1)0.270.340.400.490.52Car evaluation (S#2)0.270.340.370.410.47Figure7 compares the average computation time of two-dimensional data joint distribution estimation on the four real datasets with different average privacy budgets ɛaverage and k = 2. As we can see, the computation takes only a few seconds. Moreover, when ɛaverage is growing, the computation time increasing slowly even is unchanged. This is because the joint distribution is estimated by using LASSO regression, whose time complexity is mainly subject to the total number of records.Figure 7
Computation time vs.ɛaverage (k = 2).


## 5.1. Experimental Setup

### 5.1.1. Environment

All the experiments were performed on a machine with Intel Core i5 CPU 2.50 GHz and 8 GB RAM, using Windows 10 and Python 3.5.2.


### 5.1.2. Datasets

We performed experiments on the following four real datasets, whose parameters are presented in Table1. Abalone [31] contains the size of the abalone through physical measurements. Adult [31] is extracted by Barry Becker from the 1994 Census database. It contains personal information, such as “age,” “relationship,” and “money.” Bank marketing [32] is related with direct marketing campaigns, which are based on phone calls, of a Portuguese banking institution. Car evaluation [31] contains several basic parameters of the car, which is derived from a simple hierarchical decision model. In order to simplify the experiments, we bucket the continuous and nonnumerical data into the discretized ones.Table 1
Datasets.
DatasetsAttribute characteristics#.Records (N)#.Attributes (d)AdultCategorical, integer4884215AbaloneCategorical, integer, real41779Bank marketingReal4521117Car evaluationCategorical17287


### 5.1.3. Evaluation Metrics

The performance of PLDP is measured by the accuracy of the distribution estimation and the time consumption during the estimation. The time consumption contains CPU time and IO cost. As in much previous work, we used the average variant distance (AVD) [33] to evaluate the estimation accuracy, which is defined as(18)AVDP,Q=∑ω∈ΩPω−Qω2,where Ω is the domain of the multidimensional variable, P (ω) denotes the real joint distribution, and Q (ω) denotes the estimated distribution.


### 5.1.4. Setting of Privacy Budget

This paper considers the personalized privacy allocation. Here, we use a random function to assign the total privacy budgetɛtotal = m×ɛaverage randomly to the m valid elements for each data owner.


## 5.1.1. Environment

All the experiments were performed on a machine with Intel Core i5 CPU 2.50 GHz and 8 GB RAM, using Windows 10 and Python 3.5.2.


## 5.1.2. Datasets

We performed experiments on the following four real datasets, whose parameters are presented in Table1. Abalone [31] contains the size of the abalone through physical measurements. Adult [31] is extracted by Barry Becker from the 1994 Census database. It contains personal information, such as “age,” “relationship,” and “money.” Bank marketing [32] is related with direct marketing campaigns, which are based on phone calls, of a Portuguese banking institution. Car evaluation [31] contains several basic parameters of the car, which is derived from a simple hierarchical decision model. In order to simplify the experiments, we bucket the continuous and nonnumerical data into the discretized ones.Table 1
Datasets.
DatasetsAttribute characteristics#.Records (N)#.Attributes (d)AdultCategorical, integer4884215AbaloneCategorical, integer, real41779Bank marketingReal4521117Car evaluationCategorical17287


## 5.1.3. Evaluation Metrics

The performance of PLDP is measured by the accuracy of the distribution estimation and the time consumption during the estimation. The time consumption contains CPU time and IO cost. As in much previous work, we used the average variant distance (AVD) [33] to evaluate the estimation accuracy, which is defined as(18)AVDP,Q=∑ω∈ΩPω−Qω2,where Ω is the domain of the multidimensional variable, P (ω) denotes the real joint distribution, and Q (ω) denotes the estimated distribution.


## 5.1.4. Setting of Privacy Budget

This paper considers the personalized privacy allocation. Here, we use a random function to assign the total privacy budgetɛtotal = m×ɛaverage randomly to the m valid elements for each data owner.


## 5.2. Comparison with LoPub on Adult Dataset

In LoPub [14], the data owners report their whole data with m attributes in their perturbed version. They perturb each dimension of data with a fixed privacy budget which is predefined by the server. After receiving the perturbed data, the server tried to estimate the joint distribution of k attributes 1≤k≤m by using EM-based approach (LoPub-1), Lasso-based approach (LoPub-2), and a hybrid approach (LoPub-3). Please note that EM-based approach (LoPub-1) is not used in the case of k = 1 since the distribution of one attribute can be estimated directly by maximum likelihood estimation. In [14], the authors set a fixed privacy budget ɛ = 2 for each dimension of data, and each owner reports a 4-dimensional perturbed data. When the server estimates the joint distribution of k attributes, the total privacy budget equals to ɛ×k = 2k. In our experiments, we test our scheme with three different settings to make a full comparison with LoPub [14].


### 5.2.1. Setting#1

Each data owneroi reports an mi-dimensional data perturbed with the total privacy budget ɛtotal = mi×ɛaverage, ɛaverage = 2, and 1 ≤mi≤ 4. Setting#1 is the normal setting of the proposed scheme, where the privacy budgets allocated on the attributes are uncertain. Accordingly, the joint distribution of k = 1, 2, 3, 4 attribute(s) could be estimated in both Situation 1 and Situation 2. The AVDs in Setting#1 are averaged from 10 estimations.


### 5.2.2. Setting#2

Each owner chooses two dimensions of his data randomly and then perturbed the data with a total privacy budgetɛtotal = 2 ×ɛaverage = 2 × 2 = 4. Then, the joint distribution of k = 1, 2, 3, 4 attribute(s) is estimated. In Setting#2, the privacy budget allocated on the k attributes is equal to that in LoPub. In this way, the estimations of 1 and 2 attribute(s) follow the Situation 1 and the estimations of 3 and 4 attributes follow the Situation 2. The AVDs in Setting#2 are averaged from 10 estimations.


### 5.2.3. Setting#3

Here, each owner still chooses two dimensions of his data randomly to perturb and upload but sets differentɛaverage when a different number of attributes are considered for distribution estimation. Specifically, the ɛaverage is set to be k when the joint distribution of k attributes is estimated.Figure5(a) shows that our scheme achieves comparable accuracy to LoPub-3 despite that the privacy budgets are personally allocated to the attributes. Figure 5(b) shows that our scheme achieves better efficiency than LoPub, as our method needs not to iteratively scan the data owners’ records. To sum up, the proposed scheme can provide personalized privacy allocation for each owner, which means a less weighted privacy budget. Accordingly, compared with LoPub, our scheme has higher security, lower time consumption, and comparable estimation accuracy. Note that, the results with regard to LoPub are directly taken from [14]. The test for LoPub-1 with k = 4 is not presented in [14] as it consumes too much time.Figure 5
The comparison of the proposed scheme and LoPub on adult dataset. (a) AVD. (b) Computation time.
(a)(b)


## 5.2.1. Setting#1

Each data owneroi reports an mi-dimensional data perturbed with the total privacy budget ɛtotal = mi×ɛaverage, ɛaverage = 2, and 1 ≤mi≤ 4. Setting#1 is the normal setting of the proposed scheme, where the privacy budgets allocated on the attributes are uncertain. Accordingly, the joint distribution of k = 1, 2, 3, 4 attribute(s) could be estimated in both Situation 1 and Situation 2. The AVDs in Setting#1 are averaged from 10 estimations.


## 5.2.2. Setting#2

Each owner chooses two dimensions of his data randomly and then perturbed the data with a total privacy budgetɛtotal = 2 ×ɛaverage = 2 × 2 = 4. Then, the joint distribution of k = 1, 2, 3, 4 attribute(s) is estimated. In Setting#2, the privacy budget allocated on the k attributes is equal to that in LoPub. In this way, the estimations of 1 and 2 attribute(s) follow the Situation 1 and the estimations of 3 and 4 attributes follow the Situation 2. The AVDs in Setting#2 are averaged from 10 estimations.


## 5.2.3. Setting#3

Here, each owner still chooses two dimensions of his data randomly to perturb and upload but sets differentɛaverage when a different number of attributes are considered for distribution estimation. Specifically, the ɛaverage is set to be k when the joint distribution of k attributes is estimated.Figure5(a) shows that our scheme achieves comparable accuracy to LoPub-3 despite that the privacy budgets are personally allocated to the attributes. Figure 5(b) shows that our scheme achieves better efficiency than LoPub, as our method needs not to iteratively scan the data owners’ records. To sum up, the proposed scheme can provide personalized privacy allocation for each owner, which means a less weighted privacy budget. Accordingly, compared with LoPub, our scheme has higher security, lower time consumption, and comparable estimation accuracy. Note that, the results with regard to LoPub are directly taken from [14]. The test for LoPub-1 with k = 4 is not presented in [14] as it consumes too much time.Figure 5
The comparison of the proposed scheme and LoPub on adult dataset. (a) AVD. (b) Computation time.
(a)(b)


## 5.3. Results on Other Three Datasets

In this section, we test our scheme on four real-word datasets under Setting#1 and Setting#2 that are the same as that in Section5.2. Figure 6 shows that, besides the dataset Adult, our scheme achieves similar accuracy on other three datasets. Our scheme allowed the data owner to only share a part of his data. Thus, the joint distribution of the high-dimensional data can only be obtained by synthesizing that of the low-dimensional data. We divide the attributes into two parts and decide the division by maximizing the sum of information entropies of the two parts. Finally, we synthesize the joint distribution by multiplication principle with the assumption that the two divided parts are independent of each other. This could decrease the estimation accuracy of our scheme.Figure 6
Accuracy vs. (k) (ɛaverage = 2). (a) Adult. (b) Abalone. (c) Bank marketing. (d) Car evaluation.
(a)(b)(c)(d)Table2 shows the experimental results of aggregating five-dimensional data. The settings of S#1 and S#2 are similar to the settings of Setting#1 and Setting#2. In S#1, each data owner oi reports an mi-dimensional data perturbed with the total privacy budget ɛtotal = mi×ɛaverage, ɛaverage = 2, and 1 ≤mi≤ 5. In S#2, each owner chooses three dimensions of his data randomly and then perturbed the data with a total privacy budget ɛtotal = 3 ×ɛaverage = 3 × 2 = 6. Then, the joint distribution of k = 1, 2, 3, 4, 5 attribute(s) is estimated.Table 2
Accuracy vs.k (ɛaverage = 2).
Datasets (settings)k = 1k = 2k = 3k = 4k = 5Adult (S#1)0.290.280.470.540.54Adult (S#2)0.290.270.430.480.51Abalone (S#1)0.360.360.420.530.53Abalone (S#2)0.360.360.390.450.49Bank marketing (S#1)0.360.360.420.480.53Bank marketing (S#2)0.360.360.410.430.45Car evaluation (S#1)0.270.340.400.490.52Car evaluation (S#2)0.270.340.370.410.47Figure7 compares the average computation time of two-dimensional data joint distribution estimation on the four real datasets with different average privacy budgets ɛaverage and k = 2. As we can see, the computation takes only a few seconds. Moreover, when ɛaverage is growing, the computation time increasing slowly even is unchanged. This is because the joint distribution is estimated by using LASSO regression, whose time complexity is mainly subject to the total number of records.Figure 7
Computation time vs.ɛaverage (k = 2).


## 6. Conclusion

In this paper, a new privacy notion PLDP is proposed to provide personalized privacy allocation under LDP. PLDP can be regarded as a generalized version of LDP. It allows users only to report their partial data and perturb them with distinct privacy budgets. Then, in order to estimate the joint distribution of multidimensional data, we develop an aggregation algorithm under PLDP, which is based on LASSO regression and information entropy. Finally, experiments on four real datasets validate the superiority and efficiency of PLDP, compared with the traditional LDP.



---

*Source: 6684179-2021-01-28.xml*