{'fraction_non_alphanumeric': 0.03250766690257136, 'fraction_numerical': 0.0074309978768577496, 'mean_word_length': 4.609501124784968, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
TACO: A Tree-based Approach to Customizing Location Obfuscation based on User Policies

A large body of literature exists for studying Location obfuscation in different contexts. However, the obfuscation functions generated by existing systems are not easily customizable by end users. Users might find it difficult to understand the parameters involved (e.g., obfuscation range and granularity of location representation) and set realistic trade-offs between privacy and utility. In this paper, we propose a new framework called, TACO, i.e., Tree-based Approach to Customizing location Obfuscation , which can generate location obfuscation functions that provide strong privacy guarantees while being easily customizable via user-specified policies. First, we develop a semantic representation of a given region using tree structure. These data structures assist users in specifying their privacy requirements using policies. Second, we design a rigorous privacy model based on Geo-Indistinguishability for TACO using this tree structure. Third, we implement enforcement techniques in TACO to translate user policies to appropriate parameters and generate a robust, customized obfuscation function for each user. Finally, we carry out experiments on real world datasets to evaluate the effectiveness of the framework under different settings.


INTRODUCTION
To date, many location obfuscation mechanisms have been successfully proposed in the academic literature [1]. These approaches, often placed in the context of service provisioning, transform actual locations of users to obfuscated locations so as to protect their privacy while ensuring quality of service. Geo-Indistinguishability (Geo-Ind) is one of the most popular privacy criteria used in location obfuscation mechanisms [2]. It extends the well known Differential Privacy (DP) [3] to protect location privacy in a rigorous fashion. To satisfy Geo-Ind, if two locations are geographically close, their reported obfuscated locations will have similar probability distributions. In other words, it is hard for an adversary to distinguish a true location among nearby ones given its obfuscation location.
Despite their potential, previous studies have highlighted several limitations with DP-based approaches such as Geo-Ind location privacy mechanisms. These limitations include but are not limited to the not-so-practical nature of differential privacy. Hsu et. al [4] have shown that users do not know how to configure differential privacy ( ) parameters well and therefore they may be unable to set them correctly based on their privacy and utility needs. Garfinkel et. al [5] highlights that even though setting of is considered a policy decision, the DP literature is sparse in addressing this problem. As a result, even privacy conscious users have limited control over the privacy of their location as they have no easy way to interact with obfuscation mechanisms. The lack of flexibility in setting location privacy parameters makes adoption of DP-based (or Geo-Ind) mechanisms difficult. Additionally, one's desire for privacy is often not static or well summarized by a number. Depending on the context and application scenario, users may have different privacy needs and utility requirements. Prior work [6,7] has shown that policies can be used as a mechanism to bridge the gap between user needs and obfuscation mechanisms, providing users' autonomy to determine the privacy parameters based on their own privacy/utility needs. However, most of the prior work has focused on statistical releases of data and not point queries that are used for sharing of location data.
There are several challenges to be addressed in developing such a framework that allows users to customize location obfuscation mechanisms using policies. The first challenge is that of policy specification. This involves developing an easily understood way of writing policies and translating them into meaningful parameters for the underlying obfuscation mechanisms. The second challenge is that of generating an obfuscation function that is robust against policy enforcement. After enforcing the policies, few of the locations might not be eligible for reporting as obfuscated location given users' specific preferences. Thus, the obfuscation function has to be robust against updating Geo-Ind requirements after policy enforcement. The third challenge is that of enforcing policies and customizing the obfuscation function to meet user's privacy needs. This includes not only determining the set of possible obfuscated locations but also determining the granularity at which obfuscated location is returned.
To address the above challenges, we propose TACO (Tree-based Approach to Customizing location Obfuscation), a framework for customizing location obfuscation with strong privacy guarantees (based on -Geo-Ind) that effectively allows users to balance the trade-off between utility and privacy according to their own needs. TACO employs a semantic representation of a given region using a tree structure, namely location tree, which assists users in specifying their policies as well as generating the obfuscation matrix. Users' policies include preferences with respect to the location to obfuscate based on factors such as maximum driving/walking distance, weather, hotspots etc. TACO also includes enforcement techniques to translate these policies into appropriate parameters in the obfuscation mechanism. Locations that do not satisfy the policies are removed from the resulting obfuscation function, which is eventually used to generate the final obfuscated location for the  user. The experimental results on a real dataset show that the robust obfuscation function generated by TACO can be customized according to user policies with only minimal loss in utility compared to the traditional approaches which are non-customizable.
The main contributions of this work are as follows: ⊲ We propose a Tree-based approach for specification of user policies. Such a tree-based approach improves the utility of location reporting as the number of locations in the obfuscation function is lower than traditional non-hierarchical approaches [8]. This representation of locations is also intuitive and easier to understand by users, and thus makes the specification of the policies (defined in the following) easier. ⊲ We develop a novel method for generating obfuscation functions that is robust against removal of multiple locations/regions due to policy enforcement ⊲ We develop a mechanism for enforcing policies and ensuring that the obfuscated location meets users privacy and utility needs ⊲ We design framework with interactions between server side which performs computationally heavy tasks and user side which performs tasks involving real location data. ⊲ We carry out a large set of experiments on a real dataset (Gowalla -social network based on user check-ins) to show the effectiveness of the framework. The rest of the paper is organized as follows. We introduce the TACO framework and describe the key concepts used in our work in Section 2. In Section 3, we present the tree-based representation used in this work along with the policy model. In Section 4, we describe in detail the generation of the customized and robust obfuscation function for each user. We present in Section 5, architecture of our framework and detail the control flow on the user and server side. In Section 6, we evaluate our approach on a real dataset and compare it against a baseline. In Section 7 we go over the related work and we conclude the work by summarizing our contributions, and possible future extensions in Section 8.

BACKGROUND
In this section, we introduce the TACO framework (Section 2.1) and the preliminaries (Section 2.2) of our geo-obfuscation approach.

Framework
Our problem setting is that of Location Based Services (LBS) where users share their privatized locations with a server in order to receive task assignments (e.g. rides-sharing, measurements, delivery). There are three main actors in our setting: users, third party providers, and a server. Users wish to share their locations in a privacy-preserving manner with applications. They specify policies in order to state their preferences of the privatized location and have a privacy module/middleware running on their mobile device or on a trusted edge computer to assist with location hiding. Third party providers use the privatized locations shared by the user for assigning tasks to the user. Examples of such services are Uber, Doordash, and Citizen Science 1 . Finally, we have the location server which runs on the cloud with whom non-sensitive portions of the user policies are shared and it takes care of computationally heavy operations. Users do not trust neither the third party providers nor the server with their sensitive location information or privacy preferences. Figure 1 introduces the flow of TACO and interactions among these three actors: 1 ○ The server generates a spatial index/location tree for an area of interest such as a town, a city, or a county or an area defined by the user on a map (Section 3.1). 2 ○ 3 ○ The location tree is shared with the users to allow them to specify their privacy preferences by way of location-based policies (Section 3.2). 4 ○ The server obtains portions of the policy relevant for generating a set of potentially obfuscated locations. Obfuscated locations are obtained using Geo-Indistinguishability mechanisms [2], and provide strong location privacy guarantees. Obfuscated location information is captured by a set of probability distributions in an obfuscation matrix (Section 4.1). 5 ○ Users receive the obfuscation matrix and adjust it based on their based on their privacy and utility needs (Section 4.2). 6 ○ 7 ○ This final matrix is used to generate a robust obfuscated location, to be shared with third party applications for the purpose of task assignment.

Preliminaries
In this section, we formalize key concepts and notions for our proposed framework, introduced above. Obfuscation matrix. Generally, when considering the obfuscation range as a finite discrete location set V = { 1 , ..., }, an obfuscation strategy can be represented as a stochastic matrix Z = , × [8]. Here, each , represents the probability of selecting ∈ V as the obfuscated location given the real location ∈ V. For each real location (corresponding to each row of Z), the probability unit measure needs to be satisfied: i.e., the sum probability of its obfuscated locations is equal to 1. In this paper, we consider the location set V at different granularity levels, and any real location can be only obfuscated to the locations at the same granularity level (details are introduced in Section 3.1). Privacy Criteria. From the attacker's perspective, the user's actual and reported locations can be described as two random variables and , respectively. We apply Geo-Indistinguishability (Geo-Ind) [2] as the privacy criterion for location privacy guarantees: where and denote the prior distributions of and , respectively, > 0 is predetermined constant called privacy budget, and , denotes the distance between and .
Equ. (2) indicates that the posterior of the user's location estimated from its obfuscated location is close to the user's prior location distribution, i.e., how close they are depends on the parameter . In other words, an external attacker cannot obtain sufficient additional information from a user's obfuscated location.
The utility of our approach is measured based on the quality loss due to using obfuscated location in task assignment. Given that user's real location is v , the obfuscated location generated is v , the target location for task is v , the utility is given by where d v ,v can be implemented using spherical, euclidean, or hop distances. If there are multiple target locations denoted by v 1 , . . . , v , the overall utility is computed as

MODELS
In this section, we introduce the models, including the location tree model (Section 3.1), i.e., how we organize locations at different granularity levels in a tree structure, and the policy model (Section 3.2), i.e., what attributes are considered in the policies.

Location Tree Model
We build a hierarchical index over a given spatial region for location representation. We consider a target area that is composed of a set of locations Λ = 1 , ..., in the highest granularity. Any location in Λ with lower granularity can be represented by a subset of Λ. We design a tree-like structure, called location tree, where each level of the tree represents a particular granularity of location data, and lower levels of the tree increase granularity.
In general, a tree can be represented by T = (V, ≺), where V denotes the node set and ≺ describes the ordered relationship between nodes, i.e., ∀v Here, we slightly abuse notation by letting denote both location and its corresponding node in the location tree. Given these notations, we formally define a location tree as follows: ⊲ the root node v r ∈ V represents the whole area: v r = Λ; ⊲ the tree is balanced and leaf nodes are 1 , ..., ; ⊲ for each non-leaf node v ∈ V, its children v ∈ N v represent a partition of v , i.e., locations in N v are disjoint and their union is v .
We partition the node set V in the location tree into + 1 levels: V 0 , ..., V , where is the height of the tree and the height of nodes (i.e., the number of hops from the node to the deepest  leaf) in each V is . V 0 represents the set of leaf nodes. We let H = {0, 1, ..., } represent the possible level values. We define obfuscation in a location Tree (V, ≺) as a function that maps a given real location v ∈ V to another location v ∈ V that is at the same level with v . We generate a location tree using Uber's H3 2 hexagonal hierarchical spatial index which takes as input the longitude, latitude, and resolution (between 0 and 15, with 0 being coarsest and 15 being finest), and outputs a hexagonal grid index for the region (as illustrated in Figure 2). H3 divides the target region into contiguous hexagonal cells of the same size using the given resolution level. For each of the cells generated by H3, it keeps the distance between the center point of a hexagon and its neighboring cells consistent, making it a better candidate for represeting spatial relationships than grid based systems such as Geohash 3 . Figure 2 illustrates the location tree generated for Times Square, New York. Blue nodes at highest granularity represent the leaf nodes. Red and green nodes at lower granularity represent the intermediate nodes. The root node encompasses the entire region. Nodes in each level do not overlap with each other. Our approach for location representation is inspired by previous works on spatial indexing such as R-Tree [9]. In Beckmann's approach, however, location nodes can overlap and are not disjoint partitions. In our cases, if any two location nodes overlap, it is hard to assess whether two locations are -Geo-Ind (Equation (2)) or not as a user can be in both of these nodes simultaneously.

Policy Model
Users express privacy and utility preferences by way of policies. Any location that does not satisfy users' policies is removed from the obfuscation matrix, therefore constraining the set of possible obfuscated locations. A TACO policy captures users' requirements as follows:

Privacy level or
_ is a user-set parameter that determines the range of locations that a user may be comfortable sharing as obfuscated location. As Figure 3 shows, if a user selects privacy level , we first determine the node in V , say v, which is the ancestor of user's real location at height . The sub-tree with v as the root node includes the locations that the user could report. Accordingly, a higher privacy level implies a wider range of obfuscated locations to select for users. In Figure 3, the red and blue colored subtrees indicate two different user policies both of which specify their privacy level as 2 but with different real locations. Privacy level provides the flexibility for the user to specify the highest granularity of location sharing they are comfortable with. The server can use this attribute to limit the number of locations in the obfuscation matrix for this user, and accordingly, reduce the overhead of generating it. Given a policy P with privacy_l = , a privacy forest is the set of all sub-trees with nodes at level as their root. Thus, the privacy forest contains all the possible locations that can be reported as obfuscated location. Precision level (Precision_l) specifies the exact granularity at which the user reports their locations (e.g., neighborhood or block). For example, if a user requires the precision level to be 2, then his reported location/node is restricted to the set of nodes in level i.e., V 2 . Thus Precison_l gives users the flexibility to reduce the granularity at which location is shared depending on their needs. As the privacy level is the minimum possible granularity for location sharing, precision level is always lower than the privacy level. User Preferences specify users' preferred options for location selection. These may be expressed in a variety of ways, depending on the application at hand and the users' requests (e.g. boolean conditions, black lists of locations, dynamic checks etc). An intuitive approach is to encode preferences as Boolean predicates in the form < var, op, val> where var denotes commonly used preferences for locations such as traffic, weather, driving_distance etc; op is one among {=, ≠, <, >, ≥, ≤} depending upon the variable; and val is assigned from the domain of the var. An example of a policy modelled using these 3 attributes is as follows: <privacy_l = 3, precision_l = 1, user_preferences = [hotspot = "True", distance ≤ 5 miles] This policy states that user would prefer to have the the range of locations from level 3 (privacy_l = 3) which represents their obfuscation range. From these set of possible locations, any of them which are not hotspots i.e., locations where people usually gather, and has a distance higher than 5 miles from their real location should not be considered for the obfuscated location (user_preferences). Finally, when generating their obfuscated location, they would like it to be at the granularity of level 1 (precision_l = 1) which is just above the leaf nodes.

GENERATING FEASIBLE AND ROBUST OBFUSCATION MATRICES
We describe how to generate an obfuscation matrix, that preserve strong privacy guarantees while meeting users' policies, using the location tree. This is non-trivial, as introducing additional constraints based on policies affects the ability to obfuscate locations within certain regions and limit the range of possible obfuscated locations.

Feasibility
Given a user's requested privacy level , the nodes at level (v ∈ V ) and their children nodes (N v ) represent the possible set of obfuscated locations for a user. As the server does not know the user's real location or the subtree that contains user's real location, it has to generate obfuscation matrix for each node v based on the leaf nodes in N v . The server then returns all the generated obfuscation matrices to the user, and the user selects the obfuscation matrix according to their real location. Suppose users want to report a location with lower granularity than the leaf nodes for which the matrix is generated, they can do by applying precision reduction (discussed in Section 4.4) to generate the obfuscation matrix at the desired precision level. Next, we introduce how to generate feasible obfuscation matrices of each subtree rooted at level . Suppose that is a node at level , then we use T to denote the subtree rooted at and let V ,0 denote the set of leaf nodes in T , as shown in Fig. 3. We and probability unit measure are satisfied. We let Q = 1 , ..., denote a set of places of interests which in our problem setting are task assignment locations for e.g., passenger pickup. Given the target location ∈ Q, the actual location of a user, the obfuscated location , the expected estimation error of moving distance caused by obfuscation matrix Z 0 is obtained by Z 0 is generated by following an optimization framework, of which the objective is to minimize Δ Z 0 with the constraints of both -Geo-Ind (Equ. (4)) and probability unit measure (Equ. (5)) satisfied. Once Z 0 is generated, it will be delivered to users. At the user side, users are allowed to customize Z 0 by pruning away unneeded locations (Section 4.2) and reducing the matrix to the desired granularity level (Section 4.4). Note that, after Z 0 is pruned, the new matrix might no longer satisfy the Geo-I constraints in Equ. (4) (the details of matrix pruning will be introduced in Section 4.2). Intuitively, to avoid this potential privacy issue, we need to preserve more privacy budget when formulating the -Geo-Ind constraints, and generate a more "robust" matrix that allows users to prune up to a certain number of locations in the matrix without violating Geo-I. The details of generating such robust matrix will be given in Section 4.3.

Matrix Pruning
After receiving obfuscation matrices from the server, the user can select the matrix Z 0 covering his/her real location, and can remove the locations that do not satisfy their preferences. For example, in Figure 4, the three nodes marked in red at Level 0, {v , v , v }, are to  be pruned 4 . The 3 corresponding rows and columns in the matrix Z 0 are highlighted and in the next step they are removed as well.
The resulting matrix Z 0 * is considered feasible, only if it still satisfies the probability unit measure for each row in the matrix as per Equ. (1). We denote the set of nodes (that do not satisfy the user's preferences) to be removed from the matrix by S (S ⊆ V 0 ). After pruning, the new obfuscation matrix Z 0 * is of dimensions × where = |V 0 − S|. This process called matrix pruning is carried out as follows: ⊲ Remove the rows and the columns of nodes with indices in S from Z 0 to create Z 0 * . ⊲ For each remaining row in Z 0 * , multiply each entry in the matrix z , by This ensures that the entries in each row still satisfy the probability unit measure, i.e.,

Matrix Robustness
After matrix pruning, although the pruned matrix satisfies the probability unit measure, it might not satisfy -Geo-I since in each column , the entries , ( = 1, ..., ) are multiplied by different factors We denote the size of the set of nodes to be pruned from the matrix as i.e., =|S|, and define -prunable robust matrices as follows: Definition 4.1. An obfuscation matrix Z is called -prunable if, after removing up to number of nodes from Z through matrix pruning, the new matrix Z * still satisfies -Geo-Ind, i.e., ∀ , , , In order to make an obfuscation matrix -prunable, we need to preserve more privacy budget , (defined in Equ. (9)) for each pair of locations and , such that even a certain number of locations are pruned from the matrix, the Geo-I constraints of and are still satisfied. We now define reserved privacy budget, denoted by , , as follows.
Proposition 4.3. A sufficient condition for Z to be -prunable is to satisfy Proof. The detailed proof can be found in Appendix. □ Thus, we can state the minimization problem for robust matrix generation, min Δ Z 0 , where the objective function (Equ. (6)) and equality constraints remains the same as earlier (Equ. (5)) but the inequaility constraints are updated to Equ. (10) using reserved privacy budget.
In order to calculate , in Equ. (9), we need to consider all the possible subsets of S ⊆ V ,0 with the cardinality no larger than . The complexity of computing the reserved privacy budget increases exponentially with . Therefore, we define an approximation of , , denoted by ′ , as follows: Proof. The detailed proof can be found in Appendix. □ To calculate ′ , , we need to find top , with ∈ V ,0 , which takes ( log ) in the worst case. According to Proposition 4.4, by replacing , with ′ , in Equ. (10), we can obtain a sufficient condition of Equ. (10). By replacing Equ. (10) with its sufficient condition in the robust matrix generation problem, we can obtain an upper bound of the robust matrix generation solution.
Without loss of generality, in what follows, we target the obfuscation matrix generation in the subtree T . Upon receiving a robust obfuscation matrix (per Def. 4.1), the system at the user end prunes away entries in the matrix Z 0 for T per the user policy preferences. We detail the algorithm for matrix pruning in the extended version of the paper. Note that, if the number of locations in |S| ≤ the pruned matrix Z 0 * will satisfy -Geo-Ind because the original matrix Z 0 is -prunable. However, it is possible that when evaluating policies at the time of location sharing more than locations need to be pruned based on the policies. In such a situation, there are two options for customization: (1) Satisfy all the policies in P which results in a set of locations to be pruned S where |S| > . This leads to a privacy violation which happens when an entry z , in the matrix violates Geo-Indistinguishability constraints (Equ. (4)) w.r.t other entries in its column .
(2) Satisfy some of the policies in P such that |S| ≤ locations. This leads to a policy violation which happens when there exists a location v that does not satisfy a policy in P and its corresponding row and column are not pruned from the matrix.
Essentially, the server has to either violate some of the policies or geo-indistinguishability criterion for some entries in the matrix.

Matrix Precision Reduction
In Figure 5, the original obfuscation matrix is generated for level 0 i.e., the set of leaf nodes. Suppose the user specifies a value as its Precision_l. Matrix precision reduction generates the obfuscation matrix at level , Z ( > 0), given the obfuscation matrix at level 0, Z 0 . As illustrated in the figure, the new matrix is generated by replacing all the rows of the descendant leaf nodes by their corresponding ancestor nodes at level . For each pair of nodes v and v at level , we use N v and N v to represent the set of their descendant leaf nodes, respectively. The probability of selecting v as the obfuscated location given the real location v is calculated using Bayes' theorem.
where p v and p v denote the prior distributions of v and v respectively. Note that, Proof. The proof can be found in Appendix. □ Algorithm 1 presents the approach for matrix precision reduction given the matrix for leaf nodes (Z 0 ), the location tree (T), the prior probability distribution of the leaf nodes 0 , and the precision level ( ) which specifies the granularity/height of the tree of the reported location. First, we get the set of nodes (V ) from level (Step 2). We initialize the new obfuscation matrix with dimensions based on the set of nodes retrieved. For each pair of location nodes (v , v ) in V , we compute their corresponding probability in the new matrix (z , ) by using the probabilities of their leaf nodes, N v and N v respectively, in Equ. (12) (Steps 4-16). The prior probability distribution for the leaf nodes p V 0 in this subtree can be obtained by querying the server 5 . Finally, the new matrix Z for level is returned. Thus using matrix precision reduction, we are able to save the overhead of generating the obfuscation matrix when user chooses to share at a lower granularity than the leaf nodes. 5 We assume that the prior probability distribution is readily available based on publicly available information. We explain how it is computed for a real dataset in Section 6. We disregard communication and computation cost for this as it is a relatively small vector and only has to be periodically updated.

TACO ARCHITECTURE
Having presented matrix generation and customization, we now illustrate the architecture underlying TACO. This process is sketched in Figure 6 and we explain the steps on the user and server side in detail below.

Server side
The server receives Privacy_l and the number of locations to be pruned . Algorithm 2 reports the steps for determining the privacy forest and generating the obfuscation matrix. First, the server determines the nodes at the given privacy level V by performing a Breadth First Search in the Location Tree T(Step 2). Second, it initializes the privacy forest as a dictionary where the key is a subtree and the value is the obfuscation matrix for the leaf nodes of that subtree (Step 3). The system then iterates through each node v at the privacy level and generates an obfuscation matrix for each of them. For this purpose, server has to determine the subtree rooted at v and perform a Depth First Search to determine the leaf nodes of that subtree (Steps 5-6). Next it calls the generateRobustMatrix (algorithm included in the extended version) with the set of leaf nodes and the number of locations to be pruned (Step 7) which solves the minimization problem stated by setting the appropriate constraints for feasibility and robustness (see Section 4.3). The robust obfuscation matrix Z 0 thus generated for the leaf nodes is added to the dictionary with the subtree as the key (Steps 8-9). After iterating through all the nodes at the set privacy level and generating obfuscation matrices for each of their descendant leaf nodes, the final privacy forest PF is returned.

User side
Users input their policies as well as their actual location in order to generate the obfuscated location. First, the system uses the real location to determine the subtree that contains it and is rooted at P.Privacy_l (Step 1). We slightly abuse the notation here as v denotes the real location as well as the node in the tree that contains the actual user's location. Next, the user preferences are evaluated on the leaf nodes of that subtree and determine the set of nodes that are to be pruned. (Step 2 of Fig 6). The count of this set along with P.Privacy_l is passed to the server side (Step 4). From the privacy forest returned by the server, the obfuscation matrix Z 0 corresponding to the subtree that contains user's real location is selected (Step 5). Next, the system prunes this matrix by calling pruneMatrix (algorithm included in the extended version) with the set of nodes to be pruned (Step 6). Depending upon the P.Precision_l, the pruned matrix Z 0 * is updated to reflect the required granularity (Step 7). From this final matrix, the row corresponding to the node at P.Precision_l, that contains the ancestor of the real location of the user is selected. The obfuscated location v is selected from the row based on the probability distribution (Steps 8-9).

EXPERIMENTS 6.1 Experimental setup
Datasets: We use the state-of-the-art Gowalla dataset [10] for our experiments. Gowalla is a location-based social networking website where users share their locations by checking-in. The dataset includes check-in information, which has the following attributes: [user, check-in time, latitude, longitude, location id]. We sampled the user check-ins from the London (UK) region in the Gowalla dataset. We choose this region because it had a uniform and dense distribution of check-ins distributed over a large area. Overall, this sample includes 42,096 check ins out of which 42,036 were used for generating the tree (called training portion) and computing priors and the remaining 60 were used for simulating user location requests (called testing portion). We assigned a set of locations from the region as points of interest and used these as target locations in order to compute utility. We generated the root node which covers the entire region at resolution 5. Next, we generated the children for this root node at resolution 6. We repeated the process two more times and generated a tree of height 3 with 24,647 leaf nodes. For the sake of simplicity, we denote user preferences in the form of a set of locations that met policies' criteria and are to be pruned from the matrix. Priors: We computed prior probability for the leaf nodes in the generated location tree by counting number of user check-ins within that node. If a node had 0 check-ins, we removed that node from the tree. For intermediate nodes (higher up in the tree), the prior was computed by aggregating the priors of its children nodes. Implementation: All of the algorithms were implemented in Mathlab. We used the state-of-the-art Linear Programming tool kit from Mathlab. The data and location tree were stored in main memory.

Experiment 1: Convergence
In this experiment we test the convergence of TACO in generating the robust matrix (described in Section 4). The x-axis denotes the number of rounds and the y-axis denotes the mean of the absolute differences between matrices in consecutive iterations. Lower value on the y-axis denotes better convergence as there is little difference between entries in the matrix after each round. When generating the matrix, we set _ = 20 (number of target locations which are randomly selected from list of leaf nodes), = 50. We ran the experiments with two values of which is the number of locations to be pruned. As illustrated in Figure 7, the divergence

Experiment 2: Impact of Privacy Parameter
In this experiment, we test the impact of privacy parameter on the utility. The x-axis denotes the value that ranges from 50 to 70 in increments of 5. The y-axis denotes the utility measured as the mean estimation error of traveling distance to all the target locations. For setting the real location, we used the location_id from user check-ins in the test portion of the Gowalla dataset. When generating the matrix, we set _ = 49, and used uniform priors for all locations. We compared our results against baseline ("non-robust") approach which has = 0 and therefore is not robust against pruning of any locations from the matrix. As illustrated in Figure 8, with increasing privacy parameter the quality loss decreases and becomes close to the baseline at higher values of . The difference in utility between when = 3 and = 5 also reduces at higher values of . The results show that the robust matrix generated by TACO is able to support customization of obfuscation with only minor loss in quality.

Experiment 3: Impact of Pruning Locations
In this experiment, we test the impact of the number of locations pruned on the final utility. The x-axis denotes the value of (number of locations to be pruned) that goes from 0 to 5. The y-axis denotes the utility which is same from Experiment 2. For each value, we ran the experiments 5 times and plotted the averaged of the 5 runs as the utility. When generating the matrix, we set _ = 49, = 70 (best utility from Experiment 2) and used uniform priors (so that prior probability distribution doesn't interfere with location pruning). As in the earlier experiment, we compare our approach that generates the robust matrix against the non-robust matrix. As illustrated in figure 9, the utility of the robust matrix reduces with higher values of . This is because with higher , the robust matrix needs to have a higher reserved privacy budget. This reduces the used in generation and therefore results in higher noise.

Experiment 4: Measuring Privacy Violations
In this experiment, we measure the privacy violations (which happen when an entry in the matrix violates Geo-Ind constraint w.r.t other entries in its column) as a factor of which is the number of locations to be removed due to policies. When generating the matrix, we set _ = 20, = 70 and used uniform priors. The x-axis denotes the number of locations to be removed that goes from 0 to 5 and the y-axis denotes the number of privacy violations. As expected, the number of privacy violations in the non-robust matrix is much higher than of robust matrix. We also find a small portion of privacy violations in some robust matrices, because in those matrices, 1) the number of removed locations is higher than (the maximum number of locations allowed to be removed) and 2) the robust matrix generation algorithm only converges to a small threshold instead of 0, indicating the output matrices might still have a small number of entries violating the preserved privacy budget.

RELATED WORK
Geo-I based obfuscation. The discussion of location privacy criteria can date back to almost two decades ago, when Gruteser and Grunwald [11] first introduced the notion of location -anonymity on the basis of Sweeney's well-known concept of -anonymity for data privacy [12]. Location -anonymity was originally used to hide a user's identity in LBS [13]. This notion has been extended to obfuscate location by means of -diversity, i.e., a user's location cannot be distinguished with other − 1 locations [14,15]. However, -diversity is hard to achieve in many applications as it assumes dummy locations are equally likely to be the real location from the attacker's view [15,16].
In recent years, the privacy notion Geo-Ind [16] which was first by introduced by Andres et. al, and many obfuscation strategies based on it (e.g., [15][16][17][17][18][19][20][21][22]) have been used for location obfuscation. As these strategies inevitably introduce errors to users' reported locations, leading to quality loss in LBS, a key issue has been discussed in those works is how to trade-off QoS and privacy. Many existing works follow a global optimization framework: given the Geo-I constraints, an optimization model is formulated to minimize quality loss caused by obfuscation [18,19,23,24].
We now cover the related work closer to our work by categorizing them into tree based approaches to obfuscation and policy based approaches to customization. Tree based approaches to obfuscation. In [25], authors present a tree based approach for differentially private online task assignment for crowdsourcing applications. They construct a Hierarchially Well-separated Tree based on a region. This tree is published to both workers and task publishers who use it in order to obfuscate worker and task locations respectively. They show that such this tree-based approach achieves -Geo-Ind while minimizing total distance (maximizing utility) for task assignments. However, their approach is not geared towards helping users in customizing the obfuscation functions.
[26] uses a hierarchial grid to overcome the computational overhead of optimal mechanisms. They first construct a hierarchial grid with increasing granularity as one traverses down the index with highest granularity at leaf nodes (similar to our approach). Second, they allocate the privacy budget ( ) appropriately to these different levels using sequential composition. In order to generate the obfuscated location, they start at the root node containing the real location of the user and goes down the tree by recursively using the output of obfuscation function at the prior level. The main difference between our approach and theirs is, they partition privacy budget for each level in the grid, while ours, no matter from top to bottom or bottom to up (increase or decrease precision), uses the maximum privacy budget. Policy based approach to customization. Blowfish privacy proposed by [7] uses a policy graph to determine the set of neighbors that users want to mark as sensitive. A policy graph encodes user's preferences about which pairs of values in the domain of database should be indistinguishable for an adversary. Thus, it allows users to tradeoff privacy for utility by restricting the indistinguishability set. Blowfish works for statistical queries and not location queries. [27] extended blowfish privacy and applied it to location privacy where the nodes and edges in the policy graph represent possible locations of the user and the indistinguishability requirements respectively. Their goal is to ensure -Geo-Ind for any two connected nodes in the graph and to achieve this they apply DP based noise to latitude and longitude independently. Their approach is best suited for category based privacy i.e., indistinguishability among multiple locations of the same category (e.g., restaurants) as specifying pairwise indistinguishability between locations according to general user preferences is challenging. Our policy model allows users to specify their preferences which then gets translated to the parameters in generating the obfuscation function reducing the overhead on user in terms of specification. Their approach does not allow users to choose the granularity at which their location is shared as the graph model doesn't capture the natural hierarchy of locations.

CONCLUSIONS AND FUTURE WORK
We developed TACO, a framework for customizing location obfuscation functions using a tree-based approach. This framework includes a new location tree model and policy model to assist users in specifying their privacy preferences. We also formalized the problem of generating an obfuscation matrix that is robust against pruning of locations due to policy enforcement. TACO also outlines the various interactions on user as well as server side. Experiments show that our framework is able to satisfy policies without sacrificing privacy and utility.
A first future step is to devise ways to solve the optimization problem at the core of TACO more efficiently. In particular, we will incorporate constraint reduction and decomposition in the linear programming (similar to [28]). Second, it must be noted that generating robust obfuscation matrices with a large number of user policies might inevitably lead to either privacy or policy violations or both. This can be handled by extending our policy model and augmenting it with user's tolerance for privacy and policy violations in order to help server generate the matrix that meets user's requirements more closely. Finally, a possible extension consists of handling trajectory data. In this case, the geo-indistinguishability is not just limited to a subtree but any subtree that contains the user's location traces. Even though this can be handled by increasing the privacy level at which the matrices are generated to include all of the leaf nodes in the user's trajectory, this might have an impact on utility and will need to be addressed in future work.

APPENDIX PROOFS OF PROPOSITIONS Proof of Proposition 4.3
Proof. Given that Equation (10) is satisfied, then for each column , ∀ , ,