All Publications

Succinct Preferential Attachment Graphs

In this paper, we show that a simple degree-entropy based compression algorithm is asymptotically instance-optimal for the class of preferential attachment graphs, and can be used as an instance-optimal compressed data structure.

To support queries on the graph, such as adjacency, degree, and neighborhood queries (all in logarithmic time), we store its adjacency list as an entropy-compressed wavelet tree. For unlabeled graphs, we first remove a carefully chosen spanning tree, which is stored as a succinct tree and gives vertices new labels, thus reducing the overall space almost by $\lg n$ bits per vertex.

our data structure for unlabeled PA graphs
Our data structure for unlabeled preferential-attachment graphs. Each vertex originally has outdegree $M=3$. One of these edges is stored within $T$, the others explicitly in the wavelet tree for $A'$.