图数据压缩技术综述

计算机工程与科学

图数据压缩技术综述

李凤英，杨恩乙，董荣胜

（桂林电子科技大学可信软件重点实验室,广西桂林 541004）

收稿日期:2019-04-29 修回日期:2019-08-16 出版日期:2020-01-25 发布日期:2020-01-25
基金资助:
国家自然科学基金（61762024）；广西自然科学基金（2017GXNSFDA198050，2016GXNSFAA380054）；桂林电子科技大学研究生创新创业项目（2019YCXS053）

Summary of graph data compression technologies

LI Feng-ying,YANG En-yi,DONG Rong-sheng

(Guangxi Key Laboratory of Trusted Software,Guilin University of Electronic Technology,Guilin 541004,China)

Received:2019-04-29 Revised:2019-08-16 Online:2020-01-25 Published:2020-01-25

摘要/Abstract

摘要：

应用合适的压缩技术对包含上亿个节点和边的图数据进行紧凑准确的表示和存储是对大规模图数据进行分析和操作的前提。紧凑的图数据表示不仅可以降低图数据的存储空间，而且还可以支持在图数据上的高效操作。从图数据的存储角度出发对图数据管理中关于图数据压缩技术的研究进展进行综述，将重点介绍以下3种压缩技术：基于邻接矩阵的图数据压缩技术、基于邻接表的图数据压缩技术和基于形式化方法的图数据压缩技术，以及相关的代表性算法、适用范围和优缺点。最后对图数据压缩技术的现状和面临的问题进行了总结，并给出了未来图数据压缩技术的发展趋势。

关键词: 邻接矩阵, 邻接表, 形式化方法, 图压缩

Abstract:

Using appropriate compression techniques to compactly and accurately represent and store graph data with hundreds of millions of nodes and edges is a prerequisite for the analysis and operation of large-scale graph data. Compact graph data representation not only reduces the storage space of graph data, but also supports efficient operation on graph data. This paper summarizes the research progress of graph data compression technologies in graph data management from the storage point of graph data, and focuses on the following three compression technologies: compression technology based on adjacency matrix, compression technology based on adjacency list, and compression technology based on formal method. Their related representative algorithms, application scopes, advantages and disadvantages are discussed. Finally, the current situation and problems of graph data compression technologies are summarized, and the development trend of future graph data compression technologies is given.

Key words: adjacency matrix, adjacency list, formal method, graph compression

李凤英，杨恩乙，董荣胜. 图数据压缩技术综述[J]. 计算机工程与科学.

LI Feng-ying,YANG En-yi,DONG Rong-sheng. Summary of graph data compression technologies[J]. Computer Engineering & Science.

[1]	杨春霞, 马文文, 徐奔, 韩煜, . 融合标签信息的分层图注意力网络文本分类模型[J]. 计算机工程与科学, 2023, 45(11): 2018-2026.
[2]	黄怿豪，冯劲草，郑寒月，缪炜恺，蒲戈光. 航空机载嵌入式控制软件需求建模的形式化工程方法[J]. 计算机工程与科学, 2019, 41(06): 1016-1025.
[3]	钟小妹，肖美华，李伟，谌佳，李娅楠. RFID超轻量级认证协议RCIA形式化分析与改进[J]. 计算机工程与科学, 2018, 40(12): 2183-2192.
[4]	陈颖1，刘冬梅1，朱鸿2，兰斌1，何娟娟1. 服务组合的代数规约[J]. 计算机工程与科学, 2018, 40(06): 1075-1083.
[5]	李娅楠，肖美华，李伟，梅映天，钟小妹. 基于事件逻辑的无线Mesh网络认证协议安全性证明[J]. 计算机工程与科学, 2017, 39(12): 2236-2244.
[6]	郭瑞，钱晓东. 基于一阶谓词公式去除商务数据冗余关联规则的研究[J]. 计算机工程与科学, 2017, 39(03): 593-598.
[7]	范林军1，史湘宁2，凌云翔1,3. 时钟有限自动机模型及其演化算法[J]. 计算机工程与科学, 2017, 39(02): 378-384.
[8]	刘欣倩，肖美华，程道雷，梅映天，李伟. 基于事件逻辑的改进NeedhamSchroeder协议安全性证明[J]. J4, 2015, 37(10): 1850-1855.
[9]	李景霞1，吴国栋1，钱俊彦2. 基于邻接矩阵的Web服务组合[J]. J4, 2015, 37(09): 1627-1631.
[10]	程亦涵，黄志球，阚双龙. 一种结合AADL和IMC的系统可靠性建模方法[J]. J4, 2015, 37(08): 1517-1524.
[11]	王大伟,张大方,缪力. 一种自动化模型检测ANSIC程序的实用方法[J]. J4, 2010, 32(4): 79-82.
[12]	匡春临[1] 潘孝铭[1] 蒋胜利[2]. 集成CCS和B语言的形式化方法[J]. J4, 2007, 29(11): 102-104.
[13]	徐凤生. 求最短路径的新算法[J]. J4, 2006, 28(2): 83-85.
[14]	徐凤生李天志. 所有最短路径的求解算法[J]. J4, 2006, 28(12): 83-84.
[15]	郑国磊[1] 朱心雄[1] 许德[2]. CAD系统设计中的形式化方法与功能命题[J]. J4, 2004, 26(5): 77-81.