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

作者:Diego Caro, M. Andrea Rodríguez, Nieves R. Brisaboa, Antonio Fariña

摘要

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.

论文关键词:Multidimensional compact data structure, Compact data structures for temporal graphs, Time-varying graphs, Evolving graphs

论文评审过程:

论文官网地址:https://doi.org/10.1007/s10115-015-0908-6