期刊
IEEE ACCESS
卷 10, 期 -, 页码 58904-58912出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/ACCESS.2022.3179505
关键词
Graph compression; merging adjacency lists; node ordering; Elias-Gamma encoding
资金
- National Research Council of Science & Technology (NST) Grant by the Korea Government [Ministry of Science and ICT (MSIT)] [CRC-20-02-KIST]
- Institute of Information & Communications Technology Planning & Evaluation (IITP) - Korea Government (MSIT) [2021-0-00456]
- National Research Council of Science & Technology (NST), Republic of Korea [CRC-20-02-KIST] Funding Source: Korea Institute of Science & Technology Information (KISTI), National Science & Technology Information Service (NTIS)
This paper presents a new graph compression scheme that achieves better compression ratios by exploiting the similarity and locality of references in a graph. The scheme also provides efficient query methods.
We present a new graph compression scheme that intrinsically exploits the similarity and locality of references in a graph by first ordering the nodes and then merging the contiguous adjacency lists of the graph into blocks to create a pool of nodes. The nodes in the adjacency lists of the graph are encoded by their position in the pool. This simple yet powerful scheme achieves compression ratios better than the previous methods for many datasets tested in this paper and, on average, surpasses all the previous methods. The scheme also provides an easy and efficient access to neighbor queries, e.g., finding the neighbors of a node, and reachability queries, e.g., finding if node u is reachable from node v. We test our scheme on publicly available graphs of different sizes and show a significant improvement in the compression ratio and query access time compared to the previous approaches.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据