Research On Privacy Preservation Techniques For Spatial Data

In recent years,along with the popularization of smart mobile devices and the development of advanced GPS technology,spatial data are generated at an unprecedented scale.Researchers from different disciplines pay more and more concerns on the spatial data for mining the potential values on research and business.Spatial data analysis has become a hot-topic and core research issue of Geography,Sociology,Economics and Informatics.Spatial data publication and analysis techniques,as a powerful methodology to discover knowledge from massive data,have a very wide range of applications in daily life.However,spatial data usually contain individuals' sensitive information,which makes it an important concern that how to avoid compromising individual privacy when releasing and analyzing spatial data.Compared with relational data,the categories of privacy information and ways of privacy leakages become more diverse,so that it is a great challenge to design privacy-preserving techniques for spatial data.Protecting spatial data privacy is a hot issue that needs to be solved in the field of data privacy protection.Therefore,we need to investigate corresponding privacy protecting technologies for spatial data,regarding the categories of privacy information and ways of privacy leakages.This dissertation analyzed the requirements of users and deeply studied the various privacy leakage for spatial data.According to different application situations,some efficient and targeted solutions are proposed to satisfy people's practical needs.The main contributions are summarized as follow.(1)For location privacy preservation on road networks,we study the problem that the adversary could launch an attack using locations' semantic information as background knowledge,which results in location privacy leakage of query users.In addition,we also take the location privacy leakage of other users in the system into consideration,while providing the privacy protection for a location-based query user.Thus,to tackle these problems,we propose PrivSem,a novel framework which integrates location kanonymity,segment l-semantic diversity,and differential privacy to protect user location privacy from violation.In this framework,we devise a location cloaking algorithm.Since the cloaking algorithm only has access to the location data sanitized according to differential privacy,it is particularly challenging to determine an effective cloaked area.Further,we investigate an error analysis model to ensure the effectiveness of the generated cloaked areas.Finally,through formal privacy analysis,we show that our proposed approach is effective in providing privacy guarantees.Extensive experimental evaluations are conducted to demonstrate the effectiveness of the proposed approach in terms of providing privacy protection for mobile users on road networks.(2)For mining frequent location sequential pattern,we investigate that directly releasing discovered frequent patterns with true support counts will carry significant risk to privacy of individuals.Therefore,we propose a Differential Private frequent Location Sequence Mining(DP-LSM)algorithm.In more detailed,we use a downward closure property to generate the candidate set of sequence patterns,a smart truncating based technique to sample frequent patterns in the candidate set,and a geometric mechanism to perturb the true supports of each sampled pattern.In addition,to improve the usability of the results,we propose a threshold modification method to reduce truncation error and propagation error in the mining process.The theoretical analysis show that the proposed approach is ?-differentially private.The experimental results demonstrate the both effectiveness and efficiency of DP-LSM.(3)For analyzing trajectory data,we study the problem that improper mining timeconstrained frequent location sequential pattern could jeopardize the individually's privacy.To address this problem,we propose a two-phase algorithm PrivTS,which consists of sample-based filtering and count refining modules.In the first phase,we propose a modified downward closure property to generate candidate location sequential patterns,and devise an improved sparse vector technique to retrieve a set of potentially frequent sequential patterns from candidate set.In the second phase,we propose a group-based counting method and a greedy-based counting method to compute noisy supports of these potentially frequent patterns.Through formal privacy analysis,we show that our proposed approach guarantees ?-differential privacy.Finally,extensive experiments demonstrate that PrivTS maintains high utility while providing privacy guarantees.(4)For location-record data publication,we study the problem that the data collection may pose considerable threats to individuals' privacy.Based on local differential privacy,we propose LDPart,a probabilistic top-down partitioning algorithm to effectively generate a sanitized location-record data.This approach employs a carefully designed partition tree model to extract the essential information in terms of location records.With the help of this model,rather than exploring the entire universe of all possible distinct location records,LDPart focuses only on those potentially "non-zero".Compared with dividing the privacy budget,allocating user population is more contribute to reduce release error.According to this principle,we propose a novel adaptive user allocation scheme so that LDPart could allocate less users on internal nodes and retain most of the users on estimating counts of leaf nodes.Further,we propose a formal choice of a threshold value and a series of optimization techniques to improve the accuracy of the released data.Extensive experiments demonstrate that the proposed approach maintains high utility while providing privacy guarantees.Regarding the potential threatens and challenges,this dissertation studies on key techniques of protecting privacy for spatial data,including location privacy preservation on road networks,privacy protection in spatial data publication and analysis.This dissertation builds a foundation of providing a complete privacy protection for spatial data.