Differentially Private Publication of Location Entropy

Location entropy (LE) is an eminent metric for measuring the popularity of various locations (e.g., points-of-interest). It has applications in various areas of research, including multi-agent systems, wireless sensor networks, geosocial networks, personalized web search, image retrieval and spatial crowdsourcing. Location entropy can be used to capture the intrinsic diversity of a location without necessarily looking at the functionality of that location (e.g., is it a coffee shop or a private home? is it an airport terminal? is it a park or museum?). To illustrate LE, the figure below shows two locations with the same number of users and the number of visits. Which one do you think is more popular Intuitively, the second location is more popular because all users frequently visit the location as opposed to the first location where the black user visits most of the times.


Current solutions for computing LE (or location popularity in general) require full access to the past visits of users to locations, which has serious privacy concerns. Thus, in our recent study [1], we proposed a set of techniques based on differential privacy to publish location entropy from raw location visit data without violating users’ location privacy. Our technique would enable data aggregators such as Google, Microsoft and Apple to share their data with many industries and organizations (e.g., academia, CDC) in the form of aggregated or processed location data for the greater good, e.g., research, prevent the spread of disease.

Furthermore, we envision the data aggregators such as Google to use location entropy in two ways. First, location entropy can be used as a metric to find popular locations from location data. Our techniques help to publish such popular locations with high entropy to third parties without violating users’ location privacy, e.g., Niantic could use the published popular locations as PokeStops in the Pokemon Go game. Second, Google may use location entropy as the measure of privacy, in which Google would only reveal a location on a user’ behalf only if the location is a popular place (quantified by location entropy). Instead of directly using location entropy, our techniques add noise to its actual value so that an attacker is not able to reliably learn whether or not a particular user is present in the original data.

[1] Hien To, Kien Nguyen, and Cyrus Shahabi, Differentially Private Publication of Location Entropy, In Proceeding of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL 2016), San Francisco, CA, USA, October 31 – November 3, 2016


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s