Yousuf, Muhammad Irfan Kim, Suhyun 2024-01-19T12:01:05Z 2024-01-19T12:01:05Z 2022-06-23 2022-06 2169-3536 https://pubs.kist.re.kr/handle/201004/115141 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. English Institute of Electrical and Electronics Engineers Inc. Pool Compression for Undirected Graphs Article 10.1109/ACCESS.2022.3179505 1 IEEE Access, v.10, pp.58904 - 58912 IEEE Access 10 58904 58912 Y scie scopus 000809391100001 Computer Science, Information Systems Engineering, Electrical & Electronic Telecommunications Computer Science Engineering Telecommunications Article WEB REPRESENTATIONS Graph compression merging adjacency lists node ordering Elias-Gamma encoding