Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

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 PAN1(), Xiaofeng MENG2
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