Differential privacy for location pattern mining

Shen Shyang Ho, Shuhua Ruan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

60 Scopus citations

Abstract

One main concern for individuals to participate in the data collection of personal location history records is the disclosure of their location and related information when a user queries for statistical or pattern mining results derived from these records. In this paper, we investigate how the privacy goal that the inclusion of one's location history in a statistical database with location pattern mining capabilities does not substantially increase one's privacy risk. In particular, we propose a differentially private pattern mining algorithm for interesting geographic location discovery using a region quadtree spatial decomposition to preprocess the location points followed by applying a density-based clustering algorithm. A differentially private region quadtree is used for both de-noising the spatial domain and identifying the likely geographic regions containing the interesting locations. Then, a differential privacy mechanism is applied to the algorithm outputs, namely: the interesting regions and their corresponding stay point counts. The quadtree spatial decomposition enables one to obtain a localized reduced sensitivity to achieve the differential privacy goal and accurate outputs. Experimental results on synthetic datasets are used to show the feasibility of the proposed privacy preserving location pattern mining algorithm.

Original languageEnglish (US)
Title of host publicationSPRINGL 2011 - Proceedings of the 4th ACM SIGSPATIAL International Workshop on Security and Privacy in GIS and LBS
Pages17-24
Number of pages8
DOIs
Publication statusPublished - Dec 1 2011
Event4th ACM SIGSPATIAL International Workshop on Security and Privacy in GIS and LBS, SPRINGL 2011 - Chicago, IL, United States
Duration: Nov 1 2011Nov 1 2011

Publication series

NameSPRINGL 2011 - Proceedings of the 4th ACM SIGSPATIAL International Workshop on Security and Privacy in GIS and LBS

Other

Other4th ACM SIGSPATIAL International Workshop on Security and Privacy in GIS and LBS, SPRINGL 2011
CountryUnited States
CityChicago, IL
Period11/1/1111/1/11

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Computer Graphics and Computer-Aided Design
  • Computer Networks and Communications

Cite this

Ho, S. S., & Ruan, S. (2011). Differential privacy for location pattern mining. In SPRINGL 2011 - Proceedings of the 4th ACM SIGSPATIAL International Workshop on Security and Privacy in GIS and LBS (pp. 17-24). (SPRINGL 2011 - Proceedings of the 4th ACM SIGSPATIAL International Workshop on Security and Privacy in GIS and LBS). https://doi.org/10.1145/2071880.2071884