Differentially Private Data Publishing and Analysis: A Survey <s> Differential Privacy in Location-Based Services <s> Many mobile phones have a GPS sensor that can report accurate location. Thus, if these location data are not protected adequately, they may cause privacy breeches. Moreover, several reports are available where persons have been stalked through GPS. The contributions of this paper are in two folds. First, we examine privacy issues in snapshot queries, and present our work and results in this area. The proposed method can guarantee that all queries are protected, while previously proposed algorithms only achieve a low success rate in some situations. Next, we discuss continuous queries and illustrate that current snapshot solutions cannot be applied to continuous queries. Then, we present results for our robust models for continuous queries. We will introduce a novel suite of algorithms called MobiPriv that addressed the shortcomings of previous work in location and query privacy in mobile systems. We evaluated the efficiency and effectiveness of the MobiPriv scheme against previously proposed anonymization approaches. For our experiments, we utilized real world traffic volume data, real world road network and mobile users generated realistically by a mobile object generator. <s> BIB001 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Differential Privacy in Location-Based Services <s> Differential privacy has recently emerged as the de facto standard for private data release. This makes it possible to provide strong theoretical guarantees on the privacy and utility of released data. While it is well-understood how to release data based on counts and simple functions under this guarantee, it remains to provide general purpose techniques to release data that is useful for a variety of queries. In this paper, we focus on spatial data such as locations and more generally any multi-dimensional data that can be indexed by a tree structure. Directly applying existing differential privacy methods to this type of data simply generates noise. We propose instead the class of ``private spatial decompositions'': these adapt standard spatial indexing methods such as quad trees and kd-trees to provide a private description of the data distribution. Equipping such structures with differential privacy requires several steps to ensure that they provide meaningful privacy guarantees. Various basic steps, such as choosing splitting points and describing the distribution of points within a region, must be done privately, and the guarantees of the different building blocks composed to provide an overall guarantee. Consequently, we expose the design space for private spatial decompositions, and analyze some key examples. A major contribution of our work is to provide new techniques for parameter setting and post-processing the output to improve the accuracy of query answers. Our experimental study demonstrates that it is possible to build such decompositions efficiently, and use them to answer a variety of queries privately with high accuracy. <s> BIB002 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Differential Privacy in Location-Based Services <s> With the wide deployment of smart card automated fare collection (SCAFC) systems, public transit agencies have been benefiting from huge volume of transit data, a kind of sequential data, collected every day. Yet, improper publishing and use of transit data could jeopardize passengers' privacy. In this paper, we present our solution to transit data publication under the rigorous differential privacy model for the Societe de transport de Montreal (STM). We propose an efficient data-dependent yet differentially private transit data sanitization approach based on a hybrid-granularity prefix tree structure. Moreover, as a post-processing step, we make use of the inherent consistency constraints of a prefix tree to conduct constrained inferences, which lead to better utility. Our solution not only applies to general sequential data, but also can be seamlessly extended to trajectory data. To our best knowledge, this is the first paper to introduce a practical solution for publishing large volume of sequential data under differential privacy. We examine data utility in terms of two popular data analysis tasks conducted at the STM, namely count queries and frequent sequential pattern mining. Extensive experiments on real-life STM datasets confirm that our approach maintains high utility and is scalable to large datasets. <s> BIB003 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Differential Privacy in Location-Based Services <s> Location-tagged social media have an increasingly important role in shaping behavior of individuals. With the help of location recommendations, users are able to learn about events, products or places of interest that are relevant to their preferences. User locations and movement patterns are available from geosocial networks such as Foursquare, mass transit logs or traffic monitoring systems. However, disclosing movement data raises serious privacy concerns, as the history of visited locations can reveal sensitive details about an individual's health status, alternative lifestyle, etc. In this paper, we investigate mechanisms to sanitize location data used in recommendations with the help of differential privacy. We also identify the main factors that must be taken into account to improve accuracy. Extensive experimental results on real-world datasets show that a careful choice of differential privacy technique leads to satisfactory location recommendation results. <s> BIB004 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Differential Privacy in Location-Based Services <s> Spatial Crowdsourcing (SC) is a transformative platform that engages individuals, groups and communities in the act of collecting, analyzing, and disseminating environmental, social and other spatio-temporal information. The objective of SC is to outsource a set of spatio-temporal tasks to a set of workers, i.e., individuals with mobile devices that perform the tasks by physically traveling to specified locations of interest. However, current solutions require the workers, who in many cases are simply volunteering for a cause, to disclose their locations to untrustworthy entities. In this paper, we introduce a framework for protecting location privacy of workers participating in SC tasks. We argue that existing location privacy techniques are not sufficient for SC, and we propose a mechanism based on differential privacy and geocasting that achieves effective SC services while offering privacy guarantees to workers. We investigate analytical models and task assignment strategies that balance multiple crucial aspects of SC functionality, such as task completion rate, worker travel distance and system overhead. Extensive experimental results on real-world datasets show that the proposed technique protects workers' location privacy without incurring significant performance metrics penalties. <s> BIB005 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Differential Privacy in Location-Based Services <s> In this paper we report on the ongoing research of our team Comete on location privacy. In particular, we focus on the problem of protecting the privacy of the user when dealing with location-based services. The starting point of our approach is the principle of geo-indistinguishability, a formal notion of privacy that protects the user's exact location, while allowing approximate information --- typically needed to obtain a certain desired service --- to be released. Then, we discuss the problem that raise in the case of traces, when the user makes consecutive uses of the location based system, while moving along a path: since the points of a trace are correlated, a simple repetition of the mechanism would cause a rapid decrease of the level of privacy. We then show a method to limit such degradation, based on the idea of predicting a point from previously reported points, instead of generating a new noisy point. Finally, we discuss a method to make our mechanism more flexible over space: we start from the observation that space is not uniform from the point of view of location hiding, and we propose an approach to adapt the level of privacy to each zone. <s> BIB006 </s> Differentially Private Data Publishing and Analysis: A Survey <s> Differential Privacy in Location-Based Services <s> GPS-enabled devices are now ubiquitous, from airplanes and cars to smartphones and wearable technology. This has resulted in a wealth of data about the movements of individuals and populations, which can be analyzed for useful information to aid in city and traffic planning, disaster preparedness and so on. However, the places that people go can disclose extremely sensitive information about them, and thus their use needs to be filtered through privacy preserving mechanisms. This turns out to be a highly challenging task: raw trajectories are highly detailed, and typically no pair is alike. Previous attempts fail either to provide adequate privacy protection, or to remain sufficiently faithful to the original behavior. ::: ::: This paper presents DPT, a system to synthesize mobility data based on raw GPS trajectories of individuals while ensuring strong privacy protection in the form of e-differential privacy. DPT makes a number of novel modeling and algorithmic contributions including (i) discretization of raw trajectories using hierarchical reference systems (at multiple resolutions) to capture individual movements at differing speeds, (ii) adaptive mechanisms to select a small set of reference systems and construct prefix tree counts privately, and (iii) use of direction-weighted sampling for improved utility. While there have been prior attempts to solve the subproblems required to generate synthetic trajectories, to the best of our knowledge, ours is the first system that provides an end-to-end solution. We show the efficacy of our synthetic trajectory generation system using an extensive empirical evaluation. <s> BIB007
Advances in sensor-enabled devices, such as mobile phones and wearable gadgets, allow location information to be available on social media. This means that the places that people visit are able to disclose extremely sensitive information about their behaviors, home and work locations, preferences, and habits. In addition, the continual release of ones location can be used as a trajectory. Location and trajectory privacy are emerging issues that need to be tackled BIB001 . Location based services involve several privacy concerns. For example, a location based server would like to hide the number of people in a particular region, and this is a typical range query that differential privacy can deal with. Cormode BIB002 applied spatial decomposition methods, which is a type of dataset partitioning mechanism, to decrease noise. They instantiated a hierarchical tree structure to decompose a geometric space into smaller areas with data points partitioned among the leaves. Noise is added to the count for each node. Similarly, Zhang et al. BIB004 applied spatial decomposition methods in the problem of private location recommendations, which is the extension of range queries. Quadtree is used to partition the region and noise is added to protect users' historical trajectories. Some location based applications need to hide the exact locations of individuals. Chatzikokolakis et al. BIB006 proposed a new notion, geo-indistinguishability, which protects an individual's exact location, while disclosing enough location information to obtain the desired service. Its main idea relates to a differential privacy level of the radius that the individual has visited: for any radius # > 0, an individual will have ð; #Þ-privacy. Chen et al. BIB003 presented a data-dependent solution for sanitizing large-scale trajectory data. They developed a constrained inference technique to increase the resulting utility. He et al. BIB007 presented a system to synthesize mobility data based on raw GPS trajectories. They discretize raw trajectories using hierarchical reference systems to capture individual movements at differing speeds. They then propose an adaptive mechanism to select a small set of reference systems to construct prefix tree counts. Lastly, a directionweighted sampling is applied to improve utility. Even though previous works provide various solutions to location privacy, there are still some open questions. For example, most applications require the system to release a synthetic location dataset rather than query answers, and this is a tough problem in differential privacy. Moreover, privacy issues in spatial crowdsourcing is another emerging research area BIB005 .