摘要： 数据库领域越来越多的数据通过图的结构进行存储,随着图数据规模的快速增长和云计算的兴起,数据拥有者希望将数据外包给具有强大计算能力的服务商为其客户提供查询服务。为解决数据库中的可达性查询问题,提出一种隐私保护的可达性索引和查询方法。对原始的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

中图分类号: 

• TP391