Paper Info
Title
Queryable Compression on Time-evolving Web and Social Networks with Streaming
Abstract
AbstractTime-evolving web and social network graphs are modeled as a set of pages/individuals (nodes) and their arcs (links/relationships) that change over time. Due to their popularity, they have become increasingly massive in terms of their number of nodes, arcs, and lifetimes. However, these graphs are extremely sparse throughout their lifetimes. For example, it is estimated that Facebook has over a billion vertices, yet at any point in time, it has far less than 0.001% of all possible relationships. The space required to store these large sparse graphs may not fit in most main memories using underlying representations such as a series of adjacency matrices or adjacency lists.We propose building a compressed data structure that has a compressed binary tree corresponding to each row of each adjacency matrix of the time-evolving graph. We do not explicitly construct the adjacency matrix, and our algorithms take the time-evolving arc list representation as input for its construction. Our compressed structure allows for directed and undirected graphs, faster arc and neighborhood queries, as well as the ability for arcs and frames to be added and removed directly from the compressed structure (streaming operations). We use publicly available network data sets such as Flickr, Yahoo!, and Wikipedia in our experiments and show that our new technique performs as well or better than our benchmarks on all datasets in terms of compression size and other vital metrics.
Year
DOI
Venue
2022
10.1145/3495012
ACM Transactions on the Web
Keywords
DocType
Volume
Graph compression, time-evolving, streaming, queries, graphs, binary tree, online social networks, temporal
Journal
16
Issue
ISSN
Citations 
2
1559-1131
0
PageRank 
References 
Authors
0.34
0
5
Name
Order
Citations
PageRank
Michael Nelson100.34
Sridhar Radhakrishnan234143.65
Chandra N. Sekharan310512.77
Amlan Chatterjee400.34
Sudhindra Gopal Krishna500.34