Shrink: Distance preserving graph compression. (September 2017)

• Record Type: Journal Article
• Authors: Sadri, Amin; Salim, Flora D.; Ren, Yongli; Zameni, Masoomeh; Chan, Jeffrey; Sellis, Timos
• Is Part Of: Information systems. Volume 69(2017)
• Page Start: 180
• Page End: 193
• Publication Date: 2017-09
• Subjects: Graph compression -- Graph simplification -- Graph databases -- Shortest paths; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2017.06.001
• Languages: English
• ISSNs: 0306-4379

Abstract

Highlights: We present a graph compression method that preserves distances between the nodes. It is applicable to weighted and unweighted graphs (e.g. road and social network). Distance-based queries can be run without decompression. The user can control a trade-off between accuracy and compression ratio. The complexity is linear in the number of nodes, | V |, when the average degree σ ≪| V |. Abstract: The ever increasing size of graphs makes them difficult to query and store. In this paper, we present Shrink, a compression method that reduces the size of the graph while preserving the distances between the nodes. The compression is based on the iterative merging of the nodes. During each merging, a system of linear equations is solved to define new edge weights in a way that the new weights have the least effect on the distances. Merging nodes continues until the desired size for the compressed graph is reached. The compressed graph, also known as the coarse graph, can be queried without decompression. As the complexity of distance-based queries such as shortest path queries is highly dependent on the size of the graph, Shrink improves the performance in terms of time and storage. Shrink not only provides the length of the shortest path but also identifies the nodes on the path. The approach has been applied to both weighted and unweighted graphs including road network, friendship network, collaboration network, web graph and social network. In the experiment, a road network with more than 2.5 million nodes is reduced to fifth while the average relative error is less than 1%.