Mobile r-gather: Distributed and Geographic Clustering for Location Anonymity

Jiemin Zeng, Gaurish Telang, Matthew P. Johnson, Rik Sarkar, Jie Gao, Esther M. Arkin, Joseph S. B. Mitchell

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

Abstract

We study the r -gather clustering problem in a mobile and distributed seŠing. In this problem, nodes must be clustered into groups of at least r nodes each, and the goal is to minimize the diameter of the clusters. This notion of clustering is motivated by protecting user anonymity in location-based services or trajectory
publication. Prior works on r -gather problems are centralized and cannot be easily adapted to the mobile setting. We describe a distributed algorithm that produces compact clusters, within an approximation factor 4 of the minimum cluster diameter possible. The algorithm can run on the mobile nodes and access points at the network edge locally, and can handle node mobility, rapidly
switching cluster memberships as needed. The distributed approach naturally comes with the advantage of greater resilience and stability. Additionally, we show that it achieves local optimality; i.e., from the point of view of any particular node, the solution is nearly as favorable as possible, irrespective of the global con€figuration. We also show how to cluster trajectories with dynamic regroupings. Further, we improve the theoretical hardness results for the problem in the Euclidean setting.
Original languageEnglish
Title of host publicationMobihoc '17 Proceedings of the 18th ACM International Symposium on Mobile Ad Hoc Networking and Computing
PublisherACM
Number of pages10
ISBN (Print)978-1-4503-4912-3
DOIs
Publication statusPublished - 14 Jul 2017
Event18th ACM International Symposium on Mobile Ad Hoc Networking and Computing - Chennai, India
Duration: 10 Jul 201714 Jul 2017
https://www.sigmobile.org/mobihoc/2017/

Conference

Conference18th ACM International Symposium on Mobile Ad Hoc Networking and Computing
Abbreviated titleMobiHoc 2017
Country/TerritoryIndia
CityChennai
Period10/07/1714/07/17
Internet address

Fingerprint

Dive into the research topics of 'Mobile r-gather: Distributed and Geographic Clustering for Location Anonymity'. Together they form a unique fingerprint.

Cite this