基于二级索引结构的图压缩算法  

Graph compression algorithm based on a two-level index structure

作　　者：李高超 李犇[3] 卢毓海 刘梦雅[6] 刘燕兵 LI Gaochao;LI Ben;LU Yuhai;LIU Mengya;LIU Yanbing(School of Cyber Security,University of Chinese Academy of Sciences,Beijing 100049,China;Management Center of National Computer Network and Information Security,Beijing 100029,China;Chaoyang Branch of Beijing Public Security Bureau,Beijing 100029,China;Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China;National Engineering Laboratory for Information Security Technologies,Beijing 100093,China;University of Southampton,Southampton SO171BJ,United Kingdom)

机构地区：[1]中国科学院大学网络空间安全学院,北京100049 [2]国家计算机网络与信息安全管理中心,北京100029 [3]北京市公安局朝阳分局,北京100029 [4]中国科学院信息工程研究所,北京100093 [5]信息内容安全技术国家工程实验室,北京100093 [6]英国南安普顿大学

出　　处：《通信学报》2018年第6期109-115,共7页Journal on Communications

基　　金：国家重点研发计划基金资助项目(No.2016YFB0800300);中国科学院信息工程研究所基础前沿基金资助项目(No.Y7Z0351101)~~

摘　　要：目前,各领域对图数据的分析、应用需求日益增加,且对结构复杂、耦合度高的大规模图数据的管理面临着速度低下和空间开销大的双重挑战。面对图数据管理中查询耗时高和空间占比大的难题,提出一种图数据二级索引压缩算法——GCom Idx。该算法利用有序的键值(Key-Value)结构将相关节点和边尽可能地以相邻的方式存储,并为高效的属性查询和邻居查询分别构造二级索引和hash节点索引。此外,为了节省存储空间,GCom Idx算法采用压缩算法来降低图数据磁盘空间占用率。实验结果表明,GCom Idx算法能够有效降低图数据计算的初始化时间和图数据存储的磁盘空间占用,且查询时间小于通用数据库和其他Key-Value存储方案。The demand for the analysis and application of graph data in various fields is increasing day by day. The management of large-scale graph data with complicated structure and high degree of coupling faces two challenges： one is querying speed too slow, the other is space consumption too large. Facing the problems of long query time and large space occupation in graph data management, a two-level index compression algorithm named GCom Idx for graph data was proposed. GCom Idx algorithm used the ordered Key-Value structure to store the associated nodes and edges as closely as possible, and constructed two-level index and hash node index for efficient attribute query and neighbor query. Furthermore, GCom Idx algorithm used a graph data compressed technology to compress the graph data before it directly stored in hard disk, which could effectively reduce the storing space consumption. The experimental results show that GCom Idx algorithm can effectively reduce the initialization time of the graph data calculation and the disk space occupancy of the graph data storing, meanwhile, the query time is less than common graph databases and other Key-Value storage solutions.

关 键 词：二级索引 图压缩 键值结构 属性查询 邻居查询 

分 类 号：TN925[电子电信—通信与信息系统]