• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学

• 图形与图像 • 上一篇    下一篇

图数据压缩技术综述

李凤英,杨恩乙,董荣胜   

  1. (桂林电子科技大学可信软件重点实验室,广西 桂林 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   

  1. (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

摘要:

应用合适的压缩技术对包含上亿个节点和边的图数据进行紧凑准确的表示和存储是对大规模图数据进行分析和操作的前提。紧凑的图数据表示不仅可以降低图数据的存储空间,而且还可以支持在图数据上的高效操作。从图数据的存储角度出发对图数据管理中关于图数据压缩技术的研究进展进行综述,将重点介绍以下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