基于位置敏感哈希分割的空间K-匿名共匿算法

计算机科学 ›› 2013, Vol. 40 ›› Issue (8): 115-118.

基于位置敏感哈希分割的空间K-匿名共匿算法

侯士江,张玉江,刘国华

燕山大学信息科学与工程学院秦皇岛066004;燕山大学工业设计系秦皇岛066004;东华大学计算机科学与技术学院上海200051

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受国家自然科学基金(61070032)资助

Spatial K-Anonymity Reciprocal Algorithm Based on Locality-sensitive Hashing Partition

HOU Shi-jiang,ZHANG Yu-jiang and LIU Guo-hua

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 空间K-匿名技术主要用于隐私保护,防止个人信息泄露。目前的主要方法都基于用户-匿名器-基于位置的服务(location based services,LBS)模型。提出了一种基于位置敏感哈希分割的空间K-匿名共匿算法。这种算法在保距性和共匿性方面都可以满足要求,而且算法具有适度的计算复杂度。最后,针对有效性(最小化匿名空间区域)和效率(构建代价)做了实验,证明所提出的算法具有良好的性能。

关键词: 基于位置的服务,空间K-匿名,隐私保护,空间数据库

Abstract: Spatial K-anonymity is an important measure for privacy to prevent the disclosure of personal data．The main methods are based on the model of User-Anonymizer-LBS．This paper proposed a spatial K-anonymity algorithm based on locality-sensitive hashing partition．The algorithm is shown to preserve both locality and reciprocity with moderate computation complexity．Finally,aimed on effectiveness(minimum anonymizing spatial region size)and efficiency(construction cost),the experimental results verify that the proposed method has high performance.

Key words: Location-based services,Spatial K-anonymity,Privacy protection,Spatial databases

侯士江,张玉江,刘国华. 基于位置敏感哈希分割的空间K-匿名共匿算法[J]. 计算机科学, 2013, 40(8): 115-118. https://doi.org/

HOU Shi-jiang,ZHANG Yu-jiang and LIU Guo-hua. Spatial K-Anonymity Reciprocal Algorithm Based on Locality-sensitive Hashing Partition[J]. Computer Science, 2013, 40(8): 115-118. https://doi.org/

参考文献

[1] Agrawal D,Aggarwal C C．On the design and quantification of privacy preserving data mining algorithms [C]∥Proceedings of the Twentieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems．2001:247-255
[2] Ahmadi H,Pham N,Ganti R,et al．Privacy-aware regression modeling of participatory sensing data [C]∥Procee-dings of the 8th ACM Conference on Embedded Networked Sensor Systems．2010:99-112
[3] Sweeney L．K-anonymity:a model for protecting privacy [J]．International Journal of Uncertainty,Fuzziness and Knowledge-Based Systems,2002,10(5):557-570
[4] Mokbel M F,Chow C Y,Aref W G．The new casper:query processing for location services without compromising privacy[C]∥Proceedings of the 32nd International Conference on Very Large Data Bases．2006:763-774
[5] Gruteser M,Grunwald D．Anonymous usage of location- basedservices through spatial and temporal cloaking [C]∥Procee-dings of the 1st International Conference on Mobile Systems,Applications and Services．2003:31-42
[6] Kalnis P,Ghinita G,Mouratidis K,et al.Preventing location-based identity inference in anonymous spatial queries [J]．IEEE Transactions on Knowledge and Data Engineering,2007,19(12):1719-1733
[7] Butz A R．Alternative algorithm for hilbert’s space- filling curve [J]．IEEE Transactions on Computers,1971,C-2(4):424-426
[8] Gedik B,Liu L．Location privacy in mobile systems:a persona-lized anonymization model [C]∥Proceedings of 25th IEEE International Conference on Distributed Computing Systems．2005:620-629
[9] Cheng R,Zhang Y,Bertino E,et al.Preserving user location privacy in mobile data management infrastructures [J]．Privacy Enhancing Technologies,2006,4258:393-412
[10] Khoshgozaran A,Shahabi C．Blind evaluation of nearest neighbor queries using space transformation to preserve location privacy [J]．Advances in Spatial and Temporal Databases,2007,4605:239-257
[11] Hoh B,Gruteser M．Protecting location privacy through pathconfusion [C]∥First International Conference on Security and Privacy for Emerging Areas in Communications Networks．2005:194-205
[12] Ghinita G,Kalnis P,Khoshgozaran A,et al．Private queries inlocation based services:anonymizers are not necessary [C]∥SIGMOD．2008:121-132
[13] Khoshgozaran A,Shahabi C,Shirani-Mehr H．Location privacy:going beyond k-anonymity,cloaking and anonymizers [J]．Knowledge and Information Systems,2011,26(3):435-465
[14] Ghinita G,Kalnis P,Kantarcioglu M,et al．Approximate andexacthybrid algorithms for private nearest-neighbor queries with database protection [J]．GeoInformatica,2011,15(4):699-726
[15] Mouratidis K,Yiu M L．Anonymous query processing in roadnetworks [J]．IEEE Transaction on Knowledge and Data Engineering,2010,22(1):2-15
[16] Chow C Y,Mokbel M F,Liu X．Query-aware location anony-mization for road networks [J]．GeoInformatica,2011,15(3):571-607
[17] Datar M,Indyk P．Locality-sensitive hashing scheme based on p-stable distributions [C]∥Proceedings of the Twentieth Annual Symposium on Computational Geometry．2004:253-262

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed