Dynamic Tessellation to Ensure K-anonymity

Smart phone-powered data collection systems are rapidly becoming an effective method of gathering field data. One major challenge of using smart phones to collect data is the ability to link smart phone metadata, such as location at a specific time, back to the user -- thereby violating the privacy of that individual. A promising approach to helping ensure user privacy is through geographical k-anonymity, which attempts to ensure that every gathered data reading is geographically indistinguishable from k-1 other readings. The approach helps prevent precise localization of the user or reverse engineering of reported data by leveraging the user's known location. This paper presents a dynamic tessellation algorithm for k-anonymity that provides better privacy preservation and data reporting precision than previous static algorithms for k-anonymity. The paper presents empirical results from a real world data set that demonstrate the improvements in privacy provided by the algorithm.