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

来源：南京信息工程大学学报·自然科学版杂志2017年第5期北京时间：

作者：沈蒙

单位：沈蒙,北京理工大学 计算机学院, 北京, 100081,赵梦蕉,北京理工大学 计算机学院, 北京, 100081,祝烈煌,北京理工大学 计算机学院, 北京, 100081,liehuangz@bit.edu.cn马宝利,北京理工大学 计算机学院, 北京, 100081

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

关键词：近似最短距离;K-mediods聚类;图压缩

基金资助：北京市自然科学基金（4164098）；国家自然科学基金（61602039）；国家重点研发计划（2016YFB0800301）