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

李高超; 李犇; 卢毓海; 刘梦雅; 刘燕兵

doi:10.11959/j.issn.1000-436x.2018104

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2024-06-05

- 基于二级索引结构的图压缩算法
- Graph compression algorithm based on a two-level index structure
- 通信学报 2018年39卷第6期页码：109-115
- 作者机构：
  
  1. 中国科学院大学网络空间安全学院，北京 100049
  2. 国家计算机网络与信息安全管理中心，北京 100029
  3. 北京市公安局朝阳分局，北京 100029
  4. 中国科学院信息工程研究所，北京 100093
  5. 信息内容安全技术国家工程实验室，北京 100093
  6. 英国南安普顿大学，南安普顿SO171BJ
- 作者简介：
  
  [ "李高超（1985-），男，北京人，中国科学院大学博士生，主要研究方向为计算机软件、网络安全、下一代网络、SDN技术等。" ]
  [ "李犇（1987-），男，山东济宁人，北京市公安局朝阳分局副主任科员，主要研究方向图数据库管理技术。" ]
  [ "卢毓海（1987-），男，江西赣州人，中国科学院信息工程研究所助理研究员、博士生，主要研究方向为模式串匹配与信息过滤。" ]
  [ "刘梦雅（1991-），女，河北石家庄人，英国南安普顿大学博士生，主要研究方向为关联数据、数据整合、数据市场等。" ]
  [ "刘燕兵（1981-），男，湖北麻城人，博士，中国科学院信息工程研究所副研究员，主要研究方向为模式串匹配与信息过滤、图数据分析与挖掘等。" ]
- 基金信息：
  
  国家重点研发计划基金资助项目(2016YFB0800300);中国科学院信息工程研究所基础前沿基金资助项目(Y7Z0351101)
- DOI：10.11959/j.issn.1000-436x.2018104
  中图分类号： TN925
- 网络出版日期：2018-06，
  
  纸质出版日期：2018-06-25
- 稿件说明：
移动端阅览
李高超, 李犇, 卢毓海, 等. 基于二级索引结构的图压缩算法[J]. 通信学报, 2018,39(6):109-115.

Gaochao LI, Ben LI, Yuhai LU, et al. Graph compression algorithm based on a two-level index structure[J]. Journal on communications, 2018, 39(6): 109-115.
李高超, 李犇, 卢毓海, 等. 基于二级索引结构的图压缩算法[J]. 通信学报, 2018,39(6):109-115. DOI： 10.11959/j.issn.1000-436x.2018104.

Gaochao LI, Ben LI, Yuhai LU, et al. Graph compression algorithm based on a two-level index structure[J]. Journal on communications, 2018, 39(6): 109-115. DOI： 10.11959/j.issn.1000-436x.2018104.

摘要

目前，各领域对图数据的分析、应用需求日益增加，且对结构复杂、耦合度高的大规模图数据的管理面临着速度低下和空间开销大的双重挑战。面对图数据管理中查询耗时高和空间占比大的难题，提出一种图数据二级索引压缩算法——GComIdx。该算法利用有序的键值（Key-Value）结构将相关节点和边尽可能地以相邻的方式存储，并为高效的属性查询和邻居查询分别构造二级索引和hash节点索引。此外，为了节省存储空间，GComIdx算法采用压缩算法来降低图数据磁盘空间占用率。实验结果表明，GComIdx算法能够有效降低图数据计算的初始化时间和图数据存储的磁盘空间占用，且查询时间小于通用数据库和其他Key-Value存储方案。

Abstract

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 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 occupancy of the graph data storing

meanwhile

the query time is less than common graph databases and other Key-Value storage solutions.

关键词

Keywords

references

陈忱 . 面向 Web 的实体关系查询与分析关键技术研究 [D ] . 沈阳:东北大学 , 2013 .

CHEN C . Study on key techniques of web focused entity relation query processing and analyzing [D ] . Shenyang:Northeastern University , 2013 .

程学旗 , 靳小龙 , 王元卓 , 等 . 大数据系统和分析技术综述 [J ] . 软件学报 , 2014 , 25 ( 9 ): 1889 - 1908 .

CHENG X Q , JIN X L , WANG Y Z , et al . Survey on big data system and analytic technology [J ] . Journal of Software , 2014 , 25 ( 9 ): 1889 - 1908 .

夏黎明 . 云环境下数据关联管理机制的研究及其在铁路行业的应用实现 [D ] . 北京:北京交通大学 , 2011 .

XIA L M . Research for data association management mechanism and its application Implementation in railway [D ] . Beijing:Beijing Jiaotong University , 2011 .

周溜溜 . 基于图结构的数据挖掘研究及应用 [D ] . 南京:南京林业大学 , 2013 .

ZHOU L L . Research and application of data mining based on graph structure [D ] . Nanjing:Nanjing Forestry University , 2013 .

ANGLES R , GUTIERRZ C . Survey of graph database models [J ] . ACM Computing Surveys , 2008 , 40 ( 1 ): 178 - 187 .

于戈 , 谷峪 , 鲍玉斌 , 等 . 云计算环境下的大规模图数据处理技术 [J ] . 计算机学报 , 2011 , 34 ( 10 ): 1753 - 1767 .

YU G , GU Y , BAO Y B , et al . Large scale graph data processing on cloud computing environments [J ] . Chinese Journal of Computers , 2011 , 34 ( 10 ): 1753 - 1767 .

党永兴 . 键值数据库存储引擎设计与实现 [D ] . 武汉:华中科技大学 , 2014 .

DANG Y X . Design and implement of storage engine of key value database [D ] . Wuhan:Huazhong University of Science and Technology , 2014 .

张宇 , 刘燕兵 , 熊刚 , 等 . 图数据表示与压缩技术综述 [J ] . 软件学报 , 2014 , 25 ( 9 ): 1937 - 1952 .

ZHANG Y , LIU Y B , XIONG G , et al . Survey on succinct representation of graph data [J ] . Journal of Software , 2014 , 25 ( 9 ): 1937 - 1952 .

ZHANG Y , XIONG G , LIU Y , et al . Delta-K2-tree for compact representation of Web graphs [C ] // Asia-Pacific Web Conference . 2014 : 270 - 281 .

吴昌松 . ISCSI 双控制器存储系统缓存设计与实现 [D ] . 济南:山东大学 , 2014 .

WU C S . ISCSI based dual-controller storage system cache design and implementation [D ] . Ji’nan:Shandong University , 2014 .

GONZALEZ J E , LOW Y , GU H , et al . PowerGraph:distributed graph-parallel computation on natural graphs [C ] // Usenix Conference on Operating Systems Design and Implementation . 2012 : 17 - 30 .

邹磊 . 图数据库中的子图查询算法研究 [D ] . 武汉:华中科技大学 , 2009 .

ZOU L . Research on sub graph query algorithm in graph database [D ] . Wuhan:Huazhong University of Science and Technology , 2009 .

MOMJIAN B . Postgre SQL introduction and concepts [J ] . Journal of Conflict Resolution , 2001 ( 3 ): 353 - 355 .

郎泓钰 , 任永功 . 基于 Redis 内存数据库的快速查找算法 [J ] . 计算机应用与软件 , 2016 , 33 ( 5 ): 40 - 43 .

LANG H Y , REN Y G . A fast search algorithm based on Redis memory database [J ] . Computer Applications and Software , 2016 , 33 ( 5 ): 40 - 43 .

WEBBER J , . A programmatic introduction to Neo4j [C ] // Conference on Systems,Programming,and Applications:Software for Humanity . 2012 : 217 - 218 .

浏览量

908

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据