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

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

Abstract

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.

Key words: two-level index, graph compress, Key-Value structure, attribute query, neighbors query

CLC Number:

TN925

Gaochao LI,Ben LI,Yuhai LU,Mengya LIU,Yanbing LIU. Graph compression algorithm based on a two-level index structure[J]. Journal on Communications, 2018, 39(6): 109-115.

Figures/Tables 7

References 15

[1]	陈忱 . 面向 Web 的实体关系查询与分析关键技术研究[D]. 沈阳:东北大学, 2013.
	CHEN C . Study on key techniques of web focused entity relation query processing and analyzing[D]. Shenyang:Northeastern University, 2013.
[2]	程学旗, 靳小龙, 王元卓 ,等. 大数据系统和分析技术综述[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.
[3]	夏黎明 . 云环境下数据关联管理机制的研究及其在铁路行业的应用实现[D]. 北京:北京交通大学, 2011.
	XIA L M . Research for data association management mechanism and its application Implementation in railway[D]. Beijing:Beijing Jiaotong University, 2011.
[4]	周溜溜 . 基于图结构的数据挖掘研究及应用[D]. 南京:南京林业大学, 2013.
	ZHOU L L . Research and application of data mining based on graph structure[D]. Nanjing:Nanjing Forestry University, 2013.
[5]	ANGLES R , GUTIERRZ C . Survey of graph database models[J]. ACM Computing Surveys, 2008,40(1): 178-187.
[6]	于戈, 谷峪, 鲍玉斌 ,等. 云计算环境下的大规模图数据处理技术[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.
[7]	党永兴 . 键值数据库存储引擎设计与实现[D]. 武汉:华中科技大学, 2014.
	DANG Y X . Design and implement of storage engine of key value database[D]. Wuhan:Huazhong University of Science and Technology, 2014.
[8]	张宇, 刘燕兵, 熊刚 ,等. 图数据表示与压缩技术综述[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.
[9]	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.
[10]	吴昌松 . ISCSI 双控制器存储系统缓存设计与实现[D]. 济南:山东大学, 2014.
	WU C S . ISCSI based dual-controller storage system cache design and implementation[D]. Ji’nan:Shandong University, 2014.
[11]	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.
[12]	邹磊 . 图数据库中的子图查询算法研究[D]. 武汉:华中科技大学, 2009.
	ZOU L . Research on sub graph query algorithm in graph database[D]. Wuhan:Huazhong University of Science and Technology, 2009.
[13]	MOMJIAN B . Postgre SQL introduction and concepts[J]. Journal of Conflict Resolution, 2001(3): 353-355.
[14]	郎泓钰, 任永功 . 基于 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.
[15]	WEBBER J , . A programmatic introduction to Neo4j[C]// Conference on Systems,Programming,and Applications:Software for Humanity. 2012: 217-218.

Metrics

Recommended 0

No Suggested Reading articles found!

算法名称	时间消耗/s
PostgreSQL	50 400
SSDB	13 338
Redis	7 956
Neo4j	17 280
GComIdx	8 478

算法名称	磁盘空间占用/GB
PostgreSQL	20.1
SSDB	2.04
Redis	5.05
Neo4j	33.7
GComIdx	1.46

Graph compression algorithm based on a two-level index structure

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 15

Related Articles 15

Metrics

Recommended 0

[1]	Guojun LI, Xu HOU, Changrong YE, Yiping LUO. Wide area cooperative resource allocation algorithm for shortwave communication access network [J]. Journal on Communications, 2023, 44(2): 112-121.
[2]	Rui JIANG, Yue YU, Youyun XU, Xiaoming WANG, Dapeng LI. Improved Kalman filter indoor positioning algorithm based on CHAN [J]. Journal on Communications, 2023, 44(2): 136-147.
[3]	Guojun LI, Cuiling XIANG, Changrong YE, Zunli WANG. Fast link-establishment method of integrated of communication and detection based on short-wave digital channelization [J]. Journal on Communications, 2023, 44(1): 89-102.
[4]	Xumin HUANG, Yang ZHANG, Rong YU, Li JIANG, Hui TIAN, Yuan WU. Stackelberg game based energy optimization for unmanned aerial vehicle assisted wireless-powered Internet of things [J]. Journal on Communications, 2022, 43(12): 146-156.
[5]	Qihui WU,Wei WU. Algorithm design on energy efficiency maximization for UAV-assisted edge computing [J]. Journal on Communications, 2020, 41(10): 15-24.
[6]	Shibing ZHANG,Liuke HAN,Meijuan ZHANG. Power allocation algorithm of full duplex cognitive relay network based on energy harvesting [J]. Journal on Communications, 2020, 41(9): 139-146.
[7]	Li ZHANG,Tian LIAO,Yejun HE. Dual-target WOA spectrum sharing algorithm based on Stackelberg game [J]. Journal on Communications, 2020, 41(9): 170-178.
[8]	Weijia LEI,Minghao DONG. Optimization and realization of SWIPT relay channel transmission rate based on rateless code [J]. Journal on Communications, 2019, 40(5): 98-107.
[9]	Jisheng XU,Fanzi ZENG,Kang LI,Yongfeng LI. Performance analysis of two-way relay cooperation underlay cognitive radio networks based on WIPT [J]. Journal on Communications, 2019, 40(2): 129-136.
[10]	Keming MA,Yajun CHEN,Xin HU,Kaizhi HUANG,Xinsheng JI. Opportunistic secure transmission scheme for simultaneous wireless information and power transfer [J]. Journal on Communications, 2019, 40(2): 70-81.
[11]	Xinwei YAO,Mengna ZHANG,Chaochao WANG,Wanliang WANG. Modeling and analysis of multiple access channel capacity based on hybrid energy storage and energy harvesting [J]. Journal on Communications, 2018, 39(8): 150-159.
[12]	Kai SHE,Yigang HE,Bing LI,Yanqing ZHU. Research on the identification performance of UHF RFID system considering the correlation of cascaded channel [J]. Journal on Communications, 2018, 39(7): 59-67.
[13]	Wei WANG,Liyuan AN,Guoan ZHANG,Shibing ZHANG. Beamforming design for energy-constrained full-duplex two-way relaying system [J]. Journal on Communications, 2018, 39(2): 43-52.
[14]	Xian-zhong TIAN,Min GUO,Jia-cun HE,Gao LIU,Yi-nan ZHU. Multi relay node selection strategy for energy capture collaborative relay network [J]. Journal on Communications, 2017, 38(Z2): 1-7.
[15]	Zhen-wei XIE,Qi ZHU. Power allocation algorithm for cognitive radio energy harvesting networks based on energy cooperation [J]. Journal on Communications, 2017, 38(9): 176-184.