Chi-Yin Chow
Mohamed F. Mokbel
Walid G. Aref
Skip Abstract Section
Abstract
In this article, we present a new privacy-aware query processing framework, Capser*, in which mobile and stationary users can obtain snapshot and/or continuous location-based services without revealing their private location information. In particular, we propose a privacy-aware query processor embedded inside a location-based database server to deal with snapshot and continuous queries based on the knowledge of the user's cloaked location rather than the exact location. Our proposed privacy-aware query processor is completely independent of how we compute the user's cloaked location. In other words, any existing location anonymization algorithms that blur the user's private location into cloaked rectilinear areas can be employed to protect the user's location privacy. We first propose a privacy-aware query processor that not only supports three new privacy-aware query types, but also achieves a trade-off between query processing cost and answer optimality. Then, to improve system scalability of processing continuous privacy-aware queries, we propose a shared execution paradigm that shares query processing among a large number of continuous queries. The proposed scalable paradigm can be tuned through two parameters to trade off between system scalability and answer optimality. Experimental results show that our query processor achieves high quality snapshot and continuous location-based services while supporting queries and/or data with cloaked locations.
- Ackerman, L., Kempf, J., and Miki, T. 2003. Wireless location privacy: A report on law and policy in the United States, the European Union, and Japan. Tech. rep. DCL-TR2003-001, DoCoMo Communication Laboratories.Google Scholar
- Aggarwal, G., Bawa, M., Ganesan, P., Garcia-Molina, H., Kenthapadi, K., Mishra, N., Motwani, R., Srivastava, U., Thomas, D., Widom, J., and Xu, Y. 2004. Vision paper: Enabling privacy for the paranoids. In Proceedings of the International Conference on Very Large Data Bases (VLDB). Google ScholarDigital Library
- Agrawal, R., Evfimievski, A. V., and Srikant, R. 2003. Information sharing across private databases. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). Google ScholarDigital Library
- Anonymizer. 2008. Anonymous surfing. http://www.anonymizer.com.Google Scholar
- Bamba, B., Liu, L., Pesti, P., and Wang, T. 2008. Supporting anonymous location queries in mobile environments with privacygrid. In Proceedings of the International World Wide Web Conference (WWW). Google ScholarDigital Library
- Barkhuus, L. and Dey, A. K. 2003. Location-based services for mobile telephony: A study of users' privacy concerns. In Proceedings of the IFIP Conference on Human-Computer Interaction (INTERACT).Google Scholar
- Beresford, A. R. and Stajano, F. 2003. Location privacy in pervasive computing. IEEE Pervasive Comput. 2, 1, 46--55. Google ScholarDigital Library
- Bureau, U. C. 2006. Tiger/line census files http://www.census.gov/geo/www/tiger/.Google Scholar
- Cai, Y., Hua, K. A., and Cao, G. 2004. Processing range-monitoring queries on heterogeneous mobile objects. In Proceedings of the International Conference on Mobile Data Management (MDM).Google Scholar
- Cheng, R., Zhang, Y., Bertino, E., and Prabhakar, S. 2006. Preserving user location privacy in mobile data management infrastructures. In Proceedings of the Privacy Enhancing Technology Workshop (PET). Google ScholarDigital Library
- Chow, C.-Y. and Mokbel, M. F. 2007. Enabling private continuous queries for revealed user locations. In Proceedings of the International Symposium on Advances in Spatial and Temporal Databases (SSTD). Google ScholarDigital Library
- Chow, C.-Y., Mokbel, M. F., and He, T. 2008. Tinycasper: A privacy-preserving aggregate location monitoring system in wireless sensor networks (demo). In Proceedings of the ACM International Conference on Management of Data (SIGMOD). Google ScholarDigital Library
- Chow, C.-Y., Mokbel, M. F., and Liu, X. 2006. A peer-to-peer spatial cloaking algorithm for anonymous location-based services. In Proceedings of the ACM Symposium on Advances in Geographic Information Systems (GIS). Google ScholarDigital Library
- Du, W. and Atallah, M. J. 2001. Secure multi-party computation problems and their applications: A review and open problems. In Proceedings of the New Security Paradigms Workshop. Google ScholarDigital Library
- Duckham, M. and Kulik, L. 2005. A formal model of obfuscation and negotiation for location privacy. In Proceedings of the International Conference on Pervasive Computing. Google ScholarDigital Library
- Emekci, F., Agrawal, D., Abbadi, A. E., and Gulbeden, A. 2006. Privacy preserving query processing using third parties. In Proceedings of the International Conference on Data Engineering (ICDE). Google ScholarDigital Library
- FoxNews. 2004. Man accused of stalking ex-girlfriend with GPS. http://www.foxnews.com/story/0,2933,131487,00.html. September 4.Google Scholar
- Gedik, B. and Liu, L. 2004. Mobieyes: Distributed processing of continuously moving queries on moving objects in a mobile system. In Proceedings of the International Conference on Extending Database Technology (EDBT).Google Scholar
- Gedik, B. and Liu, L. 2005. A customizable k-anonymity model for protecting location privacy. In Proceedings of the International Conference on Distributed Computing Systems (ICDCS).Google Scholar
- Gedik, B. and Liu, L. 2008. Protecting location privacy with personalized k-anonymity: Architecture and algorithms. IEEE Trans. Mobile Comput. 7, 1, 1--18. Google ScholarDigital Library
- Ghinita, G., Kalnis, P., Khoshgozaran, A., Shahabi, C., and Tan, K.-L. 2008. Private queries in location based services: Anonymizers are not necessary. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). Google ScholarDigital Library
- Ghinita, G., Kalnis, P., and Skiadopoulos, S. 2007b. Mobihide: A mobile peer-to-peer system for anonymous location-based queries. In Proceedings of the International Symposium on Advances in Spatial and Temporal Databases (SSTD). Google ScholarDigital Library
- Ghinita, G., Kalnis, P., and Skiadopoulos, S. 2007a. PrivÉ: Anonymous location-based queries in distributed mobile systems. In Proceedings of the International World Wide Web Conference (WWW). Google ScholarDigital Library
- Gruteser, M. and Grunwald, D. 2003. Anonymous usage of location-based services through spatial and temporal cloaking. In Proceedings of the International Conference on Mobile Systems, Applications, and Services (MOBISYS). Google ScholarDigital Library
- Gruteser, M. and Liu, X. 2004. Protecting privacy in continuous location-tracking applications. IEEE Secur. Priv. 2, 2, 28--34. Google ScholarDigital Library
- Gruteser, M., Schelle, G., Jain, A., Han, R., and Grunwald, D. 2003. Privacy-aware location sensor networks. In Proceedings of the Workshop on Hot Topics in Operating Systems (HotOS). Google ScholarDigital Library
- Güting, R. H., de Almeida, V. T., Ansorge, D., Behr, T., Ding, Z., Höse, T., Hoffmann, F., Spiekermann, M., and Telle, U. 2005. Secondo: An extensible DBMS platform for research prototyping and teaching. In Proceedings of the International Conference on Data Engineering (ICDE). Google ScholarDigital Library
- Haas, L. M., Miller, R. J., Niswonger, B., Roth, M. T., Schwarz, P. M., and Wimmers, E. L. 1999. Transforming heterogeneous data with database middleware: Beyond integration. IEEE Data Engin. Bull. 22, 1, 31--36.Google Scholar
- Hadjieleftheriou, M., Kollios, G., Bakalov, P., and Tsotras, V. J. 2005. Complex spatio-temporal pattern queries. In Proceedings of the International Conference on Very Large Data Bases (VLDB). Google ScholarDigital Library
- Hashem, T. and Kulik, L. 2007. Safeguarding location privacy in wireless ad hoc networks. In Proceedings of the International Conference on Ubiquitous Computing (UBICOMP). Google ScholarDigital Library
- Hengartner, U. and Steenkiste, P. 2003. Protecting access to people location information. In Proceedings of the International Conference on Security in Pervasive Computing (SPC).Google Scholar
- Hong, J. I. and Landay, J. A. 2004. An architecture for privacy-sensitive ubiquitous computing. In Proceedings of the International Conference on Mobile Systems, Applications, and Services (MOBISYS). Google ScholarDigital Library
- Hu, H. and Lee, D. L. 2006. Range nearest-neighbor query. IEEE Trans. Knowl. Data Engin. 18, 1, 78--91. Google ScholarDigital Library
- Hu, H., Xu, J., and Lee, D. L. 2005. A generic framework for monitoring continuous spatial queries over moving objects. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). Google ScholarDigital Library
- Iwerks, G. S., Samet, H., and Smith, K. 2003. Continuous k-nearest neighbor queries for continuously moving points with updates. In Proceedings of the International Conference on Very Large Data Bases (VLDB). Google ScholarDigital Library
- Jefferies, N., Mitchell, C. J., and Walker, M. 1995. A proposed architecture for trusted third party services. In Proceedings of the International Conference on Cryptography: Policy and Algorithms. Google ScholarDigital Library
- Jensen, C. S. 2004. Database aspects of location-based services. In Location-Based Services. Morgan Kaufmann, 115--148.Google Scholar
- Kalnis, P., Ghinita, G., Mouratidis, K., and Papadias, D. 2007. Preventing location-based identity inference in anonymous spatial queries. IEEE Trans. Knowl. Data Engin. 19, 12, 1719--1733. Google ScholarDigital Library
- Khoshgozaran, A. and Shahabi, C. 2007. Blind evaluation of nearest neighbor queries using space transformation to preserve location privacy. In Proceedings of the International Symposium on Advances in Spatial and Temporal Databases (SSTD). Google ScholarDigital Library
- Kido, H., Yanagisawa, Y., and Satoh, T. 2005. An anonymous communication technique using dummies for location-based services. In Proceedings of the IEEE International Conference on Pervasive Services (ICPS).Google Scholar
- Kolahdouzan, M. R. and Shahabi, C. 2005. Alternative solutions for continuous k nearest neighbor queries in spatial network databases. GeoInformatica 9, 4, 321--341. Google ScholarDigital Library
- Lazaridis, I., Porkaew, K., and Mehrotra, S. 2002. Dynamic queries over mobile objects. In Proceedings of the International Conference on Extending Database Technology (EDBT). Google ScholarDigital Library
- Li, P.-Y., Peng, W.-C., Wang, T.-W., Ku, W.-S., and Xu, J. 2008. A cloaking algorithm based on spatial networks for location privacy. In Proceedings of the International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing (SUTC). Google ScholarDigital Library
- Lin, B. and Su, J. 2005. Shapes-based trajectory queries for moving objects. In Proceedings of the ACM Symposium on Advances in Geographic Information Systems (GIS). Google ScholarDigital Library
- Mokbel, M. F. and Aref, W. G. 2005. Place: A scalable location-aware database server for spatio-temporal data streams. IEEE Data Engin. Bull. 28, 3, 3--10.Google Scholar
- 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 Data Bases (VLDB). Google ScholarDigital Library
- Mokbel, M. F., Xiong, X., and Aref, W. G. 2004a. Sina: Scalable incremental processing of continuous queries in spatio-temporal databases. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). Google ScholarDigital Library
- Mokbel, M. F., Xiong, X., Aref, W. G., Hambrusch, S., Prabhakar, S., and Hammad, M. 2004b. Place: A query processor for handling real-time spatio-temporal data streams (Demo). In Proceedings of the International Conference on Very Large Data Bases (VLDB). Google ScholarDigital Library
- Mouratidis, K., Papadias, D., and Hadjieleftheriou, M. 2005. Conceptual partitioning: An efficient method for continuous nearest neighbor monitoring. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). Google ScholarDigital Library
- Mouratidis, K., Yiu, M. L., Papadias, D., and Mamoulis, N. 2006. Continuous nearest neighbor monitoring in road networks. In Proceedings of the International Conference on Very Large Data Bases (VLDB). Google ScholarDigital Library
- Papadias, D., Shen, Q., Tao, Y., and Mouratidis, K. 2004. Group nearest neighbor queries. In Proceedings of the International Conference on Data Engineering (ICDE). Google ScholarDigital Library
- Pfitzmann, A. and Kohntopp, M. 2000. Anonymity, unobservability, and pseudonymity—a proposal for terminology. In Proceedings of the Workshop on Design Issues in Anonymity and Unobservability. Google ScholarDigital Library
- Prabhakar, S., Xia, Y., Kalashnikov, D. V., Aref, W. G., and Hambrusch, S. E. 2002. Query indexing and velocity constrained indexing: Scalable techniques for continuous queries on moving objects. IEEE Trans. Comput. 51, 10, 1124--1140. Google ScholarDigital Library
- Samarati, P. 2001. Protecting respondents' identities in microdata release. IEEE Trans. Knowl. Data Engin. 13, 6, 1010--1027. Google ScholarDigital Library
- Smailagic, A. and Kogan, D. 2002. Location sensing and privacy in a context-aware computing environment. IEEE Wireless Commun. 9, 5, 10--17. Google ScholarDigital Library
- Sun, J., Papadias, D., Tao, Y., and Liu, B. 2004. Querying about the past, the present and the future in spatio-temporal databases. In Proceedings of the International Conference on Data Engineering (ICDE). Google ScholarDigital Library
- Sweeney, L. 2002a. Achieving k-anonymity privacy protection using generalization and suppression. Inter. J. Uncert. Fuzz. Knowl.-Based Syst. 10, 5, 571--588. Google ScholarDigital Library
- Sweeney, L. 2002b. k-anonymity: A model for protecting privacy. Inter. J. Uncert. Fuzz. Knowl.-Based Syst. 10, 5, 557--570. Google ScholarDigital Library
- Tao, Y. and Papadias, D. 2005. Historical spatio-temporal aggregation. ACM Trans. Inform. Syst. 23, 1, 61--102. Google ScholarDigital Library
- Tao, Y., Papadias, D., and Shen, Q. 2002. Continuous nearest neighbor search. In Proceedings of the International Conference on Very Large Data Bases (VLDB). Google ScholarDigital Library
- Tao, Y., Sun, J., and Papadias, D. 2003. Analysis of predictive spatio-temporal queries. ACM Trans. Datab. Syst. 28, 4, 295--336. Google ScholarDigital Library
- USAToday. 2002. Authorities: GPS system used to stalk woman. http://www.usatoday.com/tech/news/2002-12-30-gps-stalker_x.htm. December 30.Google Scholar
- Warrior, J., McHenry, E., and McGee, K. 2003. They know where you are. IEEE Spectrum 40, 7, 20--25. Google ScholarDigital Library
- Wolfson, O., Cao, H., Lin, H., Trajcevski, G., Zhang, F., and Rishe, N. 2002. Management of dynamic location information in domino (Demo). In Proceedings of the International Conference on Extending Database Technology (EDBT). Google ScholarDigital Library
- Wolfson, O., Xu, B., and Chamberlain, S. 2000. Location prediction and queries for tracking moving objects. In Proceedings of the International Conference on Data Engineering (ICDE). Google ScholarDigital Library
- Xu, T. and Cai, Y. 2007. Location anonymity in continuous location-based services. In Proceedings of the ACM Symposium on Advances in Geographic Information Systems (GIS). Google ScholarDigital Library
- Xu, T. and Cai, Y. 2008. Exploring historical location data for anonymity preservation in location-based services. In Proceedings of the International Conference of the Computer and Communications Societies (INFOCOM).Google Scholar
- Yiu, M. L., Jensen, C., Huang, X., and Lu, H. 2008. Spacetwist: Managing the trade-offs among location privacy, query performance, and query accuracy in mobile services. In Proceedings of the International Conference on Data Engineering (ICDE). Google ScholarDigital Library
- Zhang, J., Zhu, M., Papadias, D., Tao, Y., and Lee, D. L. 2003. Location-based spatial queries. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). Google ScholarDigital Library
Index Terms
- Casper*: Query processing for location services without compromising privacy
Recommendations
Distortion-based anonymity for continuous queries in location-based mobile services
GIS '09: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information SystemsPrivacy preservation has recently received considerable attention for location-based mobile services. Various location cloaking approaches have been proposed to protect the location privacy of mobile users. However, existing cloaking approaches are ill-...
Privacy-Conscious Location-Based Queries in Mobile Environments
In location-based services, users with location-aware mobile devices are able to make queries about their surroundings anywhere and at any time. While this ubiquitous computing paradigm brings great convenience for information access, it also raises ...
Preserving location privacy without exact locations in mobile services
Privacy preservation has recently received considerable attention in location-based services (LBSs). A large number of location cloaking algorithms have been proposed for protecting the location privacy of mobile users. However, most existing cloaking ...
Comments