Compressed \(\text {k}\mathsf {^d}\text {-tree}\) for temporal graphs

摘要

Temporal graphs represent vertices and binary relations that change along time. The work in this paper proposes to represent temporal graphs as cells in a 4D binary matrix: two dimensions to represent extreme vertices of an edge and two dimensions to represent the temporal interval when the edge exists. This strategy generalizes the idea of the adjacency matrix for storing static graphs. The proposed structure called Compressed \(\text {k}\mathsf {^d}\text {-tree}\) (\(\text {ck}\mathsf {^d}\text {-tree}\)) is capable of dealing with unclustered data with a good use of space. The \(\text {ck}\mathsf {^d}\text {-tree}\) uses asymptotically the same space than the (worst case) lower bound for storing cells in a 4D binary matrix, without considering any regularity. Techniques that group leaves into buckets and compress nodes with few children show to improve the performance in time and space. An experimental evaluation compares the \(\text {ck}\mathsf {^d}\text {-tree}\) with \(\text {k}\mathsf {^d}\text {-tree}\) (the d-dimensional extension of the \(\text {k}\mathsf {^2}\text {-tree}\)) and with other up-to-date compressed data structures based on inverted indexes and \(\mathsf {Wavelet}\text { Tree}\)s, showing the potential use of the \(\text {ck}\mathsf {^d}\text {-tree}\) for different types of temporal graphs.