PCPIR-V：基于Spark的并行隐私保护近邻查询算法

邓诗卓; 姚继涛; 王波涛; 陈月梅; 袁野; 李艳辉; 王国仁

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

您当前的位置：

首页 >

文章列表页 >

PCPIR-V：基于Spark的并行隐私保护近邻查询算法

学术论文 | 更新时间：2024-06-03

- PCPIR-V：基于Spark的并行隐私保护近邻查询算法
- PCPIR-V:parallel privacy protected algorithms for nearest neighbor query based on Spark
- 网络与信息安全学报 2016年2卷第5期页码：64-76
- 作者机构：
- 作者简介：
  
  [ "邓诗卓（1990-），女，辽宁凌源人，东北大学博士生，主要研究方向为大数据、云计算、位置隐私保护。" ]
  [ "姚继涛（1990-），男，山东泰安人，东北大学硕士生，主要研究方向为大数据、云计算、隐私保护。" ]
  [ "王波涛（1968-），男，山东福山人，东北大学教授、博士生导师，主要研究方向为隐私保护、大数据、云计算、基于位置服务、数据流管理系统、发布/订阅系统、移动数据库。" ]
  [ "陈月梅（1991-），女，湖北大冶人，东北大学硕士生，主要研究方向为隐私保护、大数据、数据管理。" ]
  [ "袁野（1981-），男，辽宁沈阳人，东北大学教授，主要研究方向为云计算、大数据管理、P2P计算。" ]
  [ "李艳辉（1989-），女，黑龙江讷河人，东北大学博士生，主要研究方向为查询处理、隐私保护。" ]
  [ "王国仁（1966-），男，湖北黄冈人，东北大学教授、博士生导师，主要研究方向为XML数据管理、查询处理优化、高维数据索引、分布式数据库、隐私保护。" ]
- 基金信息：
  
  国家自然科学基金资助项目;The National Natural Science Foundation of China(61173030);国家自然科学基金资助项目;The National Natural Science Foundation of China(61272181);国家自然科学基金资助项目;The National Natural Science Foundation of China(61272182);国家自然科学基金资助项目;The National Natural Science Foundation of China(61332014);国家自然科学基金资助项目;The National Natural Science Foundation of China(61370154);国家自然科学基金资助项目;The National Natural Science Foundation of China(61332006)
- DOI：10.11959/j.issn.2096-109x.2016.00057
  中图分类号： TP309
- 网络首发：2016-05，
  
  纸质出版：2016-05-15
- 稿件说明：
移动端阅览
邓诗卓, 姚继涛, 王波涛, 等. PCPIR-V：基于Spark的并行隐私保护近邻查询算法[J]. 网络与信息安全学报, 2016,2(5):64-76.

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.
邓诗卓, 姚继涛, 王波涛, 等. PCPIR-V：基于Spark的并行隐私保护近邻查询算法[J]. 网络与信息安全学报, 2016,2(5):64-76. DOI： 10.11959/j.issn.2096-109x.2016.00057.

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/ .

浏览量

120

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

面向LBS的ADS-B报文定位数据本地化差分隐私保护方法