|
|
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 |
|
|
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
|
|
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
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|