research-article

Casper*: Query processing for location services without compromising privacy

Authors:

Mohamed F. Mokbel,

Walid G. ArefAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 34, Issue 4

Article No.: 24, Pages 1 - 48

https://doi.org/10.1145/1620585.1620591

Published: 14 December 2009 Publication History

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.

References

[1]

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.

[2]

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).

Digital Library

[3]

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).

Digital Library

[4]

Anonymizer. 2008. Anonymous surfing. http://www.anonymizer.com.

[5]

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).

Digital Library

[6]

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).

[7]

Beresford, A. R. and Stajano, F. 2003. Location privacy in pervasive computing. IEEE Pervasive Comput. 2, 1, 46--55.

Digital Library

[8]

Bureau, U. C. 2006. Tiger/line census files http://www.census.gov/geo/www/tiger/.

[9]

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).

[10]

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).

Digital Library

[11]

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).

Digital Library

[12]

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).

Digital Library

[13]

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).

Digital Library

[14]

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.

Digital Library

[15]

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.

Digital Library

[16]

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).

Digital Library

[17]

FoxNews. 2004. Man accused of stalking ex-girlfriend with GPS. http://www.foxnews.com/story/0,2933,131487,00.html. September 4.

[18]

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).

[19]

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).

[20]

Gedik, B. and Liu, L. 2008. Protecting location privacy with personalized k-anonymity: Architecture and algorithms. IEEE Trans. Mobile Comput. 7, 1, 1--18.

Digital Library

[21]

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).

Digital Library

[22]

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).

Digital Library

[23]

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).

Digital Library

[24]

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).

Digital Library

[25]

Gruteser, M. and Liu, X. 2004. Protecting privacy in continuous location-tracking applications. IEEE Secur. Priv. 2, 2, 28--34.

Digital Library

[26]

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).

Digital Library

[27]

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).

Digital Library

[28]

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.

[29]

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).

Digital Library

[30]

Hashem, T. and Kulik, L. 2007. Safeguarding location privacy in wireless ad hoc networks. In Proceedings of the International Conference on Ubiquitous Computing (UBICOMP).

Digital Library

[31]

Hengartner, U. and Steenkiste, P. 2003. Protecting access to people location information. In Proceedings of the International Conference on Security in Pervasive Computing (SPC).

[32]

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).

Digital Library

[33]

Hu, H. and Lee, D. L. 2006. Range nearest-neighbor query. IEEE Trans. Knowl. Data Engin. 18, 1, 78--91.

Digital Library

[34]

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).

Digital Library

[35]

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).

Digital Library

[36]

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.

Digital Library

[37]

Jensen, C. S. 2004. Database aspects of location-based services. In Location-Based Services. Morgan Kaufmann, 115--148.

[38]

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.

Digital Library

[39]

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).

Digital Library

[40]

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).

[41]

Kolahdouzan, M. R. and Shahabi, C. 2005. Alternative solutions for continuous k nearest neighbor queries in spatial network databases. GeoInformatica 9, 4, 321--341.

Digital Library

[42]

Lazaridis, I., Porkaew, K., and Mehrotra, S. 2002. Dynamic queries over mobile objects. In Proceedings of the International Conference on Extending Database Technology (EDBT).

Digital Library

[43]

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).

Digital Library

[44]

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).

Digital Library

[45]

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.

[46]

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).

Digital Library

[47]

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).

Digital Library

[48]

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).

Digital Library

[49]

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).

Digital Library

[50]

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).

Digital Library

[51]

Papadias, D., Shen, Q., Tao, Y., and Mouratidis, K. 2004. Group nearest neighbor queries. In Proceedings of the International Conference on Data Engineering (ICDE).

Digital Library

[52]

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.

Digital Library

[53]

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.

Digital Library

[54]

Samarati, P. 2001. Protecting respondents' identities in microdata release. IEEE Trans. Knowl. Data Engin. 13, 6, 1010--1027.

Digital Library

[55]

Smailagic, A. and Kogan, D. 2002. Location sensing and privacy in a context-aware computing environment. IEEE Wireless Commun. 9, 5, 10--17.

Digital Library

[56]

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).

Digital Library

[57]

Sweeney, L. 2002a. Achieving k-anonymity privacy protection using generalization and suppression. Inter. J. Uncert. Fuzz. Knowl.-Based Syst. 10, 5, 571--588.

Digital Library

[58]

Sweeney, L. 2002b. k-anonymity: A model for protecting privacy. Inter. J. Uncert. Fuzz. Knowl.-Based Syst. 10, 5, 557--570.

Digital Library

[59]

Tao, Y. and Papadias, D. 2005. Historical spatio-temporal aggregation. ACM Trans. Inform. Syst. 23, 1, 61--102.

Digital Library

[60]

Tao, Y., Papadias, D., and Shen, Q. 2002. Continuous nearest neighbor search. In Proceedings of the International Conference on Very Large Data Bases (VLDB).

Digital Library

[61]

Tao, Y., Sun, J., and Papadias, D. 2003. Analysis of predictive spatio-temporal queries. ACM Trans. Datab. Syst. 28, 4, 295--336.

Digital Library

[62]

USAToday. 2002. Authorities: GPS system used to stalk woman. http://www.usatoday.com/tech/news/2002-12-30-gps-stalker_x.htm. December 30.

[63]

Warrior, J., McHenry, E., and McGee, K. 2003. They know where you are. IEEE Spectrum 40, 7, 20--25.

Digital Library

[64]

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).

Digital Library

[65]

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).

Digital Library

[66]

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).

Digital Library

[67]

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).

[68]

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).

Digital Library

[69]

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).

Digital Library

Cited By

Atmaca UBiswas SMaple CPalamidessi C(2024)A Privacy-Preserving Querying Mechanism with High Utility for Electric VehiclesIEEE Open Journal of Vehicular Technology10.1109/OJVT.2024.33603025(262-277)Online publication date: 2024
https://doi.org/10.1109/OJVT.2024.3360302
Lv ZShang KHuo HLiu XPeng YWang XTan Y(2023)RASK: Range Spatial Keyword Queries on Massive Encrypted Geo-Textual DataIEEE Transactions on Services Computing10.1109/TSC.2023.328965416:5(3621-3635)Online publication date: Sep-2023
https://doi.org/10.1109/TSC.2023.3289654
Liu FWang DXu Z(2023)Privacy-Preserving Travel Time Prediction With Uncertainty Using GPS Trace DataIEEE Transactions on Mobile Computing10.1109/TMC.2021.307486522:1(417-428)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TMC.2021.3074865
Show More Cited By

Index Terms

Casper*: Query processing for location services without compromising privacy

Recommendations

Feeling-based location privacy protection for location-based services
CCS '09: Proceedings of the 16th ACM conference on Computer and communications security

Anonymous location information may be correlated with restricted spaces such as home and office for subject re-identification. This makes it a great challenge to provide location privacy protection for users of location-based services. Existing work ...
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 Systems

Privacy 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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems

ACM Transactions on Database Systems Volume 34, Issue 4

December 2009

271 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/1620585

Issue’s Table of Contents

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 December 2009

Accepted: 01 June 2009

Revised: 01 October 2008

Received: 01 September 2007

Published in TODS Volume 34, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

169
Total Citations
View Citations
1,170
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)4

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Atmaca UBiswas SMaple CPalamidessi C(2024)A Privacy-Preserving Querying Mechanism with High Utility for Electric VehiclesIEEE Open Journal of Vehicular Technology10.1109/OJVT.2024.33603025(262-277)Online publication date: 2024
https://doi.org/10.1109/OJVT.2024.3360302
Lv ZShang KHuo HLiu XPeng YWang XTan Y(2023)RASK: Range Spatial Keyword Queries on Massive Encrypted Geo-Textual DataIEEE Transactions on Services Computing10.1109/TSC.2023.328965416:5(3621-3635)Online publication date: Sep-2023
https://doi.org/10.1109/TSC.2023.3289654
Liu FWang DXu Z(2023)Privacy-Preserving Travel Time Prediction With Uncertainty Using GPS Trace DataIEEE Transactions on Mobile Computing10.1109/TMC.2021.307486522:1(417-428)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TMC.2021.3074865
Liu XWang JLiu QXiong XNiu S(2023)Bidirectional location privacy protection scheme for epidemiological investigation based on OTComputers and Security10.1016/j.cose.2023.103453135:COnline publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1016/j.cose.2023.103453
Wang BLiu JDai L(2023)K-Anonymity-Based Privacy-Preserving and Efficient Location-Based Services for Internet of Vehicles Withstand Viterbi AttackProceedings of International Conference on Image, Vision and Intelligent Systems 2022 (ICIVIS 2022)10.1007/978-981-99-0923-0_101(1016-1028)Online publication date: 29-Mar-2023
https://doi.org/10.1007/978-981-99-0923-0_101
Huang QXu XChen HXie L(2022)A Vehicle Trajectory Privacy Preservation Method Based on Caching and Dummy Locations in the Internet of VehiclesSensors10.3390/s2212442322:12(4423)Online publication date: 11-Jun-2022
https://doi.org/10.3390/s22124423
Wazirali R(2022)A Review on Privacy Preservation of Location-Based Services in Internet of ThingsIntelligent Automation & Soft Computing10.32604/iasc.2022.01924331:2(767-779)Online publication date: 2022
https://doi.org/10.32604/iasc.2022.019243
Zhang ZSun XChen SLiang Y(2022)LPPS-AGCWireless Communications & Mobile Computing10.1155/2022/39840992022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/3984099
Deng LZhao YFu ZSun HLiu SZheng KAl Hasan MXiong L(2022)Efficient Trajectory Similarity Computation with Contrastive LearningProceedings of the 31st ACM International Conference on Information & Knowledge Management10.1145/3511808.3557308(365-374)Online publication date: 17-Oct-2022
https://dl.acm.org/doi/10.1145/3511808.3557308
Kai LYiliang HJingjing WKaiyang G(2022)Location Privacy Protection Method Based on Geohash Coding and Pseudo-Random Sequence2022 3rd Information Communication Technologies Conference (ICTC)10.1109/ICTC55111.2022.9778536(178-183)Online publication date: 6-May-2022
https://doi.org/10.1109/ICTC55111.2022.9778536
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents