支持近似最短距离查询的高效图加密机制

Efficient graph encryption mechanism for approximate shortest distance search based on cloud

近似最短距离查询是图检索的基本模式.为了保护外包数据安全,通常对图数据进行加密.已有加密方案使用两跳覆盖模型构建加密图索引,导致索引结构复杂,降低了查询效率.本文提出了一种基于图压缩的加密机制,可以提高图的检索效率,并且支持加密图最短路径查询.该机制使用K-mediods聚类使得图中的节点按照距离分成K个簇,每个簇内的节点使用其中心节点代理,当查询2个点间最短距离时,对于相同簇内的点直接查询,对于簇间的点使用代理节点查询距离.实验结果表明该机制有效地减少了查询时间,提高了查询效率,且查询结果误差度在可接受范围内.

Approximate shortest distance query is the basic pattern of graph search.The graph data is usually en-crypted in order to protect the security of the outsourced data.The existing encryption schemes use the two-hop labe-ling model to construct the encryption index,which leads to the high-complexity of index structure and the reductionof query efficiency.This paper proposed an algorithm based on graph compression,which can improve the efficiencyof the graph query and support the approximate shortest distance query of encrypted graph.The algorithm usesK-me-diods clustering so that the nodes in the graph are divided intoKclusters according to the distance.The nodes ineach cluster use their central node as agent node.When querying the shortest distance between two points,the pointin different clusters uses the proxy node to query distance.The experimental results show that the algorithm can ef-fectively reduce the query time and improve the query efficiency,and the deviation rate of the query result is accept-able.