Preserving location privacy without exact locations in mobile services

doi:10.1007/s11704-013-2020-y

Front Comput Sci

0, Vol.

Issue () : 317-340 https://doi.org/10.1007/s11704-013-2020-y

Preserving location privacy without exact locations in mobile services

Xiao PAN¹(

), Xiaofeng MENG²

1. School of Economics and Management, Shijiazhuang Tiedao University, Shijiazhuang 050043, China; 2. School of Information, Renmin University of China, Beijing 100872, China

Download: PDF(1167 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

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 approaches assume that mobile users are trusted. And exact locations are required to protect location privacy, which is exactly the information mobile users want to hide. In this paper, we propose a p-anti-conspiration privacy model to anonymize over semi-honest users. Furthermore, two k^?NNG-based cloaking algorithms, vk^?NNCA and ek^?NNCA, are proposed to protect location privacy without exact locations. The efficiency and effectiveness of the proposed algorithms are validated by a series of carefully designed experiments. The experimental results show that the price paid for location privacy protection without exact locations is small.

Keywords location privacy semi-honest users privacy preservation location-based services

Corresponding Author(s): PAN Xiao,Email:smallpx@gmail.com

Issue Date: 01 June 2013

Cite this article:

Xiao PAN,Xiaofeng MENG. Preserving location privacy without exact locations in mobile services[J]. Front Comput Sci, 0, (): 317-340.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-013-2020-y
https://academic.hep.com.cn/fcs/EN/Y0/V/I/317

1	Schiller J, Voisard A. General aspects of location-based services. In: Location-based Services . 2004, 9-26
2	Dobson J, Fisher P. Geoslavery. IEEE Technology and Society Magazine , 2003, 22(1): 47-52 doi: 10.1109/MTAS.2003.1188276
3	Privacy please! U.S. smartphone app users concerned with privacy. http://blog.nielsen.com/nielsenwire/online_mobile/privacy-please-ussmartphone- app-users-concerned-with-privacy-when-it-comes-tolocation
4	Sweeney L. k-anonymity: a model for protecting privacy. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems , 2002, 10(5): 557-570 doi: 10.1142/S0218488502001648
5	Liu L. From data privacy to location privacy: models and algorithms. In: Proceedings of the 33rd International Conference on Very Large Data Bases . 2007, 1429-1430
6	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 doi: 10.1145/1066116.1189037
7	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
8	Xiao Z, Meng X, Xu J. Quality aware privacy protection for locationbased services. In: Proceedings of the 12th International Conference on Database Systems for Advanced Applications . 2007, 434-446
9	Xu T, Cai Y. Location anonymity in continuous location-based services. In: Proceedings of the 15th annual ACM International Symposium on Advances in Geographic Information Systems . 2007, 39-47
10	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
11	Hu H, Lee D. Range nearest-neighbor query. IEEE Transactions on Knowledge and Data Engineering , 2006, 18(1): 78-91 doi: 10.1109/TKDE.2006.15
12	Ghinita G, Kalnis P, Khoshgozaran A, Shahabi C, Tan K. 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 doi: 10.1145/1376616.1376631
13	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
14	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-380 doi: 10.1145/1242572.1242623
15	Hu H, Xu J. Non-exposure location anonymity. In: Proceedings of the 25th IEEE International Conference on Data Engineering . 2009, 1120-1131
16	Ding C, He X. K-nearest-neighbor consistency in data clustering: incorporating local information into global optimization. In: Proceedings of the 2004 ACM Symposium on Applied Computing . 2004, 584-589 doi: 10.1145/967900.968021
17	Thomas brinkho. network-based generator of moving objects. http://www.fhoow.de/institute/iapg/personen/brinkhoff
18	Athens trucks data. http://www.rtreeportal.org/
19	Zheng Y, Wang L, Zhang R, Xie X, Ma W. Geolife: managing and understanding your past life over maps. In: Proceedings of the 9th International Conference on Mobile Data Management . 2008, 211-212
20	Cheng R, Zhang Y, Bertino E, Prabhakar S. Preserving user location privacy in mobile data management infrastructures. In: Proceedings of the 6th International Conference on Privacy Enhancing Technologies . 2006, 393-412 doi: 10.1007/11957454_23
21	Yiu M, Jensen C, Huang X, Lu H. Spacetwist: managing the trade-offs among location privacy, query performance, and query accuracy in mobile services. In: Proceedings of the IEEE 24th International Conference on Data Engineering . 2008, 366-375
22	Chow C, Mokbel M. Enabling private continuous queries for revealed user locations. In: Proceedings of the 10th International Conference on Advances in Spatial and Temporal Databases . 2007, 258-273 doi: 10.1007/978-3-540-73540-3_15
23	Gkoulalas-Divanis A, Kalnis P, Verykios V. Providing k-anonymity in location based services. ACM SIGKDD Explorations Newsletter , 2010, 12(1): 3-10 doi: 10.1145/1882471.1882473
24	Ghinita G, Kalnis P, Skiadopoulos S. MOBIHIDE: a mobilea peer-topeer system for anonymous location-based queries. In: Proceedings of the 10th International Conference on Advances in Spatial and Temporal Databases . 2007, 221-238 doi: 10.1007/978-3-540-73540-3_13
25	Hashem T, Kulik L. Safeguarding location privacy in wireless ad-hoc networks. In: Proceedings of the 9th International Conference on Ubiquitous Computing . 2007, 372-390
26	Khoshgozaran A, Shahabi C. Blind evaluation of nearest neighbor queries using space transformation to preserve location privacy. In: Proceedings of the 10th International Conference on Advances in Spatial and Temporal Databases . 2007, 239-257 doi: 10.1007/978-3-540-73540-3_14
27	Khoshgozaran A, Shahabi C, Shirani-Mehr H. Location privacy: going beyond k-anonymity, cloaking and anonymizers. Knowledge and Information Systems , 2011, 26(3): 435-465 doi: 10.1007/s10115-010-0286-z
28	Kido H, Yanagisawa Y, Satoh T. Protection of location privacy using dummies for location-based services. In: Proceedings of the 21st International Conference on Data Engineering Workshops . 2005, 1248 doi: 10.1109/ICDE.2005.269
29	Abul O, Bonchi F, Nanni M. Never walk alone: uncertainty for anonymity in moving objects databases. In: Proceedings of the IEEE 24th International Conference on Data Engineering . 2008, 376-385
30	Terrovitis M, Mamoulis N. Privacy preserving in the publication of trajectories. In: Proceedings of the International Conference on Mobile Data Management . 2008, 65-72
31	Yarovoy R, Bonchi F, Lakshmanan L, Wang W. Anonymizing moving objects: how to hide aMOB in a crowd? In: Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology . 2009, 72-83
32	Mohammed N, Fung B, Debbabi M. Walking in the crowd: anonymizing trajectory data for pattern analysis. In: Proceedings of the 18th ACM Conference on Information and Knowledge Management . 2009, 1441-1444 doi: 10.1145/1645953.1646140
33	Becchetti L, Filipponi L, Vitaletti A. Privacy support in people-centric sensing. Journal of Communications , 2012, 7(8): 606-621
34	Huo Z, Meng X. A survey of trajectory privacy-preserving techniques. Chinese Journal of Computers , 2011, 34(10): 1820-1830 doi: 10.3724/SP.J.1016.2011.01820
35	Du WJ. A study of several specific secure two-party computation problems. PhD thesis. Purdue University , 2001
36	Beresford A, Stajano F. Location privacy in pervasive computing. IEEE Pervasive Computing , 2003, 2(1): 46-55 doi: 10.1109/MPRV.2003.1186725
37	Krishnamachari B, Ghinita G, Kalnis P. Privacy-preserving publication of user locations in the proximity of sensitive sites. In: Proceedings of the 20th International Conference on Scientific and Statistical Database Management . 2008, 95-113 doi: 10.1007/978-3-540-69497-7_9
38	Hu H, Xu J, On S, Du J, Ng J. Privacy-aware location data publishing. ACM Transactions on Database Systems , 2010, 35(3): 18-59 doi: 10.1145/1806907.1806910
39	Chow C, Mokbel M. Enabling private continuous queries for revealed user locations. In: Proceedings of the 10th International Conference on Advances in Spatial and Temporal Databases . 2007, 258-273 doi: 10.1007/978-3-540-73540-3_15
40	Garey M, Johnson D, Stockmeyer L. Some simplified np-complete graph problem. Theoretical Computer Science , 1976, (1): 237--67 doi: 10.1016/0304-3975(76)90059-1
41	Chartrand G. Planar graphs and coloring problems. In: Introduction Graph Theory . 1997, 191-209
42	Welsh D, Powell M. An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal , 1967, 10(1): 85-86 doi: 10.1093/comjnl/10.1.85
43	Loukides G, Shao J. An efficient clustering algorithm for kanonymisation. Journal of Computer Science and Technology , 2008, 23(2): 188-202 doi: 10.1007/s11390-008-9121-3

[1]	Min HAO, Beihai TAN, Siming WANG, Rong YU, Ryan Wen LIU, Lisu YU. Exploiting blockchain for dependable services in zero-trust vehicular networks[J]. Front. Comput. Sci., 2024, 18(2): 182805-.
[2]	Long LI, Jianbo HUANG, Liang CHANG, Jian WENG, Jia CHEN, Jingjing LI. DPPS: A novel dual privacy-preserving scheme for enhancing query privacy in continuous location-based services[J]. Front. Comput. Sci., 2023, 17(5): 175814-.
[3]	Hongyang LI, Xinghua LI, Qingfeng CHENG. A fine-grained privacy protection data aggregation scheme for outsourcing smart grid[J]. Front. Comput. Sci., 2023, 17(3): 173806-.
[4]	Bowen ZHAO, Shaohua TANG, Ximeng LIU, Yiming WU. Return just your search: privacy-preserving homoglyph search for arbitrary languages[J]. Front. Comput. Sci., 2022, 16(2): 162801-.
[5]	Huiping LIU, Cheqing JIN, Aoying ZHOU. Popular route planning with travel cost estimation from trajectories[J]. Front. Comput. Sci., 2020, 14(1): 191-207.
[6]	Zhefan ZHONG, Xin LIN, Liang HE, Jing YANG. Answering why-not questions on KNN queries[J]. Front. Comput. Sci., 2019, 13(5): 1062-1071.
[7]	Yubao LIU, Xiuwei CHEN, Zhan LI, Zhijie LI, Raymond Chi-Wing WONG. An efficient method for privacy preserving location queries[J]. Front Comput Sci, 2012, 6(4): 409-420.

Viewed

Full text

Abstract

Cited

Shared

Discussed