An efficient method for privacy preserving location queries

Abstract

Recently, the issue of privacy preserving location queries has attracted much research. However, there are few works focusing on the tradeoff between location privacy preservation and location query information collection. To tackle this kind of tradeoff, we propose the privacy persevering location query (PLQ), an efficient privacy preserving location query processing framework. This framework can enable the location-based query without revealing user location information. The framework can also facilitate location-based service providers to collect some information about the location based query, which is useful in practice. PLQ consists of three key components, namely, the location anonymizer at the client side, the privacy query processor at the server side, and an additional trusted third party connecting the client and server. The location anonymizer blurs the user location into a cloaked area based on a map-hierarchy. The map-hierarchy contains accurate regions that are partitioned according to real landforms. The privacy query processor deals with the requested nearest-neighbor (NN) location based query. A new convex hull of polygon (CHP) algorithm is proposed for nearest-neighbor queries using a polygon cloaked area. The experimental results show that our algorithms can efficiently process location based queries.

Keywords

location based service (LBS) / privacy preservation / nearest-neighbor (NN) location query

References

[1] Ackerman L, Kempf J, Miki T. Wireless location privacy: a report on law and policy in the United States, the Europrean Union, and Japan. Technical Report DCL-TR2003-001, DoCoMo Commuinication Laboratories, USA, 2003

[2] Barkhuus L, Dey A K. Location-based services for mobile telephony: a study of users’ privacy concerns. In: Proceedings of IFIP TC13 International Conference on Human-Computer Interaction. 2003

[3] Beresford A R, Stajano F. Location privacy in pervasive computing. IEEE Pervasive Computing, 2003, 2(1): 46-55

[4] Gedik B, Liu L. Protecting location privacy with personalized kanonymity: architecture and algorithms. IEEE Transactions on Mobile Computing, 2008, 7(1): 1-18

[5] Ghinita G, Kalnis P, Skiadopoulos S. PRIVE: anonymous locationbased queries in distributed mobile systems. In: Proceedings of the 16th International Conference on World Wide Web. 2007, 371-389

[6] Wang T, Liu L. Privacy-aware mobile services over road networks. Proceedings of the VLDB Endowment, 2009, 2(1): 1042-1053

[7] Kido H, Yanagisawa Y, Satoh T. An anonymous communication technique using dummies for location-based services. In: Proceedings of the 2005 International Conference on Pervasive Services. 2005, 88-97

[8] Hong J I, Landay J A. An architecture for privacy-sensitive ubiquitous computing. In: Proceedings of the 2nd International Conference on Mobile Systems, Applications, and Services. 2004, 177-189

[9] Duckham M, Kulik L. A formal model of obfuscation and negotiation for location privacy. In: Proceedings of the 3rd International Conference on Pervasive Computing. 2005, 152-170

[10] Gruteser M, Grunwald D. Anonymous usage of location-based services through spatial and temporal cloaking. In: Proceedings of the 1st International Conference on Mobile Systems, Applications and Services. 2003, 31-42

[11] Mokbel M, Chow C, Aref W. The new Casper: query processing for location services without compromising privacy. In: Proceedings of the 32nd International Conference on Very Large Data Bases. 2006, 763-774

[12] Gedik B, Liu L. Location privacy in mobile systems: a personalized anonymization model. In: Proceedings of the 25th IEEE International Conference on Distributed Computing Systems. 2005, 620-629

[13] Sweeney L. Achieving k-anonymity privacy protection using generalization and suppression. International Journal on Uncertainty, Fuzziness and Knowledge-Based Systems, 2002, 10(5): 571-588

[14] Ardagna C A, Cremonini M, Gianini G. Landscape-aware locationprivacy protection in location-based services. Journal of Systems Architecture, 2009, 55(4): 243-254

[15] Bamba B, Liu L, Pesti P, Wang T. Supporting anonymous location queries in mobile environments with privacy grid. In: Proceedings of the 17th International Conference on World WideWeb. 2008, 237-246

[16] Chow C Y, Mokbel M F, Liu X. A peer-to-peer spatial cloaking algorithm for anonymous location-based services. In: Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems. 2006, 171-178

[17] Ghinita G, Kalnis P, Khoshgozaran A, Shahabi C, Tan K L. Private queries in location based services: anonymizers are not necessary. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. 2008, 121-132

[18] Chen J, Cheng R. Efficient evaluation of imprecise location-dependent queries. In: Proceedings of IEEE the 23rd International Conference on Data Engineering. 2007, 586-595

[19] Cheng R, Kalashnikov D V, Prabhakar S. Evaluating probabilistic queries over imprecise data. In: Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data. 2003, 551-562

[20] Hu H, Xu J. Non-exposure location anonymity. In: Proceedings of the IEEE 25th International Conference on Data Engineering. 2009, 1120-1131

[21] Zhou B, Pei J. Preserving privacy in social networks against neighborhood attacks. In: Proceedings of the IEEE 24th International Conference on Data Engineering. 2008, 506-515

[22] Pan X, Meng X, Xu J. Distortion-based anonymity for continuous queries in location-based mobile services. In: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 2009, 256-265

[23] Wong R CW, Liu Y, Yin J, Huang Z, Fu AWC, Pei J. (α,k)-anonymity based privacy preservation by lossy join. In: Proceedings of the Joint 9th Asia-Pacific Web and the 8th International Conference onWeb-age Information Management. 2007, 733-744

[24] Bu Y, Fu A W C, Wong R C W, Chen L, Li J. Privacy preserving serial data publishing by role composition. Proceedings of the VLDB Endowment, 2008, 1(1): 845-856

[25] Tian X, Sha C, Wang X, Zhou A. Privacy preserving query processing on secret share based data storage. In: Proceedings of the 16th International Conference on Database Systems for Advanced Applications, Volume Part I. 2011, 108-122

[26] Guttman A. R-trees: a dynamic index structure for spatial searching. In: Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data. 1984, 47-57

[27] Fortune S. A sweepline algorithm for voronoi diagrams. In: Proceedings of the 2nd Annual Symposium on Computational Geometry. 1986, 313-322

[28] Mioc D, Anton F, Gold C M, Moulin B. Map updates in a dynamic Voronoi data structure. In: Proceedings of the 3rd International Symposium on Voronoi Diagrams in Science and Engineering. 2006, 264-269

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg