| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Preventing Location-Based Identity Inference in Anonymous Spatial Queries
December 2007 (vol. 19 no. 12)
pp. 1719-1733
The increasing trend of embedding positioning capabilities (e.g., GPS) in mobile devices facilitates the widespread use of Location Based Services. For such applications to succeed, privacy and confidentiality are essential. Existing privacy-enhancing techniques rely on encryption to safeguard communication channels, and on pseudonyms to protect user identities. Nevertheless, the query contents may disclose the physical location of the user. In this paper, we present a framework for preventing Location-based identity inference of users who issue spatial queries to Location Based Services. We propose transformations based on the well-established K-anonymity concept to compute exact answers for range and nearest neighbor search, without revealing the query source. Our methods optimize the entire process of anonymizing the requests and processing the transformed spatial queries. Extensive experimental studies suggest that the proposed techniques are applicable to real-life scenarios with numerous mobile users.
[1] 1719 N.R. Adam and J.C. Wortmann, “Security-Control Methods for Statistical Databases: A Comparative Study,” ACM Computing Surveys, vol. 21, no. 4, pp. 515-556, 1989.[2] C.C. Aggarwal, “On K-Anonymity and the Curse of Dimensionality,” Proc. 31st Int'l Conf. Very Large Data Bases (VLDB '05), pp.901-909, 2005.[3] R. Agrawal and R. Srikant, “Privacy-Preserving Data Mining,” Proc. 19th ACM SIGMOD Int'l Conf. Management of Data (SIGMOD '00), pp. 439-450, 2000.[4] R. Bayardo and R. Agrawal, “Data Privacy through Optimal K-Anonymization,” Proc. 21st IEEE Int'l Conf. Data Eng. (ICDE '00), pp. 217-228, 2005.[5] N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger, “The ${\rm R}^{\ast}{\hbox{-}}{\rm{Tree}}$ : An Efficient and Robust Access Method for Points and Rectangles,” Proc. Ninth ACM SIGMOD Int'l Conf. Management of Data (SIGMOD '90), pp. 322-331, 1990.[6] A.R. Beresford and F. Stajano, “Location Privacy in Pervasive Computing,” IEEE Pervasive Computing, vol. 2, no. 1, pp. 46-55, 2003.[7] C. Bettini, X.S. Wang, and S. Jajodia, “Protecting Privacy against Location-Based Personal Identification,” Proc. Second VLDB Workshop Secure Data Management (SDM '05), pp. 185-199, 2005.[8] R. Cheng, Y. Zhang, E. Bertino, and S. Prabhakar, “Preserving User Location Privacy in Mobile Data Management Infrastructures,” Proc. Sixth Workshop Privacy Enhancing Technologies (PET '06), pp. 393-412, 2006.[9] B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan, “Private Information Retrieval,” J. ACM, vol. 45, no. 6, pp. 965-981, 1998.[10] C.-Y. Chow, M.F. Mokbel, and X. Liu, “A Peer-to-Peer Spatial Cloaking Algorithm for Anonymous Location-Based Services,” Proc 14th ACM Int'l Symp. Advances in Geographic Information Systems (ACM-GIS '06), pp. 171-178, 2006.[11] B. Gedik and L. Liu, “Location Privacy in Mobile Systems: A Personalized Anonymization Model,” Proc. 25th Int'l Conf. Distributed Computing Systems (ICDCS '05), pp. 620-629, 2005.[12] G. Ghinita, P. Kalnis, and S. Skiadopoulos, “PRIVE: Anonymous Location-Based Queries in Distributed Mobile Systems,” Proc. 16th Int'l World Wide Web Conf. (WWW '07), pp. 371-380, 2007.[13] G. Ghinita, P. Kalnis, and S. Skiadopoulos, “MOBIHIDE: A Mobile Peer-to-Peer System for Anonymous Location-Based Queries,” Proc. 10th Int'l Symp. Spatial and Temporal Databases (SSTD '07), pp.221-238, 2007.[14] G. Ghinita, P. Karras, P. Kalnis, and N. Mamoulis, “Fast Data Anonymization with Low Information Loss,” Proc. 33rd Int'l Conf. Very Large Data Bases (VLDB '07), 2007.[15] M. Gruteser and D. Grunwald, “Anonymous Usage of Location-Based Services through Spatial and Temporal Cloaking,” Proc. First Int'l Conf. Mobile Systems, Applications, and Services (MobiSys '03), pp. 31-42, 2003.[16] B. Hoh and M. Gruteser, “Protecting Location Privacy through Path Confusion,” Proc. First Int'l Conf. Security and Privacy for Emerging Areas in Comm. Networks (SecureComm '05), pp. 194-205, 2005.[17] H. Hu and D.L. Lee, “Range Nearest-Neighbor Query,” IEEE Trans. Knowledge and Data Eng., vol. 18, no. 1, pp. 78-91, Jan. 2006.[18] P. Kamat, Y. Zhang, W. Trappe, and C. Ozturk, “Enhancing Source-Location Privacy in Sensor Network Routing,” Proc. 25th Intl' Conf. Distributed Computing Systems (ICDCS '05), pp. 599-608, 2005.[19] K. LeFevre, D.J. DeWitt, and R. Ramakrishnan, “Incognito: Efficient Full-Domain K-Anonymity,” Proc. 24th ACM SIGMOD Int'l Conf. Management of Data (SIGMOD '05), pp. 49-60, 2005.[20] A. Machanavajjhala, J. Gehrke, D. Kifer, and M. Venkitasubramaniam, “L-Diversity: Privacy beyond K-Anonymity,” Proc. 22nd IEEE Int'l Conf. Data Eng. (ICDE '06), 2006.[21] A. Meyerson and R. Williams, “On the Complexity of Optimal K-Anonymity,” Proc. 23rd ACM Symp. Principles of Database Systems (PODS '04), pp. 223-228, 2004.[22] M.F. Mokbel, W.G. Aref, and I. Kamel, “Analysis of Multi-Dimensional Space-Filling Curves,” GeoInformatica, vol. 7, no. 3, pp. 179-209, 2003.[23] M.F. Mokbel, C.Y. Chow, and W.G. Aref, “The New Casper: Query Processing for Location Services without Compromising Privacy,” Proc. 32nd Int'l Conf. Very Large Data Bases (VLDB '06), pp. 763-774, 2006.[24] B. Moon, H. Jagadish, and C. Faloutsos, “Analysis of the Clustering Properties of the Hilbert Space-Filling Curve,” IEEE Trans. Knowledge and Data Eng., vol. 13, no. 1, pp. 124-141, Jan./Feb. 2001.[25] P. Samarati, “Protecting Respondents' Identities in Microdata Release,” IEEE Trans. Knowledge and Data Eng., vol. 13, no. 6, pp.1010-1027, Nov./Dec. 2001.[26] H. Samet, The Design and Analysis of Spatial Data Structures. Addison-Wesley, 1990.[27] L. Sweeney, “K-Anonymity: A Model for Protecting Privacy,” Int'l J. Uncertainty, Fuzziness and Knowledge-Based Systems, vol. 10, no. 5, pp. 557-570, 2002.[28] Y. Tao and D. Papadias, “Historical Spatio-Temporal Aggregation,” ACM Trans. Information Systems, vol. 23, no. 1, pp. 61-102, 2005.[29] Y. Tao, D. Papadias, and Q. Shen, “Continuous Nearest Neighbor Search,” Proc. 28th Int'l Conf. Very Large Data Bases (VLDB '02), pp.287-298, 2002.[30] Y. Theodoridis, “The R-Tree-Portal,” http:/www.rtreeportal. org, 2003.[31] X. Xiao and Y. Tao, “Personalized Privacy Preservation,” Proc. 25th ACM SIGMOD Int'l Conf. Management of Data (SIGMOD '06), pp. 229-240, 2006.
Index Terms:
Spatial databases, Security and Privacy Protection, Mobile Applications
Citation:
Panos Kalnis, Gabriel Ghinita, Kyriakos Mouratidis, Dimitris Papadias, "Preventing Location-Based Identity Inference in Anonymous Spatial Queries," IEEE Transactions on Knowledge and Data Engineering, vol. 19, no. 12, pp. 1719-1733, Aug. 2007, doi:10.1109/TKDE.2007.190662
