Personal tools
You are here: Home Title: Mobile $r$-gather: Distributed and Geographic Clustering for Location Anonymity

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

— filed under:

Speaker: Rik Sarkar

What
  • Lab Lunch
When Feb 13, 2018
from 01:00 PM to 02:00 PM
Where Mini Forum 2 (MF2) Level 4
Add event to calendar vCal
iCal


Publication:

http://homepages.inf.ed.ac.uk/rsarkar/papers/r-gather.pdf


Abstract:

We study the $r$-gather clustering problem in a mobile and distributed setting. 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. It also applies to allocation of constrained resources. Prior works on $r$-gather problems are centralized and cannot be easily adapted to the mobile setting. We describe a distributed algorithm that operates on local data and 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, and can handle node mobility. 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 favourable as possible, irrespective of the global configuration. Further, we improve the theoretical hardness results for the problem in the Euclidean setting

Document Actions