{"id":356072,"date":"2017-01-20T11:15:07","date_gmt":"2017-01-20T19:15:07","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?p=356072"},"modified":"2017-01-20T11:15:07","modified_gmt":"2017-01-20T19:15:07","slug":"project-privtree-blurring-location-privacy","status":"publish","type":"post","link":"https:\/\/www.microsoft.com\/en-us\/research\/blog\/project-privtree-blurring-location-privacy\/","title":{"rendered":"Project PrivTree: Blurring your \u201cwhere\u201d for location privacy"},"content":{"rendered":"

By Winnie Cui, Senior Research Manager, Microsoft Research Asia<\/em><\/p>\n

Data scientist, Anthony Tockar<\/a>, used publicly available location data to show how celebrities can be tracked throughout New York City<\/a>, while working on his Master\u2019s Degree at Northwestern University. By cross-referencing public news and photos about celebrities hailing cabs in NYC, Tockar found out exactly where celebrities climbed into cabs, where they traveled and even how much they paid!<\/p>\n

As this example shows, location-based services, pulling an individual\u2019s location data from GPS, IP addresses and Wi-Fi network mapping, can be a privacy nightmare. But they can also be incredibly valuable, offering real-time navigation, local weather, geographically targeted search engine results, and other useful functions.<\/p>\n

A 2011 Microsoft survey, Location Usage & Perceptions<\/a>, found that 94 percent of customers considered location-based services valuable. However, the same survey found that 52 percent were concerned about the privacy issues related to the use of geolocation data.<\/p>\n

The privacy issue is now a focus of attention in the research community. \u201cToday\u2019s computing power and scale of publicly available data makes it easier to identify individuals from the data,” said Professor Xiaokui Xiao<\/a> at Nanyang Technological University (NTU).<\/p>\n

Recently, the collaboration between Professor Xiaokui Xiao\u2019s team and Dr. Xing Xie\u2019s group<\/a> at Microsoft Research Asia in Beijing has found a way that might alleviate the privacy concerns. The team proposes a data manipulation technique, called PrivTree, which pre-processes geolocation data to protect individual privacy. Subsequently, the privatized data can be safely used in any prospective analysis, or even made publicly available, without further risk to an individual\u2019s privacy.<\/p>\n

PrivTree works by mathematically \u201cblurring\u201d the geolocation information of a specific individual, while maintaining overall accuracy for the dataset as a whole. In the example below, individuals in the dataset are projected onto a map by their geolocation coordinates.<\/p>\n

\"PrivTree

Each marker represents an individual in the geolocation database.<\/p><\/div>\n

Next, PrivTree goes through two phases to \u201cblur out\u201d the geolocation information of each individual.<\/p>\n

Phase 1: Map Partitioning<\/strong><\/p>\n

\"\"

The map is partitioned into a few sub-regions, based on the density of the data points.<\/p><\/div>\n

Phase 2:\u00a0Location Perturbation<\/strong><\/p>\n

\"\"

Using statistical analysis, individuals are subjected to a perturbation scheme where they are randomly removed, added or shuffled to guarantee privacy while maintaining statistical accuracy. A new geolocation database is ready to use, after applying location perturbation to each sub-region.<\/p><\/div>\n

This ends up with a new set of data points that follows a similar distribution to the original data, but the real location of each participant has been masked. The privatized data is then released as the output of PrivTree. PrivTree can be extended to support all kinds of location data \u2013 for example, your daily jogging route uploaded to a health app. The research paper, PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions<\/a> was accepted by\u00a0ACM SIGMOD 2016, the world\u2019s top data management conference.<\/p>\n

Professor Xiao said this about collaborating with Microsoft researchers, \u201cMicrosoft Research Asia\u2019s expertise in managing large sets of geolocation data, such as Beijing taxi data, played a crucial role to the success of this project. It helped us develop and test our model.\u201d<\/p>\n

Professor Xiao plans to further integrate PrivTree techniques into Microsoft\u2019s location-based services to provide privacy protection. Dr. Xing Xie<\/a>, Senior Researcher at Microsoft Research Asia, and a collaborator on this project, observed \u201cData privacy is a critical challenge in the cloud computing era, especially for user-generated location data that contains a lot of private knowledge about individuals. We hope this joint work can contribute to–and eventually lead to–a safer world for everyone.\u201d<\/p>\n

Learn more:<\/strong><\/p>\n