2018 年 6 月 Journal on Communications June 2018
2018104-1
第 39 卷第 6 期 通 信 学 报 Vol.39
No.6
基于二级索引结构的图压缩算法
李高超
1,2
，李犇
3
，卢毓海
4,5
，刘梦雅
6
，刘燕兵
4,5
（1. 中国科学院大学网络空间安全学院，北京 100049；2. 国家计算机网络与信息安全管理中心，北京 100029；
3. 北京市公安局朝阳分局，北京 100029；4. 中国科学院信息工程研究所，北京 100093；
5. 信息内容安全技术国家工程实验室，北京 100093；6. 英国南安普顿大学，南安普顿 SO171BJ）
摘 要：目前，各领域对图数据的分析、应用需求日益增加，且对结构复杂、耦合度高的大规模图数据的管理面
临着速度低下和空间开销大的双重挑战。面对图数据管理中查询耗时高和空间占比大的难题，提出一种图数据二
级索引压缩算法——GComIdx。该算法利用有序的键值（Key-Value）结构将相关节点和边尽可能地以相邻的方式
存储，并为高效的属性查询和邻居查询分别构造二级索引和 hash 节点索引。此外，为了节省存储空间，GComIdx
算法采用压缩算法来降低图数据磁盘空间占用率。实验结果表明，GComIdx 算法能够有效降低图数据计算的初始
化时间和图数据存储的磁盘空间占用，且查询时间小于通用数据库和其他 Key-Value 存储方案。
关键词：二级索引；图压缩；键值结构；属性查询；邻居查询
中图分类号：TN925
文献标识码：A
doi: 10.11959/j.issn.1000-436x.2018104
Graph compression algorithm based on a two-level index structure
LI Gaochao
1,2
, LI Ben
3
, LU Yuhai
4,5
, LIU Mengya
6
, LIU Yanbing
4,5
1. School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China
2. Management Center of National Computer Network and Information Security, Beijing 100029, China
3. Chaoyang Branch of Beijing Public Security Bureau, Beijing 100029, China
4. Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China
5. National Engineering Laboratory for Information Security Technologies, Beijing 100093, China
6. University of Southampton, Southampton SO171BJ, United Kingdom
Abstract: The demand for the analysis and application of graph data in various fields is increasing day by day. The man-
agement 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 GComIdx for graph data
was proposed. GComIdx 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, GComIdx 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
GComIdx algorithm can effectively reduce the initialization time of the graph data calculation and the disk space occu-
pancy of the graph data storing, meanwhile, the query time is less than common graph databases and other Key-Value
storage solutions.
Key words: two-level index, graph compress, Key-Value structure, attribute query, neighbors query
收稿日期：2017-11-08；修回日期：2018-03-30
通信作者：卢毓海，luyuhai@iie.ac.cn
基金项目：国家重点研发计划基金资助项目（No.2016YFB0800300）；中国科学院信息工程研究所基础前沿基金资助项目
（No.Y7Z0351101）
Foundation Items: The National Key R&D Program of China (No.2016YFB0800300), The Fundamental Theory and Cutting Edge
Technology Research Program of Institute of Information Engineering, CAS (No.Y7Z0351101)
剩余6页未读，继续阅读
资源评论
134678098
- 粉丝: 7
- 资源: 71
最新资源
- 机械臂运动仿真与轨迹分析：基于机器人工具箱的MATLAB正逆运动学工作空间探索与示教应用,机械臂运动仿真与轨迹分析：基于MATLAB机器人工具箱的正逆运动学工作空间探索与示教实践,机械臂运动仿真，机器
- 三相VIENNA整流器仿真研究：T型整流器双闭环PI控制及中点电位平衡控制策略，SPWM调制与高效能表现,三相VIENNA整流器仿真研究：T型整流器双闭环PI控制及中点电位平衡控制策略，SPWM调制与
- win32汇编环境,对话框程序使用跟踪条控件示例二
- apollo自动驾驶10.0-感知-lidar-完整注释版
- 五个带隙基准电路展示：包含曲率补偿与高PSRR特性，基于0.18um工艺的基准源电路设计珍藏版,展示五个带隙基准电路：含曲率补偿与高PSRR的BGR，基于0.18um工艺，完整电路及仿真测试成果，可直
- 双馈风机虚拟惯性与下垂控制在系统一次调频中的MATLAB模型：频率二次跌落研究,“双馈风机虚拟惯性与下垂控制在一次调频中的MATLAB应用：转速回复引发频率二次跌落研究”,双馈风机(永磁同步风机)惯性
- 含UPFC电力系统的潮流计算程序：一键设置，轻松复现lunwen，只需调整UPFC安装与控制参数,含UPFC电力系统的潮流计算程序：快速复现Lunwen的实用工具，只需设置安装位置与控制参数,含UPF
- 30天开发操作系统 第 21 天 -保护操作系统
- 富水断层破碎带隧道工程中流固耦合作用下的突水突泥机理及注浆治理技术研究,流固耦合作用下富水断层破碎带隧道突水突泥机理及注浆治理技术实践,富水断层破碎带隧道突水突泥机理及注浆治理技术研究 隧道开挖卸荷
- Notepad_202502151235_47394.png
- go1.23.5.Windows-amd64安装包
- JimuFlow RPA工具Windows版v1.0.0
- 1-1.学生类定义.cpp
- SVG技术在100MW直驱风电场中的应用：五个链路，每链路等值20台2MW直驱风机，配以10Mvar SVG定电压控制，构建10kV电压等级风电系统,基于SVG技术的100MW直驱风电场等值分析：单
- pycharm安装教程和基本配置
- 一个用 c 语言编写的图书管理系统源码
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
