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

Computer Engineering & Science

Previous Articles     Next Articles

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

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