Abstract
Location privacy receives considerable attentions in emerging location based services. Most current practices however either ignore users’ preferences or incompletely fulfill privacy preferences. In this paper, we propose a privacy protection solution to allow users' preferences in the fundamental query of k nearest neighbors (kNN). Particularly, users are permitted to choose privacy preferences by specifying minimum inferred region. Via Hilbert curve based transformation, the additional workload from users' preferences is alleviated. Furthermore, this transformation reduces time-expensive region queries in 2-D space to range the ones in 1-D space. Therefore, the time efficiency, as well as communication efficiency, is greatly improved due to clustering properties of Hilbert curve. Further, details of choosing anchor points are theoretically elaborated. The empirical studies demonstrate that our implementation delivers both flexibility for users’ preferences and scalability for time and communication costs.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Gruteser M, Schelle G, Jain A, Han R, Grunwald D. Privacy-aware location sensor networks. In Proc. the 9th Workshop on Hot Topics in Operating Systems (HotOS 2003), Hawaii, USA, May 18-21, 2003, pp.163–167.
Beresford A R, Stajano F. Location privacy in pervasive computing. IEEE Pervasive Computing, 2003, 2(1): 46–55.
Ronssopoulos Nick R, Kelley S, Vincent F. Nearest neighbor queries. In Proc. the ACM SIGMOD International Conference on Management of Data (SIGMOD 1995), San Jose, California, USA, May 22-25, 1995, pp.71–79.
Xiao Z, Meng X F, Xu J L. Quality aware privacy protection for location-based services. In Proc. the 12th International Conference on Database Systems for Advanced Applications (DASFAA 2007), Bangkok, Thailand, April 9-12, 2007, pp.434–446.
Bettini C, Wang X S, Jajodia S. Protecting privacy against location-based personal identification. In Proc. the 2nd VLDB Workshop on Secure Data Management (SDM 2005), Trondheim, Norway, September 2-3, 2005, pp.185–199.
Mokbel M F, Chow C Y, Aref W G. The new Casper: Query processing for location services without compromising privacy. In Proc. the 32nd International Conference on Very Large Data Bases (VLDB 2006), Seoul, Korea, September 12-15, 2006, pp.763–774.
Li P Y, Peng W C, Wang T W, Ku W S, Xu J, Hamilton J A. A cloaking algorithm based on spatial networks for location privacy. In Proc. IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing (SUTC 2008), Taichung, Taiwan, China, June 11-13, 2008, pp.90–97.
Duckham M, Kulik L. A formal model of obfuscation and negotiation for location privacy. In Proc. the 3th International Conference on Pervasive Computing (Pervasive 2005), Munich, Germany, May 8-13, 2005, pp.152–170.
Kalnis P, Ghinita G, Mouratidis K, Papadias D. Preventing location-based identity inference in anonymous spatial queries. IEEE Trans. Knowl. Data Eng., 2007, 19(12): 1719–1733.
Ghinita G, Kalnis P, Skiadopoulos S. PRIVE: Anonymous location-based queries in distributed mobile systems. In Proc. the 16th International Conference on World Wide Web (WWW 2007), Banff, Alberta, Canada, May 8-12, 2007, pp.371–380.
Indyk P, Woodruff D P. Polylogarithmic private approximations and efficient matching. In Proc. the 3 rd Theory of Cryptography Conference (TCC 2006), New York, NY, USA, March 4-7, 2006, pp.245–264.
Khoshgozaran A, Shahabi C. Blind evaluation of nearest neighbor queries using space transformation to preserve location privacy. In Proc. the 10th International Conference on Advances in Spatio and Temporal Databases (SSTD 2007), Boston, MA, USA, July 16-18, 2007, pp.239–257.
Yiu M L, Jensen C S, Huang X G, Lu H. SpaceTwist: Managing the trade-offs among location privacy, query performance, and query accuracy in mobile services. In Proc. the 24th International Conference on Data Engineering (ICDE 2008), Cancún, México, April 7-12, 2008, pp.366–375.
Gong Z Q, Sun G Z, Xie X. Protecting privacy in location-based services using k-anonymity without cloaked region. In Proc. the 11th International Conference on Mobile Data Management (MDM 2010), Kanas City, Missouri, USA, May 23-26, 2010, pp.366–371.
Ghinita G, Kalnis P, Khoshgozaran A, Shahabi C, Tan K L. Private queries in location based services: Anonymizers are not necessary. In Proc. the ACM SIGMOD International Conference on Management of Data (SIGMOD 2008), Vancouver, BC, Canada, June 9-12, 2008, pp.121–132.
Cheng R, Zhang Y, Bertino E, Prabhakar S. Preserving user location privacy in mobile data management infrastructures. In Proc. the 6th Workshop on Privacy Enhancing Technologies (PET 2006), Cambridge, UK, June 28-30, 2006, pp.393–412.
Pan X, Xu J L, Meng X F. Protecting location privacy against location-dependent attacks in mobile services. IEEE Transactions on Knowledge and Data Engineering, 2011, http://doi.ieeecomputersociety.org/10.1109/TKDE.2011.105.
Xu J L, Tang X Y, Hu H B, Du J. Privacy-conscious location-based queries in mobile environments. IEEE Trans. Parallel Distrib. Syst., 2010, 21(3): 313–326.
Papadopoulos S, Bakiras S, Papadias D. Nearest neighbor search with strong location privacy. PVLDB, 2010, 3(1): 619–629.
Moon B, Jagadish H V, Faloutsos C, Saltz J H. Analysis of the clustering properties of the Hilbert space-filling curve. IEEE Trans. Knowl. Data Eng., 2001, 13(1): 124–141.
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by the National Natural Science Foundation of China under Grant Nos. 61003057 and 60973023.
Electronic Supplementary Material
Below is the link to the electronic supplementary material.
Rights and permissions
About this article
Cite this article
Ni, WW., Zheng, JW. & Chong, ZH. HilAnchor: Location Privacy Protection in the Presence of Users’ Preferences. J. Comput. Sci. Technol. 27, 413–427 (2012). https://doi.org/10.1007/s11390-012-1231-2
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11390-012-1231-2