作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 人工智能及识别技术 • 上一篇    下一篇

图数据隐私保护可达性查询算法研究

尹树祥,靳 婷   

  1. (复旦大学计算机科学技术学院智能信息处理重点实验室,上海200433)
  • 收稿日期:2014-04-08 出版日期:2015-02-15 发布日期:2015-02-13
  • 作者简介:尹树祥(1989 - ),男,硕士研究生,主研方向:机器学习,模式识别;靳 婷,博士研究生。

Research on Privacy Protection Reachability Query Algorithm of Graph Data

YIN Shuxiang,JIN Ting   

  1. (Key Lab of Intelligent Information Processing,School of Computer Science,Fudan University,Shanghai 200433,China)
  • Received:2014-04-08 Online:2015-02-15 Published:2015-02-13

摘要: 数据库领域越来越多的数据通过图的结构进行存储,随着图数据规模的快速增长和云计算的兴起,数据拥有者希望将数据外包给具有强大计算能力的服务商为其客户提供查询服务。为解决数据库中的可达性查询问题,提出一种隐私保护的可达性索引和查询方法。对原始的2-hop 索引构建方法进行优化,设计maxISCover 启发式方法,给出根据人工节点添加算法建立pp-2-hop 索引的unifyIS 和unifyLS 算法,并在此基础上,给出基于密文域的优化可达性查询方法。实验结果表明,基于maxISCover 优化方法和unifyIS 算法建立的索引大小相比于基于原始2-hop索引的方法减小1 个~2 个数量级。

关键词: 图数据, 可达性查询, 2-hop 索引, 隐私保护, 人工节点, 查询服务

Abstract: Due to the massive volume of graph data from a wide range of recent applications and unprecedented graph data growth,it is becoming economically appealing for data owners to outsource their data to a powerful Service Provider (SP),such as a cloud computing platform,which provides high computational query services. This paper studies a novel privacy preserving 2-hop index and query algorithm for a fundamental query for graphs namely the reachability query. It optimizes the existing method for building 2-hop index, proposes one optimizing method ( maxISCover ), and two algorithms(unifyIS and unifyLS) to build privacy preserving 2-hop(pp-2-hop) index by adding some surrogate nodes, and raises up an optimized query processing algorithm based on pp-2-hop index. Experimental results show that the index size of this algorithm based on maxISCover optimization method and the unifyIS is reduced by 1 ~2 orders of magnitude, compared with the method based on the original 2-hop.

Key words: graph data, reachability query, 2-hop index, privacy protection, artificial node, query service

中图分类号: