# Achieving the Optimalk-Anonymity for Content Privacy in Interactive Cyberphysical Systems

Authors: Jinbao Wang; Ling Tian; Yan Huang; Donghua Yang; Hong Gao
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Modern applications and services leveraged by interactive cyberphysical systems (CPS) are providing significant convenience to our daily life in various aspects at present. Clients submit their requests including query contents to CPS servers to enjoy diverse services such as health care, automatic driving, and location-based services. However, privacy concerns arise at the same time. Content privacy is recognized and a lot of efforts have been made in the literature of privacy preserving in interactive cyberphysical systems such as location-based services. Nevertheless, neither the cloaking based solutions nor existing client based solutions have achieved effective content privacy by optimizing proper content privacy metrics. In this paper we formulate the problem of achieving the optimal content privacy in interactive cyberphysical systems usingk-anonymity solutions based on two content privacy metrics, which are defined using the concepts of entropy and differential privacy. Then we propose an algorithm,Multilayer Alignment (MLA), to establish k-anonymity mechanisms for preserving content privacy in interactive cyberphysical systems. Our proposedMLA is theoretically proved to achieve the optimal content privacy in terms of both the entropy based and the differential privacy mannered content privacy metrics. Evaluation based on real-life datasets is conducted, and the evaluation results validate the effectiveness of our proposed algorithm.


---

## Body

## 1. Introduction

Cyberphysical systems (CPS), which deeply integrate different computing, communication, controlling, and monitoring components, have leveraged modern services in our daily life, like smart grid, intelligent transportation, automatic driving, etc. Recent development of mobile communication and networks has leveraged many modern applications built on interactive cyberphysical systems, in which client software programs or devices take actions according to their interactions with CPS servers. In more details, a client sends a request to the CPS server and is to take actions on receiving the reply from the CPS server. The actions to be taken depend on the reply of CPS servers. Health caring, automatic driving, and location-based services fall into this category of interactive CPS applications. Suppose an old guy Bob is wearing a health caring device, which is connected to a CPS server though mobile Internet. Bob could send “stomachache” to the CPS server for instructions to help him. The CPS server may send a reply telling Bob what to do or where is the nearest hospital. Then Bob takes his action according to the reply. Similar processes could be adopted in applications of automatic driving and location-based services. These modern services over interactive CPS are attractive since they do bring convenience to people’s daily life. However, privacy concerns arise at the same time while users’ requests are submitted to the CPS servers through Internet. These requests disclose users’ query contents to the CPS server and even vicious listeners to the communication channels. Here we refer query content as parameters in users’ requests, such as “stomachache” in Bob’s request to the health caring CPS server. These query contents should be kept as sensitive information for individuals, and the abuse or further leakage of these information will make users vulnerable in respect of private life or even individual security [1].To the privacy concern, content privacy should be recognized to emphasize that users’ query contents should be kept as sensitive information in interactive cyberphysical systems. Many research efforts have been made to protect different types of query contents such as locations and keywords in the literature of interactive cyberphysical systems such as location-based services. The major body of these efforts consists of two parts, cloaking based solutions and client based solutions. Cloaking based solutions employ a trusted server from a third party. When a useru queries with a query content u.content, the query q(u.content) is sent to the trusted server which in the next step generates a cloaking region CR containing u’s location and at least another k-1 users. Here k specifies the level of privacy guarantee. Then the query with CR is sent to the CPS server, and the CPS server could not determine where u is or even whether u is querying. In this process, cloaking based solutions aim to make u indistinguishable from another k-1 users; however it suffers from inherent drawbacks brought by the trusted server, which may become the single point of failure of privacy and the bottleneck of query performance. More seriously, when the CPS server holds certain side information such as the prior probability of query contents, cloaking based solutions will suffer from further privacy breach. To address this issue, client based solutions are presented, aiming at k-anonymity provided by the client side. Reference [2] generates k-1 dummy query contents for continuous scenarios. To prevent the adversary from inferring the actual query content, [2] constrains that the selected dummies should have prior probability larger than a predefined threshold. In practice, it is difficult to determine a proper threshold, and what is more, dummies selected by [2] could still be eliminated if they have quite different prior probability. Reference [3] employs an entropy based privacy metric and generates k-1 dummy locations in random manner. However, the improper dummies could be eliminated from the reported k query contents due to the process of [3]; thus the provided privacy is degraded.In this paper, we investigate the problem of preserving content privacy in interactive cyberphysical systems with a client based solution. To guarantee the utility of requests to the CPS servers, we adoptk-anonymity in order to prevent the adversary from recognizing the actual query content from the k reported contents, since the actual query content must be sent to the CPS server for a meaningful reply. In this process, the major challenge arises in two aspects. First, the k-anonymity provided should be carefully designed so that the adversary is not able to eliminate any query contents. Second, the overall privacy produced by k-anonymity should be optimized. We present two privacy metrics denoted expected entropy and dp-ratio which depict the achieved content privacy using a entropy based concept and a differential privacy mannered measurement, respectively. Then an algorithm,Multilayer Alignment (MLA), which establishes k-anonymity based mechanisms for preserving content privacy is proposed. Given the prior probability of query contents together with an integer k which specifies the privacy level,MLA generates a set of reports, each of which consists of k distinct query contents, together with probability distribution on the report set for each query content. Given any report r submitted to the CPS server,MLA guarantees that the posterior probability of each query content in r is larger than 0. To this end, the adversary is not able to eliminate any query content from a report. Here a report could be taken as a set of different query contents, and we give its formal definition in Section 3. We theoretically introduce the properties ofMLA by proving thatMLA achieves the optimal expected entropy and the optimal dp-ratio at the same time. These attractive properties makeMLA the optimal k-anonymity solution for preserving content privacy in interactive cyberphysical systems. The major contributions of this paper are as follows.(i)
We formulate the problem of achieving the optimalk-anonymity based mechanisms for preserving content privacy in interactive cyberphysical systems. The problem formulation is based on two content privacy metrics with entropy and differential privacy concepts.(ii)
We propose theMultilayer Alignment (MLA) algorithm, which establishes k-anonymity based mechanisms for preserving content privacy. TheMLA algorithm prevents adversaries from eliminating query contents from reports using Bayes inference.(iii)
We prove thatMLA achieves the optimal k-anonymity mechanisms in terms of our presented content privacy metrics simultaneously.(iv)
We evaluate our proposedMLA algorithm using real-life datasets. The evaluation results validate thatMLA achieves effective content privacy in terms of the entropy based and differential privacy mannered content privacy metrics.The rest of this paper is organized as follows. Section2 introduces some necessary preliminaries including the process of preserving content privacy using a client based solution, together with common accepted privacy metrics. Section 3 formulates the problem of achieving the optimal k-anonymity for content privacy in interactive cyberphysical systems. Section 4 proposes theMLA algorithm which establishes effective mechanisms for preserving content privacy. Section 5 theoretically proves that our proposedMLA algorithm achieves the optimal k-anonymity for content privacy in terms of the content privacy metrics introduced in Section 3. Section 6 evaluates theMLA algorithm based on real-life datasets and related work of this paper is discussed in Section 7. Finally, Section 8 concludes this paper.


## 2. Preliminary

This section introduces necessary preliminaries including the process of preserving content privacy using a client basedk-anonymity solution. Then two accepted privacy notions, i.e., k-anonymity and differential privacy, and their corresponding metrics are introduced.


### 2.1. Client Basedk-Anonymity Solution

In the process of a client basedk-anonymity solution for content privacy preservation, k query contents are reported to the CPS server when a user u wants to submit a request. The k reported query contents are determined on u’s device, and no trusted third-party servers are employed; thus the potential single point of privacy failure and query performance bottleneck are eliminated. It is worth noticing that the actual query content u queries should be included in the reported ones; otherwise u is not able to receive a meaningful reply from the CPS server. After receiving the reported query contents, the CPS server processes k queries, one for each reported query content, and then returns the query results to u. Irrelevant results are filtered on u’s mobile device and the actual results are returned to u. In this process, the CPS server receives k distinct query contents instead of a single actual one, and to this end the actual query content is hidden. Nevertheless, careful design is required to avoid ineffective dummies in the reported query contents. The way of generating reports to the CPS server determines the level of content privacy achieved, and this motivates our work.


### 2.2. Privacy Notions and Metrics

#### 2.2.1.k-Anonymity

One widely adopted notion of privacy isk-anonymity, which is firstly introduced in the database community by [4]. The principle of k-anonymity is to hide the sensitive information into k-1 dummies so as to make the adversary unable to recognize the actual one. In the literature of privacy protection in interactive cyberphysical systems, k-anonymity could be categorized into cloaking based solutions and client based solutions. The cloaking based solutions such as [5] employ a third-party but trusted server, which is responsible for hiding the actual user among at least k-1 dummy users by spatial generalization. The client based solutions including more recent work such as [2, 3, 6] perform on users’ devices and generate k-1 dummies in a local manner, in which process certain side information is adopted, for instance, the prior probability of each query content. The trusted server in cloaking based solutions may become a single failure if it is hacked by attackers and it is the performance bottleneck to incur long latency to requests. What is more, most of cloaking based solutions is unaware of side information held by the adversary such as the prior probability of query contents. At the same time, the existing client based solutions provide specious k-anonymity, since the attackers may violate the principle of k-anonymity through rerunning of the algorithms or launching probability inference for each of the k query contents.The quality ofk-anonymity could be measured by the concept of entropy borrowed from the area of information theory. When the CPS server receives a report r={c1,…,ck} consisting of k query contents, the entropy of r is formulated as follows:(1)Hr=-∑i=1kPrci∣rlog⁡Prci∣rNote that the former formulation is slightly different from [3]. Actually, [3] takes the prior probability Pr(ci) as an approximation of the posterior probability Pr(ci∣r).


#### 2.2.2. Differential Privacy

Differential privacy was firstly introduced and applied in statistic databases, and it aims to prevent the leakage of any individual’s information during query processing. Generally speaking, to satisfy the notion of differential privacy, a random algorithm should return query results with similarly distribution for two databases differing with just one tuple. In other words, a single modification in a database brings a minor change to query results under the control of differential privacy. The definition of differential privacy is given below.Definition 1 (differential privacy).
Givenϵ⩾0, a randomized algorithm A satisfies ϵ-differential privacy if for all neighboring databases D and D′, Prob(A(D)∈S)⩽eϵ×Prob(A(D′)∈S). Here S⊆Range(A). Any pair of neighboring databases D and D′ satisfies one of the following conditions: (1) (for unbounded differential privacy) D can be transformed to D′ with exact one insertion or deletion; (2) (for bounded differential privacy) D can be transformed to D′ with exact one modification.The bounded differential privacy prevents distinguishing two datasets with the same size while differing with exact one tuple. The unbounded differential privacy prevents distinguishing two datasets which are the same except that one of them holds exact one additional tuple.The metric for differential privacy is the coefficientϵ in Definition 1. Intuitively, a smaller ϵ leads to a better privacy but larger noise in the query result, while a larger ϵ leads to less noise in the query result but a weaker privacy guarantee.


## 2.1. Client Basedk-Anonymity Solution

In the process of a client basedk-anonymity solution for content privacy preservation, k query contents are reported to the CPS server when a user u wants to submit a request. The k reported query contents are determined on u’s device, and no trusted third-party servers are employed; thus the potential single point of privacy failure and query performance bottleneck are eliminated. It is worth noticing that the actual query content u queries should be included in the reported ones; otherwise u is not able to receive a meaningful reply from the CPS server. After receiving the reported query contents, the CPS server processes k queries, one for each reported query content, and then returns the query results to u. Irrelevant results are filtered on u’s mobile device and the actual results are returned to u. In this process, the CPS server receives k distinct query contents instead of a single actual one, and to this end the actual query content is hidden. Nevertheless, careful design is required to avoid ineffective dummies in the reported query contents. The way of generating reports to the CPS server determines the level of content privacy achieved, and this motivates our work.


## 2.2. Privacy Notions and Metrics

### 2.2.1.k-Anonymity

One widely adopted notion of privacy isk-anonymity, which is firstly introduced in the database community by [4]. The principle of k-anonymity is to hide the sensitive information into k-1 dummies so as to make the adversary unable to recognize the actual one. In the literature of privacy protection in interactive cyberphysical systems, k-anonymity could be categorized into cloaking based solutions and client based solutions. The cloaking based solutions such as [5] employ a third-party but trusted server, which is responsible for hiding the actual user among at least k-1 dummy users by spatial generalization. The client based solutions including more recent work such as [2, 3, 6] perform on users’ devices and generate k-1 dummies in a local manner, in which process certain side information is adopted, for instance, the prior probability of each query content. The trusted server in cloaking based solutions may become a single failure if it is hacked by attackers and it is the performance bottleneck to incur long latency to requests. What is more, most of cloaking based solutions is unaware of side information held by the adversary such as the prior probability of query contents. At the same time, the existing client based solutions provide specious k-anonymity, since the attackers may violate the principle of k-anonymity through rerunning of the algorithms or launching probability inference for each of the k query contents.The quality ofk-anonymity could be measured by the concept of entropy borrowed from the area of information theory. When the CPS server receives a report r={c1,…,ck} consisting of k query contents, the entropy of r is formulated as follows:(1)Hr=-∑i=1kPrci∣rlog⁡Prci∣rNote that the former formulation is slightly different from [3]. Actually, [3] takes the prior probability Pr(ci) as an approximation of the posterior probability Pr(ci∣r).


### 2.2.2. Differential Privacy

Differential privacy was firstly introduced and applied in statistic databases, and it aims to prevent the leakage of any individual’s information during query processing. Generally speaking, to satisfy the notion of differential privacy, a random algorithm should return query results with similarly distribution for two databases differing with just one tuple. In other words, a single modification in a database brings a minor change to query results under the control of differential privacy. The definition of differential privacy is given below.Definition 1 (differential privacy).
Givenϵ⩾0, a randomized algorithm A satisfies ϵ-differential privacy if for all neighboring databases D and D′, Prob(A(D)∈S)⩽eϵ×Prob(A(D′)∈S). Here S⊆Range(A). Any pair of neighboring databases D and D′ satisfies one of the following conditions: (1) (for unbounded differential privacy) D can be transformed to D′ with exact one insertion or deletion; (2) (for bounded differential privacy) D can be transformed to D′ with exact one modification.The bounded differential privacy prevents distinguishing two datasets with the same size while differing with exact one tuple. The unbounded differential privacy prevents distinguishing two datasets which are the same except that one of them holds exact one additional tuple.The metric for differential privacy is the coefficientϵ in Definition 1. Intuitively, a smaller ϵ leads to a better privacy but larger noise in the query result, while a larger ϵ leads to less noise in the query result but a weaker privacy guarantee.


## 2.2.1.k-Anonymity

One widely adopted notion of privacy isk-anonymity, which is firstly introduced in the database community by [4]. The principle of k-anonymity is to hide the sensitive information into k-1 dummies so as to make the adversary unable to recognize the actual one. In the literature of privacy protection in interactive cyberphysical systems, k-anonymity could be categorized into cloaking based solutions and client based solutions. The cloaking based solutions such as [5] employ a third-party but trusted server, which is responsible for hiding the actual user among at least k-1 dummy users by spatial generalization. The client based solutions including more recent work such as [2, 3, 6] perform on users’ devices and generate k-1 dummies in a local manner, in which process certain side information is adopted, for instance, the prior probability of each query content. The trusted server in cloaking based solutions may become a single failure if it is hacked by attackers and it is the performance bottleneck to incur long latency to requests. What is more, most of cloaking based solutions is unaware of side information held by the adversary such as the prior probability of query contents. At the same time, the existing client based solutions provide specious k-anonymity, since the attackers may violate the principle of k-anonymity through rerunning of the algorithms or launching probability inference for each of the k query contents.The quality ofk-anonymity could be measured by the concept of entropy borrowed from the area of information theory. When the CPS server receives a report r={c1,…,ck} consisting of k query contents, the entropy of r is formulated as follows:(1)Hr=-∑i=1kPrci∣rlog⁡Prci∣rNote that the former formulation is slightly different from [3]. Actually, [3] takes the prior probability Pr(ci) as an approximation of the posterior probability Pr(ci∣r).


## 2.2.2. Differential Privacy

Differential privacy was firstly introduced and applied in statistic databases, and it aims to prevent the leakage of any individual’s information during query processing. Generally speaking, to satisfy the notion of differential privacy, a random algorithm should return query results with similarly distribution for two databases differing with just one tuple. In other words, a single modification in a database brings a minor change to query results under the control of differential privacy. The definition of differential privacy is given below.Definition 1 (differential privacy).
Givenϵ⩾0, a randomized algorithm A satisfies ϵ-differential privacy if for all neighboring databases D and D′, Prob(A(D)∈S)⩽eϵ×Prob(A(D′)∈S). Here S⊆Range(A). Any pair of neighboring databases D and D′ satisfies one of the following conditions: (1) (for unbounded differential privacy) D can be transformed to D′ with exact one insertion or deletion; (2) (for bounded differential privacy) D can be transformed to D′ with exact one modification.The bounded differential privacy prevents distinguishing two datasets with the same size while differing with exact one tuple. The unbounded differential privacy prevents distinguishing two datasets which are the same except that one of them holds exact one additional tuple.The metric for differential privacy is the coefficientϵ in Definition 1. Intuitively, a smaller ϵ leads to a better privacy but larger noise in the query result, while a larger ϵ leads to less noise in the query result but a weaker privacy guarantee.


## 3. Problem Definition

This section formulates the problem of achieving the optimalk-anonymity based mechanisms for content privacy in interactive cyberphysical systems. Before introducing the problem definition, we provide several definitions which interpret indispensable concepts for our problem definition.When a user queries a contentc, the client based solution first generates a report consisting of k distinct query contents and then sends the report to the CPS server for response. A formal definition of a report is given as follows.Definition 2 (report).
Given the global setC of query contents and an integer k>0, a report r is a subset of C with size k. When a user queries content c, the generated report r must contain c; i.e., c∈r. Denote the set of all the reports for the given C and k by RCk. The set of reports containing the query content c is denoted by RcC,k.In the rest of this paper, we focus on specifiedC and k, and we also use the notion Rc (instead of RcC,k) to refer to the set of reports containing the query content c.For a client based solution, multiple reports could include an identical query contentc. When c is queried, one of these reports is submitted to the CPS server. The following definition of reporting probability depicts the process of selecting such a report.Definition 3 (reporting probability).
Given the global setC of query contents and an integer k>0, a reporting probability is a function PrCk:C×RCk→[0,1] satisfying the following constraints:(i)
for anyc∈C and r∈Rc,  PrCk(c,r)≥0;(ii)
for anyc∈C, ∑r∈RcPrCk(c,r)=1;(iii)
for anyc∈C and r∉Rc, PrCk(c,r)=0.
The first two constraints in the definition of reporting probability illustrate that when querying a contentc∈C, a report r∈Rc is selected according to the probability PrCk(c,r). The third constraint specifies that a report r will not be selected for c if c∉r.Next we formulate a client based solution as a mechanism in a probabilistic manner based on the concepts of report and reporting probability.Definition 4 (mechanism).
Given the global setC of the query contents and an integer k>0, a k-anonymity based mechanism M consists of two components including the set of reports RCk and the reporting probability PrCk. When a user queries content c∈C, M randomly selects a report r from RCk and the probability of selecting r is PrCk(c,r).The above definition of ak-anonymity based mechanism looks speciously strange; nevertheless existing solutions could be taken as instances of the above definition. We could specify the reporting probability using additional parameters in these works, for instance, the predefined prior probability threshold σ in [2].This paper adopts two privacy metrics to measure a givenk-anonymity based mechanism M in terms of privacy. As formulated in the following definition, the first metric integrates entropy measures of all the reports generated by M.Definition 5 (expected entropy).
Given the global setC of query contents, an integer k>0 and the prior probability of query contents as pr(.), the expected entropy of mechanism M(RCk,PrCk) is calculated as(2)HEM=∑r∈RCkPrrHr=∑r∈RCk∑c∈rprcPrCkc,r∑c∈r-Prc∣rlog⁡Prc∣r.
HerePr(c∣r)=pr(c)PrCk(c,r)/∑i∈rpr(i)PrCk(i,r), and it is the posterior probability of c given report r. HE(M) measures the achieved content privacy overall by considering all the generated reports. The probability of each report is taken as the weight, and the entropy of each report is integrated in the above formulation. A larger HE(M) indicates that a better content privacy is obtained with respect to the concept of entropy.The second metric incorporates the notion ofk-anonymity and differential privacy. It measures a mechanism with the most distinguishable pairs of query contents in the generated reports. The following definition formulates our second metric named dp-coefficient.Definition 6 (dp-coefficient).
Given the global setC of query contents, an integer k>0, and the prior probability of query contents as pr(.), the dp-coefficient of mechanism M(RCk,PrCk) is calculated as(3)dpcM=maxr∈RCk,i,j∈r⁡ln⁡Pri∣rPrj∣r.
Here the termsPr(i∣r) and Pr(j∣r) are the posterior probability of query contents i and j given a report r, and they could be calculated in the same way as the calculation of Pr(c∣r) described above.Based on the content privacy metrics, e.g., expected entropy and differential privacy coefficient, we formulate the problem of achieving the optimalk-anonymity for content privacy in interactive cyberphysical systems as follows.Problem Definition.Given the global set C of query contents, an integer k>0, and the prior probability of query contents as pr(.), compute a mechanism M(RCk,PrCk) with the optimal content privacy. The optimal content privacy is achieved if HE(M) is maximized.H E ( M ) and dpc(M) depict the content privacy achieved by M from the holistic and individual point of view, respectively. Although our problem definition aims at the optimized expected entropy, in the next section we propose an algorithm which achieves the optimal expected entropy and the optimal dp-coefficient simultaneously.


## 4. Achieving the Optimalk-Anonymity

This section in first provides a short discuss on a naïve solution to the problem defined in Section3. Then we propose ourMultilayer Alignment (MLA) algorithm which achieves the optimal k-anonymity for content privacy in interactive cyberphysical systems.MLA exhibits an attractive property that it achieves the maximized expected entropy and the minimized dp-coefficient simultaneously.


### 4.1. A Naïve Solution

According to the problem definition in Section3, the essential challenge of establishing the optimal mechanisms lies in building the reporting probability PrCk:C×RCk→[0,1]. A naïve approach to achieve the optimal k-anonymity is formulating the problem using nonlinear-programming technique with linear constraints in Definition 3, and expected entropy or dp-coefficient is used as the optimizing objective. However, the nonlinear-programming formulation employs |C|k×|C| variables each of which stands for an entry in PrCk. When |C| grows to 100 and k is set to 10, there will be more than 1015 variables. Thus this naïve approach is impractical due to its computation expense.


### 4.2. The Multilayer Alignment Algorithm

MLA computes the optimal k-anonymity mechanism in two phases, namely, (1)Segment Alignment and (2)Mechanism Initiation. The major idea ofMLA is to generate a mechanism where query contents have as similar posterior probability as possible in each report. To accomplish this goal in a holistic manner,Segment Alignment amortizes each query content with large prior probability to multiple query contents with small prior probability. What is more, the reports generated byMechanism Initiation have the same distribution of posterior probability of the k included query contents. Next we introduce the two phases ofMLA.


#### 4.2.1. Segment Alignment

Given the prior probabilitypr(.) of query contents,MLA represents each query content ci∈C using a segment si with length |si|=pr(ci). The segments for all the query contents are sorted in descend order, and denote the sorted set as Seg={s1,…,sm}. ThenMLA aligns the segments onto k layers in order. The aligning process has two modes, i.e., aligning dominant and aligning dominated. At the beginning of aligning, the mode of aligning dominant is active. The number of rest layers (denoted restlayer) is set to k.MLA checks whether the current segment is dominant. When aligning si, si is dominant if the condition |si|×restlayer>∑i≥j≥m|sj| holds. If the current segment si is dominant,MLA aligns si onto the current layer and si takes up the entire layer. The aligning stays in mode aligning dominant, and segment si+1 is taken as the current segment when the aligning continues. If the current segment si is not dominant, the aligning turns to mode aligning dominated. ThenMLA sets the length of each of the remaining layers as ∑i≥j≥m|sj|/restlayer, and it aligns si,…,sm along the rest layers. When aligning a segment sj and the current layer has blank length lb less than |sj|, sj is divided into two parts with lengths lb and |sj|-lb. The first part is aligned onto the current layer, and the second part is aligned onto the beginning of the next layer. In the mode of aligning dominated,MLA goes on aligning all the remaining segments, and it never turns back to mode aligning dominant. After all the remaining segments are aligned, the first phase ofMLA terminates andMLA continues to the second phase.Example 7.
SupposeC={c1,c2,c3,c4,c5,c6,c7} and Alice wants to query c1 nearby, and the prior probability of each query content at her location is given as follows: pr(c1)=0.4, pr(c2)=0.15, pr(c3)=0.15, pr(c4)=0.1, pr(c5)=0.1, pr(c6)=0.05, and pr(c7)=0.05. Alice desires for 4-anonymity (k=4), and what is the optimal mechanism for Alice?Here we use the instance in Example7 to illustrate the process of segment aligning. There are 4 layers in the process of aligning. The segment for c1 is aligned in mode aligning dominant since pr(c1)×k>1. The segment for the remaining query contents is aligned in mode aligning dominated, and each of the remaining layers is at length 1-0.4/4-1=0.2. The aligning result is shown in Figure 1.Figure 1
Segment aligning for the instance consisting of 7 query contents in Example7. The first layer is taken up by c1 under aligning dominant mode, and the remaining 3 layers are taken up by c2, c3, c4, c5, c6, and c7, under aligning dominated mode. Here cij means the jth part of content i.


#### 4.2.2. Mechanism Initiation

Denote the length of theith layer by Li, where i=1,…,k. The second phase ofMLA first shrinks the length of each layer, and the ith layer is shrunk by ratio Li/Lk. The shrinking ratio of the ith layer is recorded as ratioi. All the layers have the same length after shrinking. In the next step,MLA sets a vertical line at the beginning of each layer. Then the vertical line moves to the right until it touches the first point on any layer at which a segment ends. Then the scanned parts of the k layers are packed into a report. Denote the scanned part on the ith layer with length lis; then the probability of this report is ∑1≥i≥klis×ratioi and the posterior probability of the query content on the ith layer is lis×ratioi/∑1≥j≥kljs×ratioj. The vertical line continues moving to the right andMLA packs the next report when any segment ends on a layer. The process terminates after the vertical line moves to the end of each layer and generates the last report. Continue with Example 7 as shown in Figure 2, the shrinking ratios of the 4 layers are 2, 1, 1 and 1. Then a vertical line starts moving to the right from the left end of all the layers. It first touches the end points of c32 and c5 on layers 3 and 4, respectively, and a report r1={c1,c2,c3,c5} is generated. Then it keeps moving to the right and touches the end points of c2 and c6 on layers 2 and 4, respectively, and report r2={c1,c2,c4,c6} is generated. Finally, the vertical line touches the end points of all the layers and generates the last report r3={c1,c3,c4,c7}. In the end,MLA generates 3 reports including r1={c1,c2,c3,c5}, r2={c1,c2,c4,c6}, and r3={c1,c3,c4,c7}. The reporting probability is given in Table 1. Take c1, for instance; half of its prior probability is assigned into report r1, and one-fourth of its prior probability is assigned to reports r2 and r3. Thus the reporting probability of c1 for reports r1, r2, and r3 is 1/2, 1/4, and 1/4, respectively, as shown in Table 1. The reporting probability of other contents could be calculated in the same manner.Table 1
The reporting probability for Example7.
Content / Report r 1 r 2 r3 c1 1/2 1/4 1/4 c2 2/3 1/3 0 c3 2/3 0 1/3 c4 0 1/2 1/2 c5 1 0 0 c6 0 1 0 c7 0 0 1Figure 2
The first layer is shrunk by ratio of 2, and remaining layers keep unchanged. Mechanism initiation produces three reportsr1={c1,c2,c3,c5}, r2={c1,c2,c4,c6}, and r3={c1,c3,c4,c7}. When querying c1, the mechanism adopts reporting distribution Pr(r1∣c1)=0.5, Pr(r2∣c1)=0.25 and Pr(r3∣c1)=0.25.
(a)
After shrinking (b)
Mechanism initiationThe pseudocode of theMultilayer Alignment algorithm is shown in Algorithm 1. In the beginning,MLA sorts the query contents in C according to their prior probability in descending order (line 1). Then it initiates necessary structures and variables. L1,…,Lk stores the alignment of k layers (lines 2-3). Variable lcusor indicates the layer being processed (line 4), and isDominant indicates whether the alignment is under aligning dominant mode (line 5). Variable partial indicates how much prior probability of the current query content is taken up by the last layer while average indicates the length of each layer processed in dominated mode, and they are initiated in line 6. Array Len keeping the lengths of k layers is initiated in line 7. The loop in lines 8-28 aligns query contents in C in order onto k layers. The aligning mode is set dominant in line 5 before processing the first query content. Under aligning dominant mode,MLA checks whether ci should be aligned under aligning dominant mode. If the answer is yes, a segment for ci is created with length pr(ci) and it is added to the list Llcusor for the current layer. Here the constructor of segment specifies the label and the length for a segment. Then the alignment of ci and the current layer terminates (lines 10-12). If ci should not be aligned under aligning dominant mode,MLA turns to the mode of aligning dominated and calculates the length of each of the remaining layers as average (lines 13-15). In aligning dominated mode,MLA executes the code in lines 16-28. If ci could be entirely aligned onto the current layer (line 16),MLA creates a segment for ci with length pr(ci), and adds it to list Llcusor (line 17). The length of the current layer and partial are updated (lines 18-19). If the current layer does not have sufficient space to hold ci, ci is split into two segments. Lines 21-23 align the first segment onto the current layer, and lines 26-28 align the second segment onto the next layer. Lines 24-25 deal with a special case where ci exactly uses up the space of the current layer. By here the Segment Alignment terminates and theMLA goes to the phase of Mechanism Initiation. It packs the heads of k lists Li into a report r (lines 30-31). ThenMLA determines the movement length ratio of the vertical line to the right as step (line 32). The reporting probability related to the current report is calculated in line 35. For each layer,MLA updates the length of the head. If the head of a layer is entirely packed into a report, it is popped from the list (lines 36-39).Algorithm 1: Multilayer Alignment.
Input: query content set C, integer k<|I|, the prior probability pr(.) of query content Output: the reporting probability PrCk 1  sort C according to pr(.) in descend order; 2  for  1≤i≤k  do 3 initiate a list Li; 4  lcusor=1; 5  isDominant=true; 6  partial,average=0; 7  initiate an integer array Len with k values of 0; 8  for  1≤i≤|C|  do 9  if  isDominant  then 10  if  pr(ci)≥sumpr/k+1-lcusor  then 11  L l c u s o r + + . a d d ( new  Segment ( i , p r ( c i ) ) ); 12  continue; 13  else 14  i s D o m i n a n t = f a l s e; 15  a v e r a g e = ∑ i ≤ j ≤ | C | p r ( c j ) / k + 1 - l c u s o r; 16  if  pr(ci)-partial<average-Len[lcusor]  then 17  L l c u s o r . a d d ( new  Segment ( i , p r ( c i ) - p a r t i a l ) ); 18  L e n [ l c u s o r ] = L e n [ l c u s o r ] + p r ( c i ); 19  p a r t i a l = 0; 20  else 21  s e g = new  Segment ( i , a v e r a g e - L e n [ l c u s o r ] ); 22  L l c u s o r . a d d ( s e g ) ); 23  L e n [ l c u s o r + + ] = a v e r a g e; 24  if  seg.length==pr(ci)  then 25  continue; 26  s e g ′ = new  Segment ( i , p r ( c i ) - s e g . l e n g t h ); 27  L l c u s o r . a d d ( s e g ′ ); 28  L e n l c u s o r = s e g ′ . l e n g t h; 29  while  L1≠⌀  do 30 initiate a report r; 31 add the heads of L1,…,Lk to r; 32  s t e p = m i n 1 ≤ i ≤ k  L i . h e a d . l e n g t h / L e n [ i ]; 33  for  1≤i≤k  do 34  j = L i . h e a d . l a b e l; 35  P r C k ( c j , r ) = s t e p × L e n [ i ] / p r ( c j ); 36  if  Li.head.length==step×Len[i]  then 37  L i . p o p ( ); 38  else 39  L i . h e a d . l e n g t h - = s t e p × L e n [ i ]; 40  return  PrCk;The computation cost ofMLA consists of three parts, sorting C and initiating variables, Segment Alignment, and Mechanism Initiation. The first part costs O(Clog⁡|C|). Segment Alignment costs O(k+|C|) since at most k+|C| segments are aligned, and each alignment costs a constant time. Mechanism Initiation costs O(k(k+|C|)) which is dominated by packing at most k+|C| reports (each packing costs O(k)) and calculating at most k(k+|C|) entries for PrCk. In practice, k should be set smaller than |C|. The total cost ofMLA is O(Clog⁡|C|+k|C|).


## 4.1. A Naïve Solution

According to the problem definition in Section3, the essential challenge of establishing the optimal mechanisms lies in building the reporting probability PrCk:C×RCk→[0,1]. A naïve approach to achieve the optimal k-anonymity is formulating the problem using nonlinear-programming technique with linear constraints in Definition 3, and expected entropy or dp-coefficient is used as the optimizing objective. However, the nonlinear-programming formulation employs |C|k×|C| variables each of which stands for an entry in PrCk. When |C| grows to 100 and k is set to 10, there will be more than 1015 variables. Thus this naïve approach is impractical due to its computation expense.


## 4.2. The Multilayer Alignment Algorithm

MLA computes the optimal k-anonymity mechanism in two phases, namely, (1)Segment Alignment and (2)Mechanism Initiation. The major idea ofMLA is to generate a mechanism where query contents have as similar posterior probability as possible in each report. To accomplish this goal in a holistic manner,Segment Alignment amortizes each query content with large prior probability to multiple query contents with small prior probability. What is more, the reports generated byMechanism Initiation have the same distribution of posterior probability of the k included query contents. Next we introduce the two phases ofMLA.


### 4.2.1. Segment Alignment

Given the prior probabilitypr(.) of query contents,MLA represents each query content ci∈C using a segment si with length |si|=pr(ci). The segments for all the query contents are sorted in descend order, and denote the sorted set as Seg={s1,…,sm}. ThenMLA aligns the segments onto k layers in order. The aligning process has two modes, i.e., aligning dominant and aligning dominated. At the beginning of aligning, the mode of aligning dominant is active. The number of rest layers (denoted restlayer) is set to k.MLA checks whether the current segment is dominant. When aligning si, si is dominant if the condition |si|×restlayer>∑i≥j≥m|sj| holds. If the current segment si is dominant,MLA aligns si onto the current layer and si takes up the entire layer. The aligning stays in mode aligning dominant, and segment si+1 is taken as the current segment when the aligning continues. If the current segment si is not dominant, the aligning turns to mode aligning dominated. ThenMLA sets the length of each of the remaining layers as ∑i≥j≥m|sj|/restlayer, and it aligns si,…,sm along the rest layers. When aligning a segment sj and the current layer has blank length lb less than |sj|, sj is divided into two parts with lengths lb and |sj|-lb. The first part is aligned onto the current layer, and the second part is aligned onto the beginning of the next layer. In the mode of aligning dominated,MLA goes on aligning all the remaining segments, and it never turns back to mode aligning dominant. After all the remaining segments are aligned, the first phase ofMLA terminates andMLA continues to the second phase.Example 7.
SupposeC={c1,c2,c3,c4,c5,c6,c7} and Alice wants to query c1 nearby, and the prior probability of each query content at her location is given as follows: pr(c1)=0.4, pr(c2)=0.15, pr(c3)=0.15, pr(c4)=0.1, pr(c5)=0.1, pr(c6)=0.05, and pr(c7)=0.05. Alice desires for 4-anonymity (k=4), and what is the optimal mechanism for Alice?Here we use the instance in Example7 to illustrate the process of segment aligning. There are 4 layers in the process of aligning. The segment for c1 is aligned in mode aligning dominant since pr(c1)×k>1. The segment for the remaining query contents is aligned in mode aligning dominated, and each of the remaining layers is at length 1-0.4/4-1=0.2. The aligning result is shown in Figure 1.Figure 1
Segment aligning for the instance consisting of 7 query contents in Example7. The first layer is taken up by c1 under aligning dominant mode, and the remaining 3 layers are taken up by c2, c3, c4, c5, c6, and c7, under aligning dominated mode. Here cij means the jth part of content i.


### 4.2.2. Mechanism Initiation

Denote the length of theith layer by Li, where i=1,…,k. The second phase ofMLA first shrinks the length of each layer, and the ith layer is shrunk by ratio Li/Lk. The shrinking ratio of the ith layer is recorded as ratioi. All the layers have the same length after shrinking. In the next step,MLA sets a vertical line at the beginning of each layer. Then the vertical line moves to the right until it touches the first point on any layer at which a segment ends. Then the scanned parts of the k layers are packed into a report. Denote the scanned part on the ith layer with length lis; then the probability of this report is ∑1≥i≥klis×ratioi and the posterior probability of the query content on the ith layer is lis×ratioi/∑1≥j≥kljs×ratioj. The vertical line continues moving to the right andMLA packs the next report when any segment ends on a layer. The process terminates after the vertical line moves to the end of each layer and generates the last report. Continue with Example 7 as shown in Figure 2, the shrinking ratios of the 4 layers are 2, 1, 1 and 1. Then a vertical line starts moving to the right from the left end of all the layers. It first touches the end points of c32 and c5 on layers 3 and 4, respectively, and a report r1={c1,c2,c3,c5} is generated. Then it keeps moving to the right and touches the end points of c2 and c6 on layers 2 and 4, respectively, and report r2={c1,c2,c4,c6} is generated. Finally, the vertical line touches the end points of all the layers and generates the last report r3={c1,c3,c4,c7}. In the end,MLA generates 3 reports including r1={c1,c2,c3,c5}, r2={c1,c2,c4,c6}, and r3={c1,c3,c4,c7}. The reporting probability is given in Table 1. Take c1, for instance; half of its prior probability is assigned into report r1, and one-fourth of its prior probability is assigned to reports r2 and r3. Thus the reporting probability of c1 for reports r1, r2, and r3 is 1/2, 1/4, and 1/4, respectively, as shown in Table 1. The reporting probability of other contents could be calculated in the same manner.Table 1
The reporting probability for Example7.
Content / Report r 1 r 2 r3 c1 1/2 1/4 1/4 c2 2/3 1/3 0 c3 2/3 0 1/3 c4 0 1/2 1/2 c5 1 0 0 c6 0 1 0 c7 0 0 1Figure 2
The first layer is shrunk by ratio of 2, and remaining layers keep unchanged. Mechanism initiation produces three reportsr1={c1,c2,c3,c5}, r2={c1,c2,c4,c6}, and r3={c1,c3,c4,c7}. When querying c1, the mechanism adopts reporting distribution Pr(r1∣c1)=0.5, Pr(r2∣c1)=0.25 and Pr(r3∣c1)=0.25.
(a)
After shrinking (b)
Mechanism initiationThe pseudocode of theMultilayer Alignment algorithm is shown in Algorithm 1. In the beginning,MLA sorts the query contents in C according to their prior probability in descending order (line 1). Then it initiates necessary structures and variables. L1,…,Lk stores the alignment of k layers (lines 2-3). Variable lcusor indicates the layer being processed (line 4), and isDominant indicates whether the alignment is under aligning dominant mode (line 5). Variable partial indicates how much prior probability of the current query content is taken up by the last layer while average indicates the length of each layer processed in dominated mode, and they are initiated in line 6. Array Len keeping the lengths of k layers is initiated in line 7. The loop in lines 8-28 aligns query contents in C in order onto k layers. The aligning mode is set dominant in line 5 before processing the first query content. Under aligning dominant mode,MLA checks whether ci should be aligned under aligning dominant mode. If the answer is yes, a segment for ci is created with length pr(ci) and it is added to the list Llcusor for the current layer. Here the constructor of segment specifies the label and the length for a segment. Then the alignment of ci and the current layer terminates (lines 10-12). If ci should not be aligned under aligning dominant mode,MLA turns to the mode of aligning dominated and calculates the length of each of the remaining layers as average (lines 13-15). In aligning dominated mode,MLA executes the code in lines 16-28. If ci could be entirely aligned onto the current layer (line 16),MLA creates a segment for ci with length pr(ci), and adds it to list Llcusor (line 17). The length of the current layer and partial are updated (lines 18-19). If the current layer does not have sufficient space to hold ci, ci is split into two segments. Lines 21-23 align the first segment onto the current layer, and lines 26-28 align the second segment onto the next layer. Lines 24-25 deal with a special case where ci exactly uses up the space of the current layer. By here the Segment Alignment terminates and theMLA goes to the phase of Mechanism Initiation. It packs the heads of k lists Li into a report r (lines 30-31). ThenMLA determines the movement length ratio of the vertical line to the right as step (line 32). The reporting probability related to the current report is calculated in line 35. For each layer,MLA updates the length of the head. If the head of a layer is entirely packed into a report, it is popped from the list (lines 36-39).Algorithm 1: Multilayer Alignment.
Input: query content set C, integer k<|I|, the prior probability pr(.) of query content Output: the reporting probability PrCk 1  sort C according to pr(.) in descend order; 2  for  1≤i≤k  do 3 initiate a list Li; 4  lcusor=1; 5  isDominant=true; 6  partial,average=0; 7  initiate an integer array Len with k values of 0; 8  for  1≤i≤|C|  do 9  if  isDominant  then 10  if  pr(ci)≥sumpr/k+1-lcusor  then 11  L l c u s o r + + . a d d ( new  Segment ( i , p r ( c i ) ) ); 12  continue; 13  else 14  i s D o m i n a n t = f a l s e; 15  a v e r a g e = ∑ i ≤ j ≤ | C | p r ( c j ) / k + 1 - l c u s o r; 16  if  pr(ci)-partial<average-Len[lcusor]  then 17  L l c u s o r . a d d ( new  Segment ( i , p r ( c i ) - p a r t i a l ) ); 18  L e n [ l c u s o r ] = L e n [ l c u s o r ] + p r ( c i ); 19  p a r t i a l = 0; 20  else 21  s e g = new  Segment ( i , a v e r a g e - L e n [ l c u s o r ] ); 22  L l c u s o r . a d d ( s e g ) ); 23  L e n [ l c u s o r + + ] = a v e r a g e; 24  if  seg.length==pr(ci)  then 25  continue; 26  s e g ′ = new  Segment ( i , p r ( c i ) - s e g . l e n g t h ); 27  L l c u s o r . a d d ( s e g ′ ); 28  L e n l c u s o r = s e g ′ . l e n g t h; 29  while  L1≠⌀  do 30 initiate a report r; 31 add the heads of L1,…,Lk to r; 32  s t e p = m i n 1 ≤ i ≤ k  L i . h e a d . l e n g t h / L e n [ i ]; 33  for  1≤i≤k  do 34  j = L i . h e a d . l a b e l; 35  P r C k ( c j , r ) = s t e p × L e n [ i ] / p r ( c j ); 36  if  Li.head.length==step×Len[i]  then 37  L i . p o p ( ); 38  else 39  L i . h e a d . l e n g t h - = s t e p × L e n [ i ]; 40  return  PrCk;The computation cost ofMLA consists of three parts, sorting C and initiating variables, Segment Alignment, and Mechanism Initiation. The first part costs O(Clog⁡|C|). Segment Alignment costs O(k+|C|) since at most k+|C| segments are aligned, and each alignment costs a constant time. Mechanism Initiation costs O(k(k+|C|)) which is dominated by packing at most k+|C| reports (each packing costs O(k)) and calculating at most k(k+|C|) entries for PrCk. In practice, k should be set smaller than |C|. The total cost ofMLA is O(Clog⁡|C|+k|C|).


## 4.2.1. Segment Alignment

Given the prior probabilitypr(.) of query contents,MLA represents each query content ci∈C using a segment si with length |si|=pr(ci). The segments for all the query contents are sorted in descend order, and denote the sorted set as Seg={s1,…,sm}. ThenMLA aligns the segments onto k layers in order. The aligning process has two modes, i.e., aligning dominant and aligning dominated. At the beginning of aligning, the mode of aligning dominant is active. The number of rest layers (denoted restlayer) is set to k.MLA checks whether the current segment is dominant. When aligning si, si is dominant if the condition |si|×restlayer>∑i≥j≥m|sj| holds. If the current segment si is dominant,MLA aligns si onto the current layer and si takes up the entire layer. The aligning stays in mode aligning dominant, and segment si+1 is taken as the current segment when the aligning continues. If the current segment si is not dominant, the aligning turns to mode aligning dominated. ThenMLA sets the length of each of the remaining layers as ∑i≥j≥m|sj|/restlayer, and it aligns si,…,sm along the rest layers. When aligning a segment sj and the current layer has blank length lb less than |sj|, sj is divided into two parts with lengths lb and |sj|-lb. The first part is aligned onto the current layer, and the second part is aligned onto the beginning of the next layer. In the mode of aligning dominated,MLA goes on aligning all the remaining segments, and it never turns back to mode aligning dominant. After all the remaining segments are aligned, the first phase ofMLA terminates andMLA continues to the second phase.Example 7.
SupposeC={c1,c2,c3,c4,c5,c6,c7} and Alice wants to query c1 nearby, and the prior probability of each query content at her location is given as follows: pr(c1)=0.4, pr(c2)=0.15, pr(c3)=0.15, pr(c4)=0.1, pr(c5)=0.1, pr(c6)=0.05, and pr(c7)=0.05. Alice desires for 4-anonymity (k=4), and what is the optimal mechanism for Alice?Here we use the instance in Example7 to illustrate the process of segment aligning. There are 4 layers in the process of aligning. The segment for c1 is aligned in mode aligning dominant since pr(c1)×k>1. The segment for the remaining query contents is aligned in mode aligning dominated, and each of the remaining layers is at length 1-0.4/4-1=0.2. The aligning result is shown in Figure 1.Figure 1
Segment aligning for the instance consisting of 7 query contents in Example7. The first layer is taken up by c1 under aligning dominant mode, and the remaining 3 layers are taken up by c2, c3, c4, c5, c6, and c7, under aligning dominated mode. Here cij means the jth part of content i.


## 4.2.2. Mechanism Initiation

Denote the length of theith layer by Li, where i=1,…,k. The second phase ofMLA first shrinks the length of each layer, and the ith layer is shrunk by ratio Li/Lk. The shrinking ratio of the ith layer is recorded as ratioi. All the layers have the same length after shrinking. In the next step,MLA sets a vertical line at the beginning of each layer. Then the vertical line moves to the right until it touches the first point on any layer at which a segment ends. Then the scanned parts of the k layers are packed into a report. Denote the scanned part on the ith layer with length lis; then the probability of this report is ∑1≥i≥klis×ratioi and the posterior probability of the query content on the ith layer is lis×ratioi/∑1≥j≥kljs×ratioj. The vertical line continues moving to the right andMLA packs the next report when any segment ends on a layer. The process terminates after the vertical line moves to the end of each layer and generates the last report. Continue with Example 7 as shown in Figure 2, the shrinking ratios of the 4 layers are 2, 1, 1 and 1. Then a vertical line starts moving to the right from the left end of all the layers. It first touches the end points of c32 and c5 on layers 3 and 4, respectively, and a report r1={c1,c2,c3,c5} is generated. Then it keeps moving to the right and touches the end points of c2 and c6 on layers 2 and 4, respectively, and report r2={c1,c2,c4,c6} is generated. Finally, the vertical line touches the end points of all the layers and generates the last report r3={c1,c3,c4,c7}. In the end,MLA generates 3 reports including r1={c1,c2,c3,c5}, r2={c1,c2,c4,c6}, and r3={c1,c3,c4,c7}. The reporting probability is given in Table 1. Take c1, for instance; half of its prior probability is assigned into report r1, and one-fourth of its prior probability is assigned to reports r2 and r3. Thus the reporting probability of c1 for reports r1, r2, and r3 is 1/2, 1/4, and 1/4, respectively, as shown in Table 1. The reporting probability of other contents could be calculated in the same manner.Table 1
The reporting probability for Example7.
Content / Report r 1 r 2 r3 c1 1/2 1/4 1/4 c2 2/3 1/3 0 c3 2/3 0 1/3 c4 0 1/2 1/2 c5 1 0 0 c6 0 1 0 c7 0 0 1Figure 2
The first layer is shrunk by ratio of 2, and remaining layers keep unchanged. Mechanism initiation produces three reportsr1={c1,c2,c3,c5}, r2={c1,c2,c4,c6}, and r3={c1,c3,c4,c7}. When querying c1, the mechanism adopts reporting distribution Pr(r1∣c1)=0.5, Pr(r2∣c1)=0.25 and Pr(r3∣c1)=0.25.
(a)
After shrinking (b)
Mechanism initiationThe pseudocode of theMultilayer Alignment algorithm is shown in Algorithm 1. In the beginning,MLA sorts the query contents in C according to their prior probability in descending order (line 1). Then it initiates necessary structures and variables. L1,…,Lk stores the alignment of k layers (lines 2-3). Variable lcusor indicates the layer being processed (line 4), and isDominant indicates whether the alignment is under aligning dominant mode (line 5). Variable partial indicates how much prior probability of the current query content is taken up by the last layer while average indicates the length of each layer processed in dominated mode, and they are initiated in line 6. Array Len keeping the lengths of k layers is initiated in line 7. The loop in lines 8-28 aligns query contents in C in order onto k layers. The aligning mode is set dominant in line 5 before processing the first query content. Under aligning dominant mode,MLA checks whether ci should be aligned under aligning dominant mode. If the answer is yes, a segment for ci is created with length pr(ci) and it is added to the list Llcusor for the current layer. Here the constructor of segment specifies the label and the length for a segment. Then the alignment of ci and the current layer terminates (lines 10-12). If ci should not be aligned under aligning dominant mode,MLA turns to the mode of aligning dominated and calculates the length of each of the remaining layers as average (lines 13-15). In aligning dominated mode,MLA executes the code in lines 16-28. If ci could be entirely aligned onto the current layer (line 16),MLA creates a segment for ci with length pr(ci), and adds it to list Llcusor (line 17). The length of the current layer and partial are updated (lines 18-19). If the current layer does not have sufficient space to hold ci, ci is split into two segments. Lines 21-23 align the first segment onto the current layer, and lines 26-28 align the second segment onto the next layer. Lines 24-25 deal with a special case where ci exactly uses up the space of the current layer. By here the Segment Alignment terminates and theMLA goes to the phase of Mechanism Initiation. It packs the heads of k lists Li into a report r (lines 30-31). ThenMLA determines the movement length ratio of the vertical line to the right as step (line 32). The reporting probability related to the current report is calculated in line 35. For each layer,MLA updates the length of the head. If the head of a layer is entirely packed into a report, it is popped from the list (lines 36-39).Algorithm 1: Multilayer Alignment.
Input: query content set C, integer k<|I|, the prior probability pr(.) of query content Output: the reporting probability PrCk 1  sort C according to pr(.) in descend order; 2  for  1≤i≤k  do 3 initiate a list Li; 4  lcusor=1; 5  isDominant=true; 6  partial,average=0; 7  initiate an integer array Len with k values of 0; 8  for  1≤i≤|C|  do 9  if  isDominant  then 10  if  pr(ci)≥sumpr/k+1-lcusor  then 11  L l c u s o r + + . a d d ( new  Segment ( i , p r ( c i ) ) ); 12  continue; 13  else 14  i s D o m i n a n t = f a l s e; 15  a v e r a g e = ∑ i ≤ j ≤ | C | p r ( c j ) / k + 1 - l c u s o r; 16  if  pr(ci)-partial<average-Len[lcusor]  then 17  L l c u s o r . a d d ( new  Segment ( i , p r ( c i ) - p a r t i a l ) ); 18  L e n [ l c u s o r ] = L e n [ l c u s o r ] + p r ( c i ); 19  p a r t i a l = 0; 20  else 21  s e g = new  Segment ( i , a v e r a g e - L e n [ l c u s o r ] ); 22  L l c u s o r . a d d ( s e g ) ); 23  L e n [ l c u s o r + + ] = a v e r a g e; 24  if  seg.length==pr(ci)  then 25  continue; 26  s e g ′ = new  Segment ( i , p r ( c i ) - s e g . l e n g t h ); 27  L l c u s o r . a d d ( s e g ′ ); 28  L e n l c u s o r = s e g ′ . l e n g t h; 29  while  L1≠⌀  do 30 initiate a report r; 31 add the heads of L1,…,Lk to r; 32  s t e p = m i n 1 ≤ i ≤ k  L i . h e a d . l e n g t h / L e n [ i ]; 33  for  1≤i≤k  do 34  j = L i . h e a d . l a b e l; 35  P r C k ( c j , r ) = s t e p × L e n [ i ] / p r ( c j ); 36  if  Li.head.length==step×Len[i]  then 37  L i . p o p ( ); 38  else 39  L i . h e a d . l e n g t h - = s t e p × L e n [ i ]; 40  return  PrCk;The computation cost ofMLA consists of three parts, sorting C and initiating variables, Segment Alignment, and Mechanism Initiation. The first part costs O(Clog⁡|C|). Segment Alignment costs O(k+|C|) since at most k+|C| segments are aligned, and each alignment costs a constant time. Mechanism Initiation costs O(k(k+|C|)) which is dominated by packing at most k+|C| reports (each packing costs O(k)) and calculating at most k(k+|C|) entries for PrCk. In practice, k should be set smaller than |C|. The total cost ofMLA is O(Clog⁡|C|+k|C|).


## 5. Properties ofMLA Algorithm

This section formally proves thatMLA achieves the optimal expected entropy and the optimal dp-coefficient simultaneously. We first introduce some concepts which build necessary foundation for our formal proof.Definition 8 (dominant content).
Given the global setC of query contents, an integer k>0, and the prior probability pr(.), ∀c∈C, let dom⁡(c) be the number of query contents larger than c. A query content c∈C is a dominant content iff the following conditions hold:(i)
dom⁡(c)<k;(ii)
∑prc′≤prcpr(c′)≤pr(c)(k-dom⁡(c)).Definition 9 (dominated content).
Given the global setC of query contents, an integer k>0, and the prior probability pr(.), c∈C is a dominated content, not a dominant content.According to the process of segment alignment inMLA, each dominant content takes up an entire layer. If there are remaining layers, the dominated contents take up these layers and none of them take up an entire layer. In the rest of this paper, we use dominant layer and dominated layer to denote a layer taken up by a dominant content or dominated contents, respectively. Recall the instance in Figure 1; c1 is a dominant content and layer 1 is a dominant layer. Query contents c2,…,c7 are dominated contents and layers 2, 3, and 4 are dominated layers.Definition 10 (layering strategy).
Given the global setC of the query contents, an integer k>0, the prior probability pr(.) of query contents, and a reporting probability PrCk, let the query contents in each report be permuted arbitrarily and denote the ith query content of report r by cir. A layering strategy induced by M is a k dimensional vector, whose ith component is calculated as ∑r∈RCkPrCk(cir,r)pr(cir). When query contents are sorted by the value of PrCk(c,r)pr(c) in descend order, the standard layering strategy is induced.According to the above definition of layering strategy, a mechanism has multiple layering strategies. Intuitively, a mechanism assigns the prior probability of each query content to one or multiple reports. A reportr contains k parts from distinct query contents, and they can be viewed as k segments on k layers. When query contents in each report are permuted, we can build k layers by connecting all the segments on the same layer from different reports together. To this end, we call the k dimensional vector a layering strategy. Next we define the entropy of a layering strategy.Definition 11 (entropy of layering strategy).
Given a layering strategyls={v1,…,vk}, the entropy of ls is calculated as H(ls)=-∑1≤i≤kvilog⁡vi.Lemma 12.
Given a mechanismM(RCk,PrCk), let ls be any induced layering strategy of M; then HE(M)≤H(ls).Proof.
Suppose the query contents in each report ofM are arbitrarily sorted, and we get an induced layering strategy ls={v1,…,vk}. Denote the set of reports with posterior probability larger than 0 by R={r1,…,rm}, and ci,j is the jth query content of report ri in the process of inducing ls. For 1≤j≤k, we have the following equation:(4)vj=∑1≤i≤mPrci,jPrri∣ci,j=∑1≤i≤mPrci,jri.∑1≤i≤mPrri=1.
By applying the log-sum inequality [7] (adopted in the last but one line in the below), we have the following condition:(5)HEM=∑1≤i≤mPrriHri=-∑1≤i≤mPrri∑1≤j≤kPrci,j∣rilog⁡Prci,j∣ri=-∑1≤i≤m∑1≤j≤kPrci,jrilog⁡Prci,jriPrri=-∑1≤j≤k∑1≤i≤mPrci,jrilog⁡Prci,jriPrri≤∑1≤j≤k∑1≤i≤mPrci,jrilog⁡∑1≤i≤mPrci,jri∑1≤i≤mPrri=-∑1≤j≤kvjlog⁡vj=HlsSo we prove that HE(M)≤H(ls).Lemma 13.
Given a mechanismM(RCk,PrCk) generated byMLA, ls is the standard layering strategy of M and M′ is an arbitrary mechanism; then M′ has at least one induced layering strategy ls′ satisfying the fact that H(ls)≥H(ls′).Proof.
Given the mechanismM produced byMLA together with its standard layering strategy ls, we prove Lemma 13 by conducting an induced layering strategy ls′ for an arbitrary mechanism M′, so that H(ls)≥H(ls′). To this end, we sort the query contents in each report of M′ as follows.
For each reportr of M′, we iterate all the query contents. For a query content c, if it is a dominating query content determined byMLA and its order in ls is ols(c), we set the order of c in r by ols(c). After arranging all the dominating query contents, we sort the rest of query contents in r by pr(c)×Pr(r∣c) in descend order and then fill the blanks in the ordering of r. In this way we conduct an inducing layering strategy ls′ of M′, and in the following we are to prove that H(ls)≥H(ls′).
Letndom be the number of dominant layers in ls, and we first investigate the first ndom layers of ls′. For each dominant content on the jth layer of ls, it is also aligned only on the jth layer of ls′. At the same time, on the jth layer of ls′ there are possibly dominated contents. So we get that for each dominant layer the length of ls′ is no smaller than that of ls, i.e., ls′.vj≥ls.vj, 1≤j≤ndom. As a consequence, the total length of dominated layers in ls′ is no larger than that of ls if ndom<k; i.e., ∑ndom≤j≤kls′.vj≤∑ndom≤j≤kls.vj.
Here we turn to a necessary observation of modifying a layering strategy at two layers with increased entropy. Supposels′′ is an arbitrary layering strategy, and its values on layer j and layer h are different. With no loss of generality, assume ls′′.vj>ls′′.vh. Then we move a length of l from layer j to layer h; here 0<l<2(ls′′.vj-ls′′.vh). It is easy to see that the entropy of the modified layering strategy is larger than the entropy of ls′′. Next we transform ls′ to ls with a series of modifications of the above type between two layers with different lengths.
The transform includes two phases. In the first phase,ls′ make the dominated layers (here the dominated layers and dominant layers are determined by ls) have the same length. Let lavgdtd be the average length of dominated layers for ls′. We repeat the below modification. Each time we pick the dominated layer with smallest length and largest length, and move the length from longer to the shorter until either one of them reaches lavgdtd. Then the number of layers with length lavgdtd increases by at least one. After at most k-ndom modifications, phase 1 terminates. And each modification make the entropy of ls′ increase. If the dominated layers of ls′ have the same length at the beginning of phase 1, its entropy remains unchanged.
In phase 2, we investigate each of the firstndom layers. For a layer j≤ndom, let the jth dominant content ofMLA be cjdom. Then we remove a length of ls′.vj-pr(cjdom) and distribute it evenly to dominated layers. After that, the length of each dominated layers for ls′ is no larger than that of ls (denoted ldtd). Meanwhile, the remaining length pr(cjdom) of layer j is larger than ldtd. According to the observation above, each modification of phase 2 will increase the entropy of ls′. After at most ndom modifications, ls′ will be transformed to ls, and each modification will not decrease the entropy.
Combining phase 1 and phase 2, we conduct a transformation from an induced layering strategyls′ of an arbitrary mechanism to ls, which is an induced layering strategy of the mechanism produced byMLA. Each step of the conducted transformation will increase the entropy or keep the entropy unchanged, so we prove that H(ls′)≤H(ls).Lemma 14.
Given a mechanismM(RCk,PrCk) generated byMLA, and ls is the standard layering strategy of M, then HE(M)=H(ls).Proof.
The standard layering strategy ofM restores the result of segment alignment in the process ofMLA. Let L1,…Lk be the lengths of the k generated layers. Due to the shrinking process ofMLA, the initiated reports have the same ratios between pairs of corresponding query contents on two given layers. Thus the standard layering strategy ls of M could be calculated as ls={L1/∑1≤j≤kLj,L2/∑1≤j≤kLj,…Lk/∑1≤j≤kLj}. For each produced report ri in the process of inducing ls, we use ci,j to denote the jth query content in ri. Then we have Pr(ci,j)Pr(r∣ci,j)/Pr(ci,j′)Pr(r∣ci,j′)=Lj/Lj′, for 1≤j,j′≤k. So we can get that the entropy of each report ri equals the entropy of ls. As a consequence the expected entropy of M can be calculated as follows:(6)HEM=∑r∈M.RPrrHr=∑r∈M.RPrrHls=Hls.So we prove that HE(M)=H(ls).Lemmas12, 13, and 14 illustrate the relationship between the expected entropy achieved byMLA and the entropy of induced layering strategies of any other mechanisms. Based on these facts, we get the following theorem.Theorem 15.
MLA achieves the optimal expected entropy.Proof.
According to Lemma14, the mechanism M produced byMLA achieves the expected entropy of H(ls), where ls is the standard induced layering strategy of M. Assume M′ is an arbitrary mechanism, and it has at least on induced layering strategy ls′ so that H(ls′)≤H(ls) due to Lemma 13. At the same time, HE(M′)≤H(ls′) according to Lemma 12. Then we have HE(M)≥HE(M′), so we prove thatMLA achieves the optimal expected entropy through M.Theorem 16.
MLA achieves the optimal dp-coefficient.Proof.
Given the mechanismM produced byMLA together with its standard layering strategy ls, we conduct an induced layering strategy ls′ for an arbitrary mechanism M′ in the same way as the proof of Lemma 13. We sort the query contents in each report of M′ as follows. For each report r of M′, we traverse its query contents. For a query content c, if it is a dominated content determined byMLA and its order in ls is ols(c), we set the order of c in r by ols(c). After arranging all the dominating query contents, we sort the rest of query contents in r by pr(c)×Pr(r∣c) in descend order, and then fill the blanks in the ordering of r. The first layer of ls only contains the first dominant content; however the first layer of ls not only contains the first dominant content entirely but also possibly dominated contents. So we have ls.v1≤ls′.v1. On the other hand, we know that the total length of dominated layers in ls is no smaller than that of ls′. At the same time, each dominated layer has the same length in ls while the kth layer in ls′ has the smallest length. Then we have ls.vk≥ls′.vk. In M the dp-coefficient is actually ln⁡ls.v1/ls.vk. Denote the set of reports produced by M′ by M′.RCk={r1,…,rm}, and let ci,j be the jth query content in report ri, 1≤i≤m and 1≤j≤k. Then we have ∑1≤i≤mPr(ci,1)Pr(ri∣ci,1)=ls′.v1 and ∑1≤i≤mPr(ci,k)Pr(ri∣ci,k)=ls′.vk. Thus max1≤i≤m⁡Pr(ci,1∣r)/Pr(ci,k∣r)=Pr(ci,1)Pr(r∣ci,1)/Pr(ci,k)Pr(r∣ci,k)≥ls′.v1/ls′.vk. The dp-coefficient achieved by M′ is ln⁡Pr(ci,1∣r)/Pr(ci,k∣r)≥ln⁡ls′.v1/ls′.vk. Since we have got that ls.v1≤ls′.v1 and ls.vk≥ls′.vk, we conclude that ln⁡ls.v1/ls.vk≤ln⁡ls′.v1/ls′.vk≤ln⁡Pr(ci,1∣r)/Pr(ci,k∣r). That is to say the dp-coefficient of M is no larger than that of an arbitrary mechanism M′. So we prove thatMLA achieves the optimal dp-coefficient through M.


## 6. Evaluation

This section evaluates the performance of our proposedMLA algorithm based on three real-life datasets, and evaluation results report the comparison betweenMLA and three existing approaches including MEE, MER [8], and DLS [3].


### 6.1. Evaluation Setting

Datasets.To obtain the prior probability of query contents, we employ three real-life datasets including TX and CA from [9] and POIs from [10]. TX and CA contains street objects in the state of Texas and California. Each object is labeled with a coordinate and a set of keywords. POIs contains worldwide coordinates and geotags. We use the coordinates as locations, and take the keywords and geotags as query contents. We divide TX, CA, and POIs into 8km×8km regions and calculate a prior distribution of query contents for each region. Given the number of query contents |C|, we pick query contents with top-|C| frequency and they are used to compute the prior probability. In TX and CA, some keywords such as city name and state name are removed since they dominate the frequency but provide no meanings. For each dataset, the average measures of its regions are reported in the evaluation results. The details of TX, CA, and POIs are introduced in Table 2.Table 2
Details of datasets in evaluation.
Name Description Original/Preprocessed Size Number of Words TX street objects in Texas 14182368/557918 64934 CA street objects in California 13820481/559349 70584 POIs POIs worldwide 1157570/1157570 585626Testbed.We implement our proposedMLA and competitors including MEE, MER, and DLS in Java language. The JDK version is jdk1.8.0_151. All of the evaluation is conducted on a PC-machine with i7-7700 CPU, 8GB memory, and 1TB 7200rpm Hard Disk.Query Generation.For each prior distribution obtained for a region, we generate 1000 queries, which follows the prior distribution, to test DLS. The internal loop times is set to 50 as in [3]. ForMLA, MEE, and MER we directly evaluate the privacy measures using the mechanism obtained for each prior distribution.Privacy Measures.We employ three privacy measures to evaluate content privacy achieved byMLA and its competitors. These privacy measures are (1) expected entropy; (2) dp-coefficient; and (3) effective k. Expected entropy and dp-coefficient are introduced in Section 3. Effective k measures the number of query contents whose posterior probability is positive, and it measures the uncertainty of the reports in a mechanism.Parameters.We test the effects of two parameters on the privacy measures we employ. These parameters include the number of query content in a report (denoted k) and the number of query contents in the global set C (denoted N). In the following evaluation k is set to 5, 10, 15, 20, and 25 and its default value is 10. Parameter N is set to 50, 60, 70, 80, 90, and 100 and its default value is 80.


### 6.2. Evaluation Results

Figures3 and 4 depict the expected entropy achieved byMLA and its competitors. We first study the effects of parameter k on the expected entropy in Figure 3. Here the total number of query contents in C is set to 80 and k is increased from 5 to 25. As shown in Figure 3, our proposedMLA achieves the best expected entropy in the real-life datasets of TX, CA, and POIs. This is consistent with the fact thatMLA achieves the optimal expected entropy. The achieved expected entropy ofMLA and its competitors grows with parameter k, since a larger k improves the uncertainty of reports in a mechanism. In the more skewed dataset, i.e., CA,MLA outperforms MEE and MER in larger degree than that of the case in datasets of TX and POIs. The reason is thatMLA splits larger prior probability of query contents into a larger number of reports; thus it is more suitable to deal with skewed prior distribution of query contents. On the other hand, in MEE, MER and DLS (approximately) keep the ratio of posterior probability for two query contents the same as that of their prior probability. Compared to the datasets of TX and POIs, the expected entropy achieved in CA is smaller correspondingly, since more skewed distribution of query content prior probability decreases the optimal expected entropy.Figure 3
Expected entropy versus parameterk.
(a)
CA dataset (b)
TX dataset (c)
POIs datasetFigure 4
Expected entropy versus parameterN.
(a)
CA dataset (b)
TX dataset (c)
POIs datasetFigure4 presents the achieved expected entropy when parameter N grows from 50 to 100 while k is fixed at 10.MLA again outperforms its competitors in terms of expected entropy. When N grows, the expected entropy ofMLA, MEE, and MER slightly increases while DLS gets decreasing expected entropy. The reason is that increased N brings a relief to the skewness of prior distribution of query contents, soMLA, MEE, and MER achieve better expected entropy. However, due to the process of DLS, querying top frequent contents will make fewer query contents in reports eliminated. When an increasing N relieves the effects of top frequent contents, more query contents in reports of DLS get eliminated. Consistent with what is shown in Figure 3, a larger improvement is obtained in CA when we compareMLA with MEE and MER. Meanwhile, better expected entropy is achieved in more uniform datasets of TX and POIs compared to CA.Next we investigate the dp-coefficient ofMLA and its competitors. The privacy measure of dp-coefficient depicts the uncertainty of reports in a mechanism. A smaller dp-coefficient means that it is more difficult for the adversary to eliminate a query content from any report. The effects of parameter k on dp-coefficient is studied in Figure 5. We fix parameter N at 80 and increase k from 5 to 25. In all the datasets,MLA achieves significantly better dp-coefficient compared to MEE, MER, and DLS. When k increases, the dp-coefficient of all the algorithms grows, since more query contents are packed into the same report. In more skewed dataset, CA, a larger dp-coefficient is obtained. The skewness increases the difference of prior probability for query contents in the same report. In datasets TX and POIs, very small dp-coefficient is achieved when k is set to 5 to 10. For other cases of k, the dp-coefficient is almost always smaller than 1, and this means very good uncertainty among query contents in any reports. On the other hand, MEE, MER, and DLS suffer a larger dp-coefficient around 4 and 2 in different datasets, respectively.Figure 5
dp-coefficient versus parameterk.
(a)
CA dataset (b)
TX dataset (c)
POIs datasetThe effects of parameterN on dp-coefficient are investigated in Figure 6. When we fix k at 10 and increase N from 50 to 100, MEE, MER, and DLS produce nearly constant dp-coefficient. The dp-coefficient of MEE, MER, and DLS in CA is larger than 2.5, while a dp-coefficient around 1.5 is obtained for datasets of TX and POIs. In contrast, the dp-coefficient ofMLA decreases when N grows, since larger N brings relief to the skewness of prior distribution. In CA,MLA achieves dp-coefficient smaller than 1.5. For more uniform datasets of TX and POIs,MLA produces very small dp-coefficients. It obtains ideal dp-coefficient with 0 for TX dataset, and the dp-coefficient for POIs is also very close to 0. This brings significant difficulty to the adversary to infer the actual query content from any report ofMLA. Generally speaking,MLA achieves much better dp-coefficient compared to MEE, MER, and DLS, and it is able to produce dp-coefficient close to 0 for more uniform datasets.Figure 6
dp-coefficient versus parameterN.
(a)
CA dataset (b)
TX dataset (c)
POIs datasetFinally we test effective k ofMLA and its competitors in Figure 7. Given the value of k and N, the same effective k is obtained for different datasets, so we report the effects of parameter N and parameter k on effective k in Figures 7(a) and 7(b), respectively (not for each dataset individually). As shown in Figure 7,MLA, MEE, and MER achieve the optimal effective k with the value of k. In contrast, DLS provides smaller effective k than the value of k. This illustrates the effectiveness ofMLA, MEE, and MER with regard to the disability of eliminating any query contents from each report. We argue that an effective k-anonymity mechanism should provide effective k with the value of k.Figure 7
Effective k versus parametersN and k.
(a)
Varying parameterN (b)
Varying parameterkIn summary,MLA achieves the best privacy measures of expected entropy, dp-coefficient, and effective k simultaneously, which is consistent with our theoretical analysis in Section 5.


## 6.1. Evaluation Setting

Datasets.To obtain the prior probability of query contents, we employ three real-life datasets including TX and CA from [9] and POIs from [10]. TX and CA contains street objects in the state of Texas and California. Each object is labeled with a coordinate and a set of keywords. POIs contains worldwide coordinates and geotags. We use the coordinates as locations, and take the keywords and geotags as query contents. We divide TX, CA, and POIs into 8km×8km regions and calculate a prior distribution of query contents for each region. Given the number of query contents |C|, we pick query contents with top-|C| frequency and they are used to compute the prior probability. In TX and CA, some keywords such as city name and state name are removed since they dominate the frequency but provide no meanings. For each dataset, the average measures of its regions are reported in the evaluation results. The details of TX, CA, and POIs are introduced in Table 2.Table 2
Details of datasets in evaluation.
Name Description Original/Preprocessed Size Number of Words TX street objects in Texas 14182368/557918 64934 CA street objects in California 13820481/559349 70584 POIs POIs worldwide 1157570/1157570 585626Testbed.We implement our proposedMLA and competitors including MEE, MER, and DLS in Java language. The JDK version is jdk1.8.0_151. All of the evaluation is conducted on a PC-machine with i7-7700 CPU, 8GB memory, and 1TB 7200rpm Hard Disk.Query Generation.For each prior distribution obtained for a region, we generate 1000 queries, which follows the prior distribution, to test DLS. The internal loop times is set to 50 as in [3]. ForMLA, MEE, and MER we directly evaluate the privacy measures using the mechanism obtained for each prior distribution.Privacy Measures.We employ three privacy measures to evaluate content privacy achieved byMLA and its competitors. These privacy measures are (1) expected entropy; (2) dp-coefficient; and (3) effective k. Expected entropy and dp-coefficient are introduced in Section 3. Effective k measures the number of query contents whose posterior probability is positive, and it measures the uncertainty of the reports in a mechanism.Parameters.We test the effects of two parameters on the privacy measures we employ. These parameters include the number of query content in a report (denoted k) and the number of query contents in the global set C (denoted N). In the following evaluation k is set to 5, 10, 15, 20, and 25 and its default value is 10. Parameter N is set to 50, 60, 70, 80, 90, and 100 and its default value is 80.


## 6.2. Evaluation Results

Figures3 and 4 depict the expected entropy achieved byMLA and its competitors. We first study the effects of parameter k on the expected entropy in Figure 3. Here the total number of query contents in C is set to 80 and k is increased from 5 to 25. As shown in Figure 3, our proposedMLA achieves the best expected entropy in the real-life datasets of TX, CA, and POIs. This is consistent with the fact thatMLA achieves the optimal expected entropy. The achieved expected entropy ofMLA and its competitors grows with parameter k, since a larger k improves the uncertainty of reports in a mechanism. In the more skewed dataset, i.e., CA,MLA outperforms MEE and MER in larger degree than that of the case in datasets of TX and POIs. The reason is thatMLA splits larger prior probability of query contents into a larger number of reports; thus it is more suitable to deal with skewed prior distribution of query contents. On the other hand, in MEE, MER and DLS (approximately) keep the ratio of posterior probability for two query contents the same as that of their prior probability. Compared to the datasets of TX and POIs, the expected entropy achieved in CA is smaller correspondingly, since more skewed distribution of query content prior probability decreases the optimal expected entropy.Figure 3
Expected entropy versus parameterk.
(a)
CA dataset (b)
TX dataset (c)
POIs datasetFigure 4
Expected entropy versus parameterN.
(a)
CA dataset (b)
TX dataset (c)
POIs datasetFigure4 presents the achieved expected entropy when parameter N grows from 50 to 100 while k is fixed at 10.MLA again outperforms its competitors in terms of expected entropy. When N grows, the expected entropy ofMLA, MEE, and MER slightly increases while DLS gets decreasing expected entropy. The reason is that increased N brings a relief to the skewness of prior distribution of query contents, soMLA, MEE, and MER achieve better expected entropy. However, due to the process of DLS, querying top frequent contents will make fewer query contents in reports eliminated. When an increasing N relieves the effects of top frequent contents, more query contents in reports of DLS get eliminated. Consistent with what is shown in Figure 3, a larger improvement is obtained in CA when we compareMLA with MEE and MER. Meanwhile, better expected entropy is achieved in more uniform datasets of TX and POIs compared to CA.Next we investigate the dp-coefficient ofMLA and its competitors. The privacy measure of dp-coefficient depicts the uncertainty of reports in a mechanism. A smaller dp-coefficient means that it is more difficult for the adversary to eliminate a query content from any report. The effects of parameter k on dp-coefficient is studied in Figure 5. We fix parameter N at 80 and increase k from 5 to 25. In all the datasets,MLA achieves significantly better dp-coefficient compared to MEE, MER, and DLS. When k increases, the dp-coefficient of all the algorithms grows, since more query contents are packed into the same report. In more skewed dataset, CA, a larger dp-coefficient is obtained. The skewness increases the difference of prior probability for query contents in the same report. In datasets TX and POIs, very small dp-coefficient is achieved when k is set to 5 to 10. For other cases of k, the dp-coefficient is almost always smaller than 1, and this means very good uncertainty among query contents in any reports. On the other hand, MEE, MER, and DLS suffer a larger dp-coefficient around 4 and 2 in different datasets, respectively.Figure 5
dp-coefficient versus parameterk.
(a)
CA dataset (b)
TX dataset (c)
POIs datasetThe effects of parameterN on dp-coefficient are investigated in Figure 6. When we fix k at 10 and increase N from 50 to 100, MEE, MER, and DLS produce nearly constant dp-coefficient. The dp-coefficient of MEE, MER, and DLS in CA is larger than 2.5, while a dp-coefficient around 1.5 is obtained for datasets of TX and POIs. In contrast, the dp-coefficient ofMLA decreases when N grows, since larger N brings relief to the skewness of prior distribution. In CA,MLA achieves dp-coefficient smaller than 1.5. For more uniform datasets of TX and POIs,MLA produces very small dp-coefficients. It obtains ideal dp-coefficient with 0 for TX dataset, and the dp-coefficient for POIs is also very close to 0. This brings significant difficulty to the adversary to infer the actual query content from any report ofMLA. Generally speaking,MLA achieves much better dp-coefficient compared to MEE, MER, and DLS, and it is able to produce dp-coefficient close to 0 for more uniform datasets.Figure 6
dp-coefficient versus parameterN.
(a)
CA dataset (b)
TX dataset (c)
POIs datasetFinally we test effective k ofMLA and its competitors in Figure 7. Given the value of k and N, the same effective k is obtained for different datasets, so we report the effects of parameter N and parameter k on effective k in Figures 7(a) and 7(b), respectively (not for each dataset individually). As shown in Figure 7,MLA, MEE, and MER achieve the optimal effective k with the value of k. In contrast, DLS provides smaller effective k than the value of k. This illustrates the effectiveness ofMLA, MEE, and MER with regard to the disability of eliminating any query contents from each report. We argue that an effective k-anonymity mechanism should provide effective k with the value of k.Figure 7
Effective k versus parametersN and k.
(a)
Varying parameterN (b)
Varying parameterkIn summary,MLA achieves the best privacy measures of expected entropy, dp-coefficient, and effective k simultaneously, which is consistent with our theoretical analysis in Section 5.


## 7. Related Work

Privacy issues are attracting more and more attention in people’s daily life, and studies for protecting privacy in various fields have been proposed, for instance, [11–13] for social network data, [14] for cloud storage, [15–17] for mobile crowd sensing systems, [18, 19] for wireless sensor networks, [1, 20] for sensory data and devices, [21, 22] for cyberphysical systems, and [23] for IoT applications.Location privacy and content privacy are recognized in location-based services. Solutions to preserving location privacy and content privacy in location-based services mainly focus on cloaking technique such as [5]. Cloaking technique employs a third-party server to execute spatial generalization algorithms so that the querier is hidden among at least k-1 users. However, the third-party server unfortunately possibly becomes the single point of failure for privacy or a performance bottleneck of query processing. To this end, a number of client based solutions [2, 3, 6, 8] are proposed recently. Reference [3] works on the problem of generating proper dummies for locations in reported queries to CPS servers for hiding the user’s actual locations. In [3], 2k locations with similar probability with the user’s location are chosen as dummy candidates, and k-1 of them are randomly selected as final dummies. This approach obtains good entropy for the k locations in the reported query. Although this solution includes random nature, the posterior probability of the k reported location is still different due to the process of dummy selection, and the privacy guaranteed is not clear. Reference [6] employs cache to avoid submitting queries to CPS servers as much as possible and thus prevents the leakage of user’s location. Reference [2] proposes a mechanism for protecting content privacy in a continuous manner. A set of k query contents are generated for a traveling path, and the user submits the same queries along the path to avoid privacy breach. This fits to continuous querying; however there is no privacy guarantee since it simply chooses query contents with probability larger than a given threshold as candidates. In summary, server-based k-anonymity suffers single point of failure and existing client based solutions do not provide provable privacy guarantee based on the k-location/query contents reported to CPS server. Reference [24] studies improving geoindistinguishability with multiple criteria for better location privacy; however this approach could not be adopted for content privacy due to utility concern. Reference [25] studies protecting privacy for smartphone usage, and this is parallel to our work. Recommendation [26] in location-based system is getting more and more attention, and a location privacy preservation method is proposed for review publication in location-based systems in [27]. The notion of k-anonymity is also developed in statistical databases in [28, 29].Differential privacy is first introduced in statistic databases [30]. The intuitive idea of differential privacy is that a single change of the input should not modify the output significantly. By this guarantee the adversary cannot recognize the input among all possible inputs similar to the real one. Due to the simple and clean nature of differential privacy, it has been adopted widely, such as machine learning [31], statistic database [32–37], data mining [38], graph [39], data analytic [40], and crowdsourcing [15]. Recent research starts combining correlation [41] and personality [42] nature to original differential privacy. Our work is parallel to the large body of differential privacy research. We combine differential privacy and k-anonymity to provide guaranteed privacy in interactive cyberphysical systems. Differential privacy has been adopted in the literature of privacy protection in location-based services, and [43] ensures that an adversary will not get significant information about a user’s location after a query is reported. This is achieved by making the ratio of two nearby locations’ posterior probability similar to that of their prior probability. Mechanisms following or adopting similar privacy guarantee are presented to optimize privacy or utility [44]. Besides k-anonymity and differential privacy, a number of works customize semantic privacy metrics such as [45–47] in social networks. This paper also defines privacy measures based on entropy and differential privacy.


## 8. Conclusion

This paper investigates preserving content privacy in interactive cyberphysical systems throughk-anonymity based mechanisms. We present two privacy metrics denoted expected entropy and dp-coefficient, which are based on entropy and differential privacy, respectively, and formulate the problem of achieving the optimal k-anonymity for content privacy in interactive cyberphysical systems based on these privacy metrics. An algorithmMLA consisting of two phases, namely, segment alignment and mechanism initiation, is proposed to establish mechanisms for achieving the optimal k-anonymity. Theoretical analysis illustrates the attractive property thatMLA achieves the optimal expected entropy and the optimal dp-coefficient simultaneously. We conduct evaluation based on three real-life datasets, and three privacy metrics, namely, expected entropy, dp-coefficient, and effective k, which depict uncertainty of reports in mechanisms, are tested. Evaluation result demonstrates thatMLA outperforms its competitors including recent client based solutions over all the employed privacy metrics, and these results are consistent with the fact thatMLA achieves the optimal k-anonymity for content privacy in interactive cyberphysical systems.



---

*Source: 7963163-2018-09-26.xml*