PCPIR-V:parallel privacy protected algorithms for nearest neighbor query based on Spark

Shi-zhuo DENG; Ji-tao YAO; Bo-tao WANG; Yue-mei CHEN; Ye YUAN; Yan-hui LI; Guo-ren WANG

doi:10.11959/j.issn.2096-109x.2016.00057

您当前的位置：

首页 >

文章列表页 >

PCPIR-V:parallel privacy protected algorithms for nearest neighbor query based on Spark

Papers | 更新时间：2024-06-03

- PCPIR-V:parallel privacy protected algorithms for nearest neighbor query based on Spark
- Chinese Journal of Network and Information Security Vol. 2, Issue 5, Pages: 64-76(2016)
- 作者机构：
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-109x.2016.00057
  CLC： TP309
- Online First：2016-05，
  
  Published：15 May 2016
- 稿件说明：
移动端阅览
Shi-zhuo DENG, Ji-tao YAO, Bo-tao WANG, et al. PCPIR-V:parallel privacy protected algorithms for nearest neighbor query based on Spark[J]. Chinese Journal of Network and Information Security, 2016, 2(5): 64-76.
DOI：

Shi-zhuo DENG, Ji-tao YAO, Bo-tao WANG, et al. PCPIR-V:parallel privacy protected algorithms for nearest neighbor query based on Spark[J]. Chinese Journal of Network and Information Security, 2016, 2(5): 64-76. DOI： 10.11959/j.issn.2096-109x.2016.00057.

摘要

摘要：针对面向大数据的隐私保护查询效率低问题，利用CPIR保护程度高，实现了基于Spark的并行CPIR空间近邻查询隐私保护算法 PCPIR-V，提出了基于 Row 和 Bit 的并行策略，同时提出并实现了基于聚类的PCPIR-V的缓存优化技术。利用均匀分布、高斯分布和真实数据对PCPIR-V进行了测试验证，在40个核心范围内，PCPIR-V具有良好的扩展性，PCPIR-V缓存优化技术计算时间与朴素PCPIR-V时间相比，平均减少了20%。

Abstract

To address the low-efficiency problem for query privacy protection on big data

parallel CPIR-V (PCPIR-V)

which had a high level of privacy protection for nearest neighbor query

was presented and implemented based on spark.Two parallel strategies for PCPIR-V

Row strategy and Bit strategy

were proposed.To avoid redundant multiplications

the repeated products were cached based on a clustering technique while computing CPIR on Spark.According to the evaluation results of PCPIR-V on three datasets

the scalablity of PCPIR-V is good until the number of core is larger than 40.The cost of PCPIR-V with the method of caching partial multiplication results is reduced by 20% averagely.

关键词

Keywords

references

王璐 , 孟小峰 . 位置大数据隐私保护研究综述 [J ] . 软件学报 , 2014 , 25 ( 4 ): 693 - 712 .

WANG L , MENG X F . Position big data privacy protection research review [J ] . Journal of Software , 2014 , 25 ( 4 ): 693 - 712 .

NIU B , LI Q , ZHU X , et al . Achieving k-anonymity in privacy-aware location-based services [C ] // 2014 IEEE Conference on Computer Communications(Infocom) . c2014 : 754 - 762 .

ZHOU C , MA C , YANG S , et al . A location privacy preserving method based on sensitive diversity for LBS [M ] // Network and Parallel Computing . Berlin:Springer , 2014 : 409 - 422 .

CICEK A E , NERGIZ M E , SAYGIN Y . Ensuring location diversity in privacy-preserving spatio-temporal data publishing [J ] . The International Journal on Very Large Data Bases , 2014 , 23 ( 4 ): 609 - 625 .

PAN X , XU J , MENG X . Protecting location privacy against location-dependent attacks in mobile services [J ] . IEEE Transactions on Knowledge and Data Engineering , 2012 , 24 ( 8 ): 1506 - 1519 .

ŠIKŠNYS L , THOMSEN J R , ŠALTENIS S , et al . A location privacy aware friend locator [M ] . Berlin : SpringerPress , 2009 : 405 - 410 .

CHOW C Y , MOKBEL M F , BAO J , et al . Query-aware location anonymization for road networks [J ] . Geoinformatica , 2011 , 15 ( 3 ): 571 - 607 .

CHOW C Y , MOKBEL M F , LEONG H V . On efficient and scalable support of continuous queries in mobile peer-to-peer environments [J ] . IEEE Transactions on Mobile Computing , 2011 , 10 ( 10 ): 1473 - 1487 .

AMBAINIS A . Upper bound on the communication complexity of private information retrieval [M ] . Berlin : SpringerPress , 1997 : 401 - 407 .

KUSHILEVITZ E , OSTROVSKY R . Replication is not needed:single database,computationally-private information retrieval [C ] // Annual Symposium on Foundations of Computer Science . c1997 : 364 - 373 .

GHINITA G , KALNIS P , KHOSHGOZARAN A , et al . Private queries in location based services:anonymizers are not necessary [C ] // The ACM Sigmod International Conference on Management of Data . c2008 : 121 - 132 .

FUNG E , KELLARIS G , PAPADIAS D . Combining differential privacy and pir for efficient strong location privacy [M ] // Advances in Spatial and Temporal Databases . Berlin:Springer , 2015 : 295 - 312 .

YU M , YANG K , WEI L , et al . Practical private information retrieval supporting keyword search in the cloud [C ] // 2014 6th International Conference on Wireless Communications and Signal Processing (WCSP) . c2014 : 1 - 6

张峰 , 倪巍伟 . 基于伪随机数加密的保护位置隐私近邻查询方法 [J ] . 华东师范大学学报(自然科学版) , 2015 ( 5 ): 128 - 142 .

ZHANG F , NI W W . Protect the location privacy neighbor query methods based on the pseudo random number of encryption [J ] . Journal of East China Normal University( Natural Science Edition) , 2015 ( 5 ): 128 - 142 .

SHVACHKO K , KUANG H , RADIA S , et al . The Hadoop distributed file system [C ] // The 26th Symposium on Mass Storage Systems and Technologies (MSST),IEEE . c2010 : 1 - 10 .

ZAHARIA M , CHOWDHURY M , DAS T , et al . Resilient distributed datasets:a fault-tolerant abstraction for in-memory cluster computing [C ] // Usenix Conference on Networked Systems Design and Implementation (NSDI) . c2012 : 141 - 146 .

PAPADOPOULOS S , BAKIRAS S , PAPADIAS D . pCloud:a distributed system for practical PIR [J ] . IEEE Transactions on Dependable and Secure Computing , 2012 , 9 ( 1 ): 115 - 127 .

MAYBERRY T , BLASS E O , CHAN A H . PIRMAP:efficient private information retrieval for MapReduce [M ] // Financial Cryptography and Data Security . Berlin:Springer , 2013 : 371 - 385 .

BLASS E O , DI P R , MOLVA R , et al . PRISM–privacy-preserving search in MapReduce [M ] // Privacy Enhancing Technologies . Berlin:Springer , 2012 : 180 - 200 .

刘金义 , 刘爽 . Voronoi 图应用综述 [J ] . 工程图学学报 , 2004 , 25 ( 2 ): 125 - 132 .

LIU J Y , LIU S . Voronoi diagram application review [J ] . Journal of Engineering Graphics , 2004 , 25 ( 2 ): 125 - 132 .

ASC sequoia benchmark codes [EB/OL ] . https://asc.llnl.gov/sequoia/benchmarks/ https://asc.llnl.gov/sequoia/benchmarks/ .

GMP [EB/OL ] . http://gmplib.org/ http://gmplib.org/ .

Views

120

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Differential privacy protection method for localization of ADS-B message positioning data oriented to LBS

Related Author

YANG Hongyu

ZHANG Hengming

ZHU Youwen

HU Huiling

HU Juncheng

Related Institution

School of Safety Science and Engineering, Civil Aviation University of China

School of Computer Science and Technology, Civil Aviation University of China

College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics

Air Traffic Management Department, Central and Southern Regional Air Traffic Management Bureau of CAAC

School of Computer Science and Technology, Jilin University

⁰