Compressed kd-tree for temporal graphs

Authors: Caro, D.; Rodríguez, M. Andrea; Brisaboa, N. R.; Fariña, A.
Year: 2016 (to appear)
Venue: Knowledge and Information Systems
Link: Compressed kd-tree for temporal graphs
Product of the Action: No

Abstract:
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 kd-tree (ckd-tree) is capable of dealing with unclustered data with a good use of space. The ckd-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 ckd-tree with kd-tree (the d-dimensional extension of the k2-tree) and with other up-to-date compressed data structures based on inverted indexes and Wavelet Trees, showing the potential use of the ckd-tree for different types of temporal graphs.