Gergely Acs
email: gergely.acs@inria.fr

Jagdish Prasad Achara
email: jagdish.achara@inria.fr

Claude Castelluccia
email: claude.castelluccia@inria.fr

Probabilistic k m -anonymity Efficient Anonymization of Large Set-Valued Datasets

Set-valued dataset contains different types of items/values per individual, for example, visited locations, purchased goods, watched movies, or search queries. As it is relatively easy to re-identify individuals in such datasets, their release poses significant privacy threats. Hence, organizations aiming to share such datasets must adhere to personal data regulations. In order to get rid of these regulations and also to benefit from sharing, these datasets should be anonymized before their release.

In this paper, we revisit the problem of anonymizing setvalued data. We argue that anonymization techniques targeting traditional k m -anonymity model, which limits the adversarial background knowledge to at most m items per individual, are impractical for large real-world datasets. Hence, we propose a probabilistic relaxation of k m -anonymity and present an anonymization technique to achieve it. This relaxation also improves the utility of the anonymized data. We also demonstrate the effectiveness of our scalable anonymization technique on a real-world location dataset consisting of more than 4 million subscribers of a large European telecom operator. We believe that our technique can be very appealing for practitioners willing to share such large datasets.

I. INTRODUCTION

Today digital data about individuals are being collected on a large scale by different actors. This vast amount of data, termed as big data in the literature, could be of great use for social or economical development if shared. Set-valued data is a renowned form of big data, which contains a set of items/values per individual, for example, visited locations, purchased items, watched movies, or search queries. Although set-valued data typically do not include any direct personal identifiers, their release can still lead to a privacy breach if an adversary learns a subset of items of an individual from other sources. In particular, the adversary might be able to re-identify individuals if the known subset of items is unique or not shared by many people. For instance, de Montjoye et al. have shown that four spatio-temporal positions are enough to uniquely identify an individual 95% of the times in a dataset of one and a half million users [START_REF] De Montjoye | Unique in the crowd: The privacy bounds of human mobility[END_REF]. Similar re-identification attacks have been demonstrated on credit-card metadata [START_REF] De Montjoye | Unique in the shopping mall: On the reidentifiability of credit card metadata[END_REF] and movie ratings [START_REF] Narayanan | Robust de-anonymization of large sparse datasets[END_REF]. These attacks pose significant privacy threats, as the adversary can learn about all items of individuals after identifying their records, which may uncover potential sensitive information such as their health and sex life or political beliefs [START_REF] Narayanan | Robust de-anonymization of large sparse datasets[END_REF].

In the literature, different privacy models are proposed for privacy-preserving data release. One of the first of these models was k-anonymity [START_REF] Samarati | Protecting respondents' identities in microdata release[END_REF], [START_REF] Sweeney | k-anonymity: A model for protecting privacy[END_REF], which was originally proposed for relational databases. However, k-anonymity is not a meaningful privacy model for set-valued data, where attributes cannot be separated into quasi-identifiers (which the adversary might already know from external sources about an individual) and sensitive attributes (which the adversary intends to learn). Rather, every item can equally serve as a quasi-identifier as well as a sensitive attribute. As a straw man approach of k-anonymization, one can consider all items of an individual as quasi-identifiers. However, it is unreasonable to assume that the adversary knows all the items of an individual, especially if there are many of them. Moreover, k-anonymity suffers from the curse of dimensionality [START_REF] Aggarwal | On k-anonymity and the curse of dimensionality[END_REF], i.e., datasets with many attributes require excessive modification in order to satisfy k-anonymity. As set-valued data are typically large-dimensional and sparse, this would render most of such data practically useless.

As a result, k m -anonymity has been proposed in [START_REF] Terrovitis | Privacy-preserving anonymization of set-valued data[END_REF], which has a weaker but more reasonable guarantee than kanonymity; any subset of m items must be shared by 0 or at least k individuals in the dataset. In [START_REF] Terrovitis | Privacy-preserving anonymization of set-valued data[END_REF], Manolis et al. also proposed algorithms to achieve k m -anonymity but these solutions are not applicable for large datasets. That is, the running time of their apriori-based anonymization remains exponential in m in the worst case, and therefore impractical for larger values of m.

In this paper, we propose a probabilistic version of k manonymity which is suitable for big data. This comes at the cost of a bit relaxation of privacy requirements as it provides a probabilistic guarantee on k m -anonymity. Roughly saying, our model guarantees that any m items of an individual are shared by at least k -1 other individuals with a certain probability σ. Here, the value of σ is typically very close or even equal to 1. If σ = 1 our model boils down to the standard k m -anonymity model [START_REF] Terrovitis | Privacy-preserving anonymization of set-valued data[END_REF] providing the same privacy guarantee. We propose an anonymization technique based on random sampling to achieve probabilistic k manonymity with a worst-case complexity that is linear in the number of individuals and quadratic in m. Therefore, our solution becomes practical for any values of m, and it is also sufficiently flexible to provide different guarantees for different values of m. Indeed, it is rational to have stronger privacy guarantee (i.e., larger k and/or larger σ) for smaller values of m, which are always easier to acquire from external sources than larger number of items. This allows to further improve utility meanwhile providing reasonable privacy guarantee even for large values of m.

Moreover, our model perfectly complies with current personal data regulations and therefore can be a compelling choice for the purpose of anonymization in practice. In particular, the central concept of such regulations is reidentifiability of individuals likewise in our model. For example, if re-identifiability rate can be proved to fall below a particular threshold (see the United States HIPAA Privacy Rule Safe Harbor de-identification standard 1 ), then the data is not considered to be personal any more and the regulation does not apply. Similarly, the European Data Protection law (Directive 95/46/EC) [START_REF]EU Directive 95/46/EC -The Data Protection Directive[END_REF] defines personal data as "any information relating to an identified or identifiable natural person". In determining whether a person is identifiable "account should be taken of all the means likely reasonably to be used either by the controller or by any other person to identify the said person" [START_REF]EU Directive 95/46/EC -The Data Protection Directive[END_REF]. Our model provides a straightforward interpretation of these privacy requirements through the fine-tuning of its parameters (i.e., m, k, and σ).

Contributions: More specifically, the contributions of this paper are as follows:

1) We propose a probabilistic relaxation of k manonymity in order to anonymize large set-valued datasets efficiently. The parameters of our model can be fine-tuned to the desired privacy requirements. 2) We design an anonymization technique which uses generalization to achieve our probabilistic privacy guarantees. The running time of our approach is linear in the number of records, the maximum number of generalizations, and quadratic in m. Hence, it remains scalable even for big data regardless what generalization method is used. Our scheme is based on the random sampling of different subsets of items and can optimize the utility with respect to any error function.

To this end, we use a Markov Chain Monte Carlo sampling technique, whose worst-case running time (aka., mixing time) is known. 3) We evaluate our anonymization solution on the location data of more than 4 million individuals in a large European city. This location data is derived from their call data records, and consists of the set of visited cell towers per individual. We show that the localization error due to anonymization with reasonable anonymity guarantees falls below a few hundred meters, and the 1 http://aspe.hhs.gov/admnsimp/final/PvcFR06.txt# resolution ranges from 100 to 400 partitions of the city which has a total area of 128 km 2 . This makes an average localization accuracy between 0.3 and 1 km 2 depending on the applied privacy parameters.

II. RELATED WORK

In this section, we briefly review the related work on the anonymization of set-valued data (i.e., excluding the problem of attribute inference). Many works divide items into sensitive attributes and quasi-identifiers, and assume that the adversary's background knowledge is confined to quasiidentifiers [START_REF] Ghinita | On the anonymization of sparse high-dimensional data[END_REF], [START_REF] Ghinita | Anonymous publication of sensitive transactional data[END_REF], [START_REF] Cao | ρ-uncertainty: Inference-Proof Transaction Anonymization[END_REF], [START_REF] Loukides | Anonymizing transaction data to eliminate sensitive inferences[END_REF], [START_REF] Xu | Publishing sensitive transactions for itemset utility[END_REF], [START_REF] Xu | Anonymizing transaction databases for publication[END_REF]. Similarly to [START_REF] Terrovitis | Privacy-preserving anonymization of set-valued data[END_REF], [START_REF] Terrovitis | Local and global recoding methods for anonymizing set-valued data[END_REF], our approach does not have such a limitation as all items can equally be sensitive and also quasi-identifier in our model.

In [START_REF] Terrovitis | Privacy-preserving anonymization of set-valued data[END_REF], [START_REF] Terrovitis | Local and global recoding methods for anonymizing set-valued data[END_REF], Terrovitis et al. propose the model of k manonymity as well as different anonymization algorithms using global and local recoding. However, these algorithms do not scale well for large datasets as their computational cost is exponential in m in the worst case (see Section V-C for details). k m -anonymity has also been applied on trajectory data in [START_REF] Poulis | Distance-based k m -anonymization of trajectory data[END_REF], but this solution suffers from the same drawbacks as [START_REF] Terrovitis | Local and global recoding methods for anonymizing set-valued data[END_REF]. Another approach of anonymization of set-valued data were proposed in [START_REF] Loukides | Coat: Constraint-based anonymization of transactions[END_REF], where the privacy constraints need to be specified in advance in the form of specific itemsets which must satisfy k-anonymity. However, the proposed solutions have a cost which is exponential in m if the privacy constraints are composed of all subsets of items with size m.

He et al. propose a top-down generalization algorithm in [START_REF] He | Anonymization of set-valued data via top-down, local generalization[END_REF] to provide k-anonymity for set-valued data. However, as [START_REF] Terrovitis | Local and global recoding methods for anonymizing set-valued data[END_REF] also points out, this approach underperforms the anonymization techniques proposed for k m -anonymity in [START_REF] Terrovitis | Local and global recoding methods for anonymizing set-valued data[END_REF], if m is less than the average record size. Also, kanonymity has an unnecessarily strong assumption for setvalued data as the adversary is unlikely to know all the items of an individual.

Set-valued data have also been sanitized under differential privacy. Instead of releasing microdata, these solutions publish the noisy occurrence counts of certain items [START_REF] Korolova | Releasing search queries and clicks privately[END_REF] or itemsets [START_REF] Chen | Publishing set-valued data via differential privacy[END_REF] in the dataset. Due to the injected noise, these techniques do not preserve data truthfulness, and hence cannot be used in several applications [START_REF] Fung | Privacypreserving data publishing: A survey of recent developments[END_REF], [START_REF] Loukides | Coat: Constraint-based anonymization of transactions[END_REF]. Moreover, the solution proposed in [START_REF] Chen | Publishing set-valued data via differential privacy[END_REF] releases the noisy occurrence counts of complete records which provides weak utility if the records are unique in the dataset (which is the case for most real-world large datasets like in Section VI-A).

Finally, similarly to [START_REF] Poulis | Distance-based k m -anonymization of trajectory data[END_REF], our scheme does not require a pre-computed generalization hierarchy for anonymization but rather a set of more general constraints describing the desired output. This provides a wide applicability to our approach which is also demonstrated in Section VI. I.

The goal of the adversary is to re-identify a targeted user u in D such that at most m items of u (i.e, a single m-itemset from u's record) are known to the adversary. We assume that the adversary has no other available background knowledge about u.

An itemset is k-anonym in D, if the number of records containing that itemset is either 0 or at least k. k manonymity [START_REF] Terrovitis | Privacy-preserving anonymization of set-valued data[END_REF] guarantees that all m-itemsets are kanonym. In other words, if the adversary knows any mitemset which occurs in at least one record of D, then there are at least k -1 other records which also contain that itemset. For example, the dataset in Table I is not 2 2anonym, as {LA, Boston} and {Seattle, Boston} only occur in the last record.

In the following definition, we relax k m -anonymity and require that any itemset, up to size m, which is known by the adversary must be k-anonym with large probability. Definition 1 (σ-k m -anonymity) Let supp(x, D) denote the support of x ∈ I m in D, i.e., the number of records in D which contain x. Let Ω denote the set of allitemsets which occur in at least one record in D, i.e., Ω = {x : x ∈ I ∧ supp(x, D) ≥ 1}, and let B denote a random variable describing a probability distribution over

Ω . A dataset D is σ-k m -anonym with respect to the ensemble of B 1 , B 2 , . . . , B m , if P r[supp(B , D) ≥ k] ≥ σ for all 1 ≤ ≤ m.
σ-k m -anonymity requires that any -itemset ( ≤ m) chosen from the distribution of B is k-anonym with probability at least σ. In particular, the adversary has a probability distribution of B over all -itemsets, which represents the likelihood that a particular -itemset is learned by the adversary from external sources. Then, the adversary picks one itemset x from this distribution, and the attack is successful if x is not k-anonym (i.e., supp(x, D) < k). In Definition 1, 1σ measures the success probability of this attack.

In order to ease presentation, Definition 1 requires the same privacy guarantee (i.e., identical values of σ and k) for all -itemsets where ≤ m. However, we stress that the privacy guarantee may depend on the size of itemsets in reality. That is, larger values of may need less privacy protection and hence smaller values of σ and k, as the adversary may be less capable to acquire large number of items from external sources. Therefore, in a more general sense, σ and k can be vectors with size m, i.e., (σ 1 , σ 2 , . . . , σ m ) and (k 1 , k 2 , . . . , k m ) requiring an -itemset drawn from B to be k -anonym with probability at least σ .

Finally, we note that the k-anonymity of m-itemsets does not imply that of shorter itemsets in general, and hence the identical and explicit privacy requirement for all -itemsets, where < m, in Definition 1. Indeed, there is no guarantee that records with size shorter than m also occur in longer records.

IV. SAMPLING FOR ANONYMITY

The basic idea of our anonymization approach is to sample a set S of -itemsets from the distribution of B for all 1 ≤ ≤ m, and perform anonymization only if any itemset in S for any ≤ m violates k-anonymity. It follows from standard sampling complexity bounds that if all itemsets in S are k-anonym and |S| is O(ln(1/δ)/ε 2 ) then allitemsets are k-anonym in the entire dataset as well with an error of ε and confidence 1δ. Importantly, the number of required samples is independent of the size of Ω m , which is exponential in m in the worst case.

A. Sufficient requirement of σ-k m -anonymity

Theorem 1 D is k m -anonym with probability at least σ with respect to B 1 , B 2 , . . . , B m , if, for each 1 ≤ ≤ m, there exists S ⊆ Ω such that 1) each element of S is independently drawn from the distribution of B , 2) each element of S is k-anonym in D, 3) |S| ≥ ln(1/x) 2 1 -σ 1-x -2
, where x satisfies x 2 + 2xσ ln(x) + (σ -2)xσ + 1 = 0 and σ ≥ 0.5

Proof: Let Ĥk denote the relative frequency ofitemsets in S which do not satisfy k-anonymity in D. Furthermore, let

H k = P r[supp(B , D) < k]. As each element of S is drawn independently from the distribution of B (Condition 1), Ĥk is an unbiased estimator of H k , i.e., E[ Ĥk ] = H k . It follows from the Chernoff-Hoeffding inequality [14] that P r Ĥk -H k ≥ ε ≤ e -2|S|ε 2
, or equivalently, P r Ĥk -

H k < ε ≥ 1 -e -2|S|ε 2
. Since Ĥk = 0 in our case (Condition 2), we obtain that

P r [H k < ε] ≥ 1 -e -2|S|ε 2 where δ = e -2|S|ε 2
. Therefore, D is k m -anonym with probability at least σ, if

|S| ≥ ln (1/δ) 2ε 2
and

(1 -ε)(1 -δ) ≥ σ (1)
Our goal is to minimize the number of samples |S| meanwhile satisfying the constraint in Inequality [START_REF]EU Directive 95/46/EC -The Data Protection Directive[END_REF]. Therefore, we can formulate the following simple optimization problem minimize

ε,δ f (ε, δ) = ln (1/δ) 2ε 2 subject to (1 -ε)(1 -δ) ≥ σ, 0 < ε, δ ≤ 1
This is a convex non-linear optimization problem, and therefore the Karush-Kuhn-Tucker (KKT) conditions are necessary for a solution to be optimal. Indeed, if 0 < δ ≤ 0.5, the leading principal minors of the Hessian matrix H of f is strictly positive on ε ∈ (0, 1] which means that H is positive definite. Hence, f is convex when ε ∈ (0, 1] and δ ∈ (0, 0.5]. Solving the KKT-conditions yields Condition 3 of the theorem.

In the rest of the paper, we assume that B is the uniform distribution over all -itemsets in D (i.e., the adversary can learn any -itemset in the dataset with equal probability). Although the adversary can always learn certain -itemsets of some users with larger probability, the uniform distribution over all possible -itemsets of any user is the most general assumption in practice.

B. Uniform sampling of -itemsets

As B has uniform distribution over Ω , our task is to sample an element from Ω uniformly at random for any 1 ≤ ≤ m. A first (naive) approach could be to use rejection sampling, i.e., sample a candidate -itemset from I uniformly at random, and then accept this candidate as a valid sample only if it also occurs in D. Otherwise, repeat the process until a candidate is accepted. Although sampling a candidate from I is straightforward, it is very likely to be non-existent in D (especially if is large), and hence its running complexity is O(|I| ) in the worst case. An alternative approach could be to enumerate Ω , and choosing one element directly from Ω uniformly at random. However, the complexity of this approach is still O(|D|(max u |D u |) / !) (recall that D u denotes the record of user u in D). Unfortunately, these naive methods provide acceptable performance only if is small.

We instead use a sampling technique from [START_REF] Achara | On the unicity of smartphone applications[END_REF] based on the Metropolis-Hastings algorithm [START_REF] Metropolis | Equation of state calculations by fast computing machines[END_REF], [START_REF] Chib | Understanding the metropolishastings algorithm[END_REF], which is a Markov Chain Monte Carlo (MCMC) method. This technique has a worst-case complexity which is roughly linear in the number of records and , and hence it remains reasonably fast even for larger values of .

In particular, an ergodic Markov chain, which is denoted by M and detailed in Algorithm 1, is constructed such that its stationary distribution π is the uniform distribution over Ω that we want to sample from. Each -itemset in Ω corresponds to a state of M, and we simulate M until it gets close to π, at which point the current state of M can be considered as a sample from π.

Specifically, at each state transition, M picks a candidate next state C (i.e., an -itemset) independently of the current state S (in Line 6-7 of Algorithm 1). In Line 8, the candidate is either accepted (and M moves to C) or rejected with certain probability (in which case the candidate state is discarded, and M stays at S). The main idea is that, at each state, we use a fast but biased sampling mechanism to propose a candidate C (in Line 6-7); we first sample a record uniformly at random in D, and then an -itemset from this record also uniformly at random. This sampling is more likely to select any -itemset which occurs in multiple records (assuming records have similar sizes). We correct this bias by adjusting the acceptance/rejection probability (in Line 8) accordingly; M is more likely to accept such states which are less likely to be proposed in Line 6-7. Let S := C with probability min (1, q(S)/q(C)), where q(x) = ∀u:Du⊇x i=1 Convergence of M: To compute t in Algorithm 1, we need to know how many transitions M should do in order to "forget" its initial state and get "close enough" to its stationary distribution, i.e., the uniform distribution over Ω . The time that M takes to converge to its stationary distribution π is known as the mixing time of M, and is measured in terms of the total variation distance between the distribution at time t and π.

Definition 2 (Mixing time) For ξ > 0, the mixing time

τ M (ξ) of Markov chain M is τ M (ξ) = min{t : ||P t M -π|| tv ≤ ξ, ∀t ≥ t } where ||P t M -π|| tv = max x∈Ω 1 2 y∈Ω |P t M (x, y) -π(y)|
defines the total variation distance. P t M (x, y) denotes the tstep probability of going from state x to y, and P t M denotes the t-step probability distribution over all states.

The next theorem shows that τ M (ξ) is O(|D| log(1/ξ)/R * ),
where |D| is the dataset size and R * is the uniqueness of -itemsets from the largest record of D, i.e., the probability that an -itemset selected from the largest record uniformly at random occurs only once in D. As the uniqueness of -itemsets is usually large in practice, especially if is large, M is fast-mixing in general 2 . Indeed, in our dataset detailed in Section VI-A, R * = 0.07 when = 5, and it increases to 0.75 ( = 11).

Theorem 3 (Mixing time of M [START_REF] Achara | On the unicity of smartphone applications[END_REF]) Let R * denote the probability that a set of items selected from the largest record (i.e., having the most items) in D uniformly at random is unique. Then, τ M (ξ) ≤ |D| ln(1/ξ)/R * for any .

Notice that q in Algorithm 1 can be computed rapidly in practice by precomputing a table T , where each row corresponds to an item in D, and row i contains the sorted list of all records which have item i. Hence, the set of records which have a common specific -itemset can be computed by taking the intersection of the corresponding rows in T in time O( |i max |), where |i max | is the maximum row size in T . Fast implementations of the intersection of sorted integers described in [START_REF] Lemire | SIMD compression and the intersection of sorted integers[END_REF]. Supposing that ln(1/ξ) i max |D| and 1/R * is a constant close to 1, the total running complexity of M is roughly O( |D|). Therefore, a "good" uniform sample from Ω can be obtained roughly after O( |D|) iterations in most practical cases.

V. ANONYMIZATION ALGORITHM

We perform anonymization through the generalization of items in D. Our goal is to find a generalization function R : I → 2 I \ {}, which maps an item I ∈ I to a non-empty subset of I. An anonymized dataset R, D is obtained by applying R on the original dataset D, i.e., each item i occurring in D is replaced with R(i) (i.e., global recoding is applied on D). The idea is that if multiple items are mapped to the same subset of I, then the records containing these items become indistinguishable w.r.t these items after generalization. A possible (deterministic) anonymization of the example dataset from Table I is illustrated in Figure 1.

In this paper, we assume that the image of R must correspond to a partitioning of I. That is, for any i, j ∈ I, either R(i) = R(j) or R(i) ∩ R(j) = ∅, and ∀i R(i) = I. In order to find a partitioning of I, which results in σ-k manonymity meanwhile maximizes utility, the algorithm needs to be provided with the set of allowed generalization functions, i.e., a subset C of possible partitionings. In general, C can be succinctly described in the form of constraints. For example, in Figure 1, the constraint is specified in the form of a generalization hierarchy, i.e., Image(R) must be a partitioning of I which corresponds to a horizontal cut of the specified hierarchy.

We define the hamming distance on the set of generalizations as dist h (R 1 , R 2 ) = |{i ∈ I : R 1 (i) = R 2 (i)}|, i.e., the number of items on which R 1 and R 2 differ. Two generalization functions 1 is the neighbor of function R at item "New York" and also at item "Boston", where R maps each city to itself (i.e., R (i) = {i} for all i ∈ I) 3 . Furthermore, err : 2 I ×2 2 I → R denotes an error function measuring some distance between the original dataset D and its anonymized version R, D . err represents the utility loss due to applying R on D. For example, in Figure 1, a possible error function is the average distance between cities and the centroid of their aggregate regions (i.e., the centroid of West US for Boston and New York).

R 1 , R 2 ∈ C are neighbors at item i ∈ I, if R 1 (i) = R 2 (i) and dist h (R 1 , R 2 ) = min R ∈C dist h (R 1 , R ) = min R ∈C dist h (R , R 2 ). For ex- ample, function R in Figure
All (US) = West US ∪ East US West US = {New York, Boston} East US = {LA, Seattle} New York Seattle LA Boston R(New York) = West US R(Boston) = West US R(LA) = LA R(Seattle) = Seattle Rec# Items 1 {LA} 2 {LA,
Given an input dataset D and constraint C, our goal is to find R ∈ C (i.e., a partitioning of I) such that err (D, R, D ) is minimized and R, D satisfies σ-k manonymity.

A. Operation

Our proposal, denoted by A, is detailed in Algorithm 2. We perform a randomized greedy search on the set of generalizations in C; it starts from the identity mapping of all items (i.e., when there is no generalization) and it always proceeds to a random neighboring generalization by merging partitions following the given constraint. The search stops as soon as we find a generalization R such that R, D satisfies σ-k m -anonymity, or no more generalization can be done because Image(R) is a singleton.

In particular, A first generalizes D by considering shorter itemsets and then proceeds with larger itemsets till the size of m. A maintains a generalization function R which is initialized to the identity mapping of all items in I (in Line 4), and updates R if a sampled -itemset violates kanonymity (Line 12-14). Specifically, A picks an -itemset s from the original dataset D uniformly at random using M (in Line 8). If the generalized -itemset s (Line 10) occurs at least k times in the anonymized dataset R, D , then it is added to the set S of found k-anonym samples (Line 11) and R is left unchanged. Otherwise, all generalizations R ∈ C are identified such that (1) R is the neighbor of the current generalization R at an item j ∈ s, i.e., there exists j ∈ s where they differ, and ( 2)

|Image(R )| < |Image(R)|, i.e.,
R is obtained from R by merging the partition of an item j ∈ s with another partition in Image(R) specified by the constraint. Then, we update R to the generalization which minimizes the error and satisfies both requirements. Notice that Requirement [START_REF] Achara | On the unicity of smartphone applications[END_REF] guarantees that the algorithm will terminate after finite number of steps due to the monotonicity property of k-anonymity [START_REF] Terrovitis | Privacy-preserving anonymization of set-valued data[END_REF].

If at least γ samples 4 of -itemsets satisfy k-anonymity, or no more generalizations can be applied because only a single set of items occurs in each record (i.e., Image(R) is a singleton), A stops (Line 7) and proceeds to itemsets with size + 1 as long as ≤ m -1 (Line 5). Since γ is adjusted according to Theorem 1, and S contains itemsets selected by M uniformly at random, it follows from Theorem 1 and 2 that the output of A satisfies σ-k m -anonymity.

Notice that in Line 8 of Algorithm 2, the uniform samples are always taken from the original dataset D and not from its anonymized version R, D . Recall that, in Definition 1, the adversary's background knowledge is assumed to be at most m items from I (and not from Image(R)).

Example 1 Consider the anonymization of the dataset from Table I with σ = 0.99, k = 2, m = 2, err is the geographic distance, and each valid generalization in C corresponds to a horizontal cut of the hierarchy in Figure 1. First, A checks all 1-itemsets. As all cities are present in at least 2 records, A proceeds to 2-itemsets. Suppose that A samples s = {LA, Boston}, which fails 2-anonymity. Hence, A considers all possible neighboring generalizations of R, where R is the identity mapping of cities, and finds two valid neighbors; R 1 at item Boston (i.e., Boston is merged with New York), and R 2 at item LA (i.e., LA is merged with Seattle). In particular, R 1 (New

York) = R 1 (Boston) = West, R 1 (LA) = LA, R 1 (Seattle) = Seattle, and R 2 (Seattle) = R 2 (LA) = East, R 2 (New York) = New York, R 2 (Boston) = Boston. Since
Boston is closer to New York than LA to Seattle, A chooses R 1 which results in the least error. The resulting dataset R 1 , D , which is also shown in Figure 1, is 2 2 -anonym 4 γ can be efficiently computed with any numerical root-finding method (e.g., Newton's method) and hence returned by A.

B. Amplifying utility

It can be shown that finding the optimal generalization function R, which results in the least error and also provides k m -anonymity, is NP-hard [START_REF] Terrovitis | Privacy-preserving anonymization of set-valued data[END_REF]. Although A tends to output datasets with low error, it is not guaranteed to find a dataset which is "close" to the optimal solution. However, as A is randomized, we can approach such a solution if A is executed multiple times.

Algorithm 2 Anonymization A 1: Input: D, C, m, k, σ, t 2: Output: Anonymized dataset R, D 3: γ := ln(1/x) 2 1 -σ 1-x -2
, where x satisfies x 2 + 2xσ ln(x) + (σ -2)x -σ + 1 = 0 4: R(i) := {i} for all i ∈ I 5: for = 1 to m do In particular, we amplify the utility of A by multiple independent trials. Consider A (r) which executes A independently r times, and selects the output among the r executions which has the best utility (i.e., the least error). Notice that multiple executions do not deteriorate anonymity, but rather improve utility. Indeed, A (r) can find a dataset which is closer to the optimal solution if r is sufficiently large. Moreover, this approach is independent of the error function err .

Theorem 4 A (r) achieves σ-k m -anonymity in O rm 2 |D||I|(1 -σ) -2 ln 1 1-σ steps.
Proof: A picks γ samples maximum |I| -1 times in the worst case for any C. In addition,

γ = O (1 -σ) -2 ln 1 1-σ . Indeed, γ = O ln(1/δ)/ε 2 , where (1 -ε)(1 -δ) ≥ σ. This means that ε = (1 -σ)/2 implies δ = (1 -σ)/(1 + σ) which results in γ < ln 4 1-σ (1 -σ) -2 . As the complexity of M is O( |D|), we obtain that the complexity of A (r) is O rm 2 |D||I|(1 -σ) -2 ln 1 1-σ .

C. Comparison to the deterministic Apriori-based anonymization

In [START_REF] Terrovitis | Privacy-preserving anonymization of set-valued data[END_REF], the authors proposed a deterministic anonymization technique to achieve traditional k m -anonymity (i.e, σ = 1) based on the apriori-principle. However, the running time of their apriori-based anonymization (AA) remains exponential in m in the worst case. In particular, AA first generalizes all 1-itemsets in D and obtains a new generalized dataset D 1 . Then all 2-itemsets of D 1 are generalized in order to get D 2 , and so on until D m is obtained and released. At step ( ≤ m), AA requires to enumerate and store all -itemsets of each record in D , which has a cost of O |D| • t , where t is the size of the longest record in D . Although t 1 ≥ t 2 ≥ . . . ≥ t m , there is no guarantee that tm m is sufficiently small in practice (which is the case for our dataset in Section VI) as its magnitude depends on the applied generalization hierarchy and dataset D.

VI. EVALUATION A. Dataset characteristics

We use a CDR (Call Data Record) dataset provided by a cell phone operator in Europe, where I represents the set of cell towers of the operator in a large European city. A cell tower T ∈ I is visited by an individual, if the operator has a recorded event at tower T related to the individual over the observed period (01/09/2007 -17/10/2007). An event can be an incoming/outgoing call or message to/from the individual. The dataset contains the events of 4, 427, 486 users at |I| = 1303 towers within the administrative region of the city, where the GPS coordinates of all the towers are also available. In our dataset D, a record contains only the set of towers that are visited by a user over six weeks, i.e., it does not contain the time of visits. Indeed, including time of visits would enable the adversary to easily compute the frequency of each tower per user which allows to deduce the top locations (e.g., home and working place) of each individual in D. Top locations of individuals are highly unique [START_REF] Zang | Anonymization of location data does not work: A large-scale measurement study[END_REF] even in large populations, which makes the anonymization of time-stamped location data very challenging. 5 The average number of individuals per tower over this period was 38817 with a standard deviation of 50911. The total area of the city which is covered by cell towers is 128.1 km 2 . The main characteristics of our dataset are summarized in Table II. The towers are shown in Figure 2.

B. Uniqueness

In what follows, we illustrate the potential privacy risks of releasing our dataset without any anonymization. The uniqueness of a set of items (i.e., towers) of different sizes is shown in Figure 2. Recall that the uniqueness is defined as 5 Notice that, in our simplified dataset, even if the adversary knows the top locations of a single user, there can be multiple other users who visited each of these locations at least once. Without time information, the adversary does not know whether these are also top locations of other users or not. . As the denominator is infeasible to compute in our case, we use sampling to approximate the uniqueness. In particular, according to the Chernoff-Hoeffding bound, we pick 2 ln(2/δ)/ε 2 subsets of towers with the given size uniformly at random using M, which is described in Section IV-B, and approximate the real uniqueness with the uniqueness of the sample set. We note that, unlike in [START_REF] De Montjoye | Unique in the crowd: The privacy bounds of human mobility[END_REF], this technique provides an unbiased estimation of the real unicity. In particular, in [START_REF] De Montjoye | Unique in the crowd: The privacy bounds of human mobility[END_REF], the authors used a biased sampling technique to estimate unicity; they first selected a record uniformly at random, and then a subset of towers with the given size also uniformly at random. However, their approach is more likely to select subsets which occur in multiple records, and hence underestimates the real unicity in the dataset.

For the sampling algorithm M, we emphasize that the bound in Theorem 3 is a worst-case bound, and the real convergence time can be much smaller depending on the dataset D as well as the starting state of the chain. In order to speed up computations even more, we detected the convergence of M using the Geweke diagnostic [START_REF] Geweke | Evaluating the accuracy of sampling-based approaches to the calculation of posterior moments[END_REF] in the rest of the simulations (see the appendix).

For our measurements, we used ε = 0.01 and σ = 0.99 which requires at least 26492 samples from D (with replacement). This guarantees that the sample uniqueness is within ±1% error of the real uniqueness with probability at least 0.99. As Figure 2 shows, the uniqueness of 5 towers already reaches 0.2 and it increases to 0.78 when the number of towers is 11. These large values of uniqueness even for small number of towers indicates the serious privacy threats of releasing CDR data even if time information is withheld.

C. Anonymization of CDR data

We use A in Algorithm 2 to anonymize our CDR dataset D with the following constraint. A partition of cell towers, which is always represented by a contiguous region of the city, can only be merged with a neighboring partition in the generalization process. In other words, C contains all possible partitionings of the towers such that the voronoi polygons of all towers within a partition must constitute a single contiguous polygon. Notice that this requirement cannot be specified in the form of a single generalization hierarchy of cell towers and hence would not be achievable with most previous anonymization techniques.

Initially, R is the identity mapping, i.e., every partition is a singleton containing a cell tower from D. Then, at each iteration, when a partition needs to be further generalized (Line 13-14 of Algorithm 2), it is merged with a neighboring partition6 such that the following error function is minimized.

Let D denote the anonymized dataset R, D . The error function is defined as the average geographical approximation error due to generalization in the anonymized dataset D . That is,

err (D, D ) = u∈Du i∈D u dist(i, R(i))
u∈Du |D u | where dist denotes the geographical distance between a tower and the center of its partition R(i) in D 7 . In other words, the average error is the weighted average of the approximation error of all towers, where the weight of a tower i is the number of occurrences of i in D.

As in Algorithm 2, the anonymization stops when there is a single all-inclusive partition, or all -itemsets sampled from D satisfy k-anonymity in R, D for 1 ≤ ≤ m. In order to amplify utility, we execute the above algorithm 10 times independently, i.e., r = 10, and select the output which has the least error.

D. Privacy guarantee

We anonymized our dataset with the following privacy guarantees. For 1 ≤ ≤ 4, we guaranteed k m -anonymity with probability 1, i.e., we used a deterministic apriori-based anonymization (see Section V-C). That is, we replaced the random sampling step of Algorithm 2 with the deterministic enumeration of all -itemsets. However, for ≥ 5, this technique turns out to be very expensive, and we rather employed our probabilistic solution described in Section VI-C. Indeed, the size of the longest record after generalizing all 4-itemsets is till more than 300.

In fact, the above approach provides reasonable anonymity guarantee in practice; the adversary is more likely to collect a few, but usually no more than 5 locations of multiple individuals. For example, the adversary can crawl an online social network (OSN) where many individuals publish a few of their visited locations (such as home or working place), and try to re-identify the OSN users in our dataset. However, if m ≥ 5, the adversary is less likely to collect at least 5 locations of 100 (or say 1000 if σ = 0.999) OSN users, and hence a probabilistic guarantee can make more sense in practice. That is, as our dataset covers a large proportion of all the citizens, a probabilistic guarantee with σ = 0.99 results in the privacy breach of 1 out of 100 users on average (assuming that all of them publish at least five of their locations in OSN and are also present in our dataset).

E. Results

As the average record size is 11, we anonymized itemsets up to size 11. In particular, we considered two different values of k; k = 10 and k = 20, and two different values of σ; 0.99 and 0.999. These probabilistic guarantees require 45, 845 and 5, 866, 617 samples of -itemsets, respectively (see Condition 3 of Theorem 1). For a particular value of m, we used the same value of σ if 5 ≤ ≤ m, and σ = 1 if 1 ≤ ≤ 4. In addition, we used the same value of k for all 1 ≤ ≤ m.

The average number of released partitions is depicted in Figure 4. Recall that the maximum number of partitions is the original number of towers which is 1303. The number of partitions decreases from 350 (m = 5) to 150 (m = 11) for σ = 0.99, and from 260 (m = 5) to 120 (m = 11) for σ = 0.999. Interestingly, increasing k from 10 to 20 does not significantly change the results. Although the number of partitions seem to be too limited at first sight, Figure 3 illustrates that they still provide a meaningful partitioning of the city. Indeed, as Figure 5 also shows, the average error ranges from 110 to 350 meters. Specifically, for σ = 0.99, the error changes from 120 meters (m = 5) to 280 meters (m = 11), and, for σ = 0.999, from 160 meters (m = 5) to 350 meters (m = 11). We also computed the average partition size, where the size of each partition is weighted with the number of individuals within the partition. The results are shown in Figure 6. The average partition size in the original dataset is 0.1 km 2 , which increases to 1 km 2 when σ = 0.99, and to 1.3 km 2 when σ = 0.999. Again, the results are only slightly influenced by the value of k.

VII. CONCLUSION

We proposed a probabilistic relaxation of k m -anonymity for the purpose of anonymizing large set-valued datasets. This relaxation is important to achieve scalability and to improve the utility of the anonymized data. We believe that our privacy guarantees are sufficient for most real-world adversaries and also to get rid of personal data regulations if a dataset needs to be shared. We also presented an anonymiza- tion technique to achieve this relaxation. Our technique does not rely on a pre-defined generalization hierarchy of the set of items but rather on more general constraints describing the desired output. Moreover, it can optimize the utility of the anonymized dataset against privacy constraints with respect to any error function providing wide applicability to our solution. We evaluated our technique on a realworld large dataset and found that the anonymized dataset is still reasonably accurate. We also studied the effect of the privacy parameters m, σ and k on the utility. According to our measurements, the adversarial background knowledge, which is measured by m, has the largest impact on the utility in general followed by the confidence σ of the privacy guarantee.

Algorithm 1 1 : 6 :

 116 MCMC sampling (M) Input: Dataset D, , # of iterations t 2: Output: A sample S ∈ Ω 3: Let U := {Du : |Du| ≥ ∧ Du ∈ D} 4: Let S be an arbitrary -itemset in Ω 5: for k = 1 to t do Select a record r ∈ U uniformly at random 7: Select a subset of items C ⊆ r uniformly at random such that |C| = 8:

1 |Du|-+i 9 :

 9 return S Theorem 2 ([START_REF] Achara | On the unicity of smartphone applications[END_REF]) M in Algorithm 1 is an ergodic Markov chain whose unique stationary distribution is the uniform distribution over Ω for any .

6 :SV

 6 := {} // set of found k-anonym itemsets 7:while |S| ≤ γ ∧ |Image(R)| > 1 do 8: s = M(D, , t) // see Algorithm 1 9: s = {R(i) | ∀i ∈ s} 10: if supp(s , R, D ) ≥ kthen11: := {R ∈ C : R is neighbor of R at an item j ∈ s, and |Image(R )| < |Image(R)|} 14: R := arg min R ∈V err (D, R , D ) 15:S := {} 16: return R, D

Figure 2 :

 2 Figure 2: Voronoi-tessellation of cell towers (left). Red lines denote the boundaries of districts. Uniqueness depending on m (right)

  σ = 0.999

Figure 4 :

 4 Figure 4: Number of partitions (more are better) (r = 10).

  m = 5, σ = 0.99 Avg. err: 143 meters, Partitions: 296 m = 8, σ = 0.99 Avg. err: 264 meters, Partitions: 158 m = 11, σ = 0.99 Avg. err: 284 meters, Partitions: 143 m = 5, σ = 0.999 Avg. err: 184 meters, Partitions: 234 m = 8, σ = 0.999 Avg. err: 314 meters, Partitions: 121 m = 11, σ = 0.999 Avg. err: 331 meters, Partitions: 118

Figure 3 :

 3 Figure 3: Partitions of cell towers depending on m and σ. k = 20 and r = 10 in all settings.

Figure 5 :

 5 Figure 5: Average error (smaller is better) (r = 10).

Figure 6 :

 6 Figure 6: Average partition size (smaller is better) (r = 10).

  \{} is the ensemble of all items of some set of individuals, where |D| denotes the number of individuals in D. A record D u , which is a non-empty subset of I, refers to all items of an individual u in D. A set of items with cardinality m is shortly called as an m-itemset henceforth. The set of all m-itemsets over I is denoted as I m . A set-valued dataset containing the set of visited cities per individual is illustrated in Table

	Rec# Items
	1	{LA}
	2	{LA, Seattle}
	3	{New York, Boston}
	4	{New York, Boston}
	5	{LA, Seattle, New York}
	6	{LA, Seattle, New York}
	7	{LA, Seattle, New York, Boston}
	Table I: Example for a set-valued dataset, where I =
	{LA, Boston, New York, Seattle}.
		III. MODEL
	Let I denote the universe of all items (e.g., set of visited
	locations, purchased items, etc.). A dataset D ⊆ 2 I

Table II :

 II Characteristics of our dataset D the relative frequency of m-itemsets with respect to a single occurrence in D, i.e., |{x:x∈I m ∧supp(x,D)=1}| |{x:x∈I m ∧supp(x,D)≥1}|

The uniqueness of -itemsets from a single record can easily be approximated with the Chernoff-Hoeffding inequality using uniform samples over all -itemsets from the record. This sampling is straightforward to implement by choosing items from the record without replacement.

Recall that a function R, where R(Boston) = West US but R(New York) = New York, is not a valid generalization function as Image(R) is not a partitioning of I.

Two polygons are immediate neighbors if their boundaries have at least one common point.

The center of a partition is the centroid of the polygon which is obtained by merging all the voronoi polygons of the cell towers belonging to the partition.

ACKNOWLEDGEMENTS

This work was funded by the PIA (projet investissements d'avenir) XData Project (http://xdata.fr).

APPENDIX

Geweke convergence diagnostic: if X t denotes a random variable describing the number of records in D containing the current state of M at time t, and

, where X a is the prefix of X t (first 10%), and X b is the suffix of X t (last 50%). We declare convergence when the z-score falls within [-1, 1]. Indeed, if X a and X b become identically distributed (i.e., X a and X b appears to be uncorrelated), the z values become normally distributed with mean 0 and variance 1 according to the law of large numbers.