Privacy-aware location data publishing

Abstract

This article examines a new problem of k-anonymity with respect to a reference dataset in privacy-aware location data publishing: given a user dataset and a sensitive event dataset, we want to generalize the user dataset such that by joining it with the event dataset through location, each event is covered by at least k users. Existing k-anonymity algorithms generalize every k user locations to the same vague value, regardless of the events. Therefore, they tend to overprotect against the privacy compromise and make the published data less useful. In this article, we propose a new generalization paradigm called local enlargement, as opposed to conventional hierarchy- or partition-based generalization. Local enlargement guarantees that user locations are enlarged just enough to cover all events k times, and thus maximize the usefulness of the published data. We develop an O(H_n)-approximate algorithm under the local enlargement paradigm, where n is the maximum number of events a user could possibly cover and H_n is the Harmonic number of n. With strong pruning techniques and mathematical analysis, we show that it runs efficiently and that the generalized user locations are up to several orders of magnitude smaller than those by the existing algorithms. In addition, it is robust enough to protect against various privacy attacks.

References

1. Bayardo, R. and Agrawal, R. 2005. Data privacy through optimal k-anonymization. In Proceedings of the International Conference on Data Engineering (ICDE'05). 217--228.
2. Brinkhoff, T. 2002. A framework for generating network-based moving objects. Geoinformatica 6, 2, 153--180.
3. Chen, B.-C., LeFevre, K., and Ramakrishnan, R. 2007. Privacy skyline: Privacy with multi-dimensional adversarial knowledge. In Proceedings of the International Conference on Very Large Databases (VLDB'07).
4. Du, Y., Xia, T., Tao, Y., Zhang, D., and Zhu, F. 2007. On multidimensional k-anonymity with local recoding generalization (poster paper). In Proceedings of the International Conference on Data Engineering (ICDE'07).
5. Fung, C. M., Wang, K., and Yu, P. S. 2005. Top-Down specialization for information and privacy preservation. In Proceedings of the International Conference on Data Engineering (ICDE'05). 205--216.
6. Gedik, B. and Liu, L. 2005. Location-Privacy in mobile systems: A personalized anonymization model. In Proceedings of the IEEE International Conference on Distributed Computing Systems (ICDCS'05).
7. Gedik, B. and Liu, L. 2008. Protecting location privacy with personalized k-anonymity: Architecture and algorithms. IEEE Trans. Mobile Comput. 7, 1, 1--18.
8. Ghinita, G., Kalnis, P., and Skiadopoulos, S. 2007a. Mobihide: A mobile peer-to-peer system for anonymous location-based queries. In Proceedings of the International Symposium in Spatial and Temporal Databases (SSTD'07). 221--238.
9. Ghinita, G., Kalnis, P., and Skiadopoulos, S. 2007b. Prive: Anonymous location-based queries in distributed mobile systems. In Proceedings of the International World Wide Web Conference (WWW '07). 371--380.
10. Gruteser, M. and Grunwald, D. 2003. Anonymous usage of location-based services through spatial and temporal cloaking. In Proceedings of the ACM International Conference on Mobile Systems, Applications and Services (MobiSys'03). 31--42.
11. Iwuchukwu, T. and Naughton, J. F. 2007. K-Anonymization as spatial indexing: Toward scalable and incremental anonymization. In Proceedings of the International Conference on Very Large Databases (VLDB'07).
12. Iyengar, V. 2002. Transforming data to satisfy privacy constraints. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 279--288.
13. LeFevre, K., D.DeWitt, and Ramakrishnan, R. 2005. Incognito: Efficient full-domain k-anonymity. In Proceedings of the ACM Conference on Management of Data (SIGMOD'05). 49--60.
14. LeFevre, K., DeWitt, D. J., and Ramakrishnan, R. 2006. Mondrian multidimensional k-anonymity. In Proceedings of the International Conference on Data Engineering (ICDE'06).
15. Li, N., Li, T., and Venkatasubramanian, S. 2007. t-Closeness: Privacy beyond k-anonymity and l-diversity. In Proceedings of the 23rd IEEE International Conference on Data Engineering (ICDE'07). 106--115.
16. Machanavajjhala, A., Gehrke, J., Kifer, D., and Venkitasubramaniam, M. 2006. l-Diversity: Privacy beyond k-anonymity. In Proceedings of the 22nd IEEE International Conference on Data Engineering (ICDE'06). 24--35.
17. Martin, D. J., Kifer, D., Machanavajjhala, A., Gehrke, J., and Halpern, J. Y. 2007. Worst-Case background knowledge for privacy-preserving data publishing. In Proceedings of the International Conference on Data Engineering (ICDE'07).
18. Mokbel, M. F., Chow, C.-Y., and Aref, W. G. 2006. The new casper: Query processing for location services without compromising privacy. In Proceedings of the International Conference on Very Large Databases (VLDB'06).
19. Samarati, P. 2001. Protecting respondents privacy in microdata release. IEEE Trans. Knowl. Data Engin. 13, 6, 1010--1027.
20. Sweeney, L. 2002. Achieving k-anonymity privacy protection using generalization and suppression. Int. J. Uncertainty, Fuzz. Knowl.-based Syst. 10, 5, 571--588.
21. Vazirani, V. V. 2001. Approximation Algorithms. Springer.
22. Wang, K., Yu, P. S., and Chakraborty, S. 2004. Bottom-Up generalization: A data mining solution to privacy protection. In Proceedings of the IEEE International Conference on Data Mining (ICDM'04). 249--256.
23. Xiao, X. and Tao, Y. 2006a. Anatomy: Simple and effective privacy preservation. In Proceedings of the 32nd International Conference on Very Large Databases (VLDB '06). 139--150.
24. Xiao, X. and Tao, Y. 2006b. Personalized privacy preservation. In Proceedings of the ACM Conference on Management of Data (SIGMOD'06). 229--240.

Index Terms

• Human-centered computing

  • Visualization

    • Visualization application domains

      • Geographic visualization

• Information systems

  • Information systems applications

    • Spatial-temporal systems

• Security and privacy

  • Database and storage security

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory

      • Theory of database privacy and security