Compressed $$ ext {k}mathsf {^d} ext {-tree}$$kd-tree for temporal graphs
Compressed $$ ext {k}mathsf {^d} ext {-tree}$$kd-tree for temporal graphs
复制标题
时间图的压缩 $$ ext {k}mathsf {^d} ext {-tree}$$kd-tree
DOI：
--
复制
发表时间：
2016
影响因子：
2.7
通讯作者：
A. Fariña
中科院分区：
文献类型：
--
作者：
Diego Caro;M. A. Rodríguez;N. Brisaboa;A. 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 $$ ext {k}mathsf {^d} ext {-tree}$$kd-tree ($$ ext {ck}mathsf {^d} ext {-tree}$$ckd-tree) is capable of dealing with unclustered data with a good use of space. The $$ ext {ck}mathsf {^d} ext {-tree}$$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 $$ ext {ck}mathsf {^d} ext {-tree}$$ckd-tree with $$ ext {k}mathsf {^d} ext {-tree}$$kd-tree (the d-dimensional extension of the $$ ext {k}mathsf {^2} ext {-tree}$$k2-tree) and with other up-to-date compressed data structures based on inverted indexes and $$mathsf {Wavelet} ext { Tree}$$WaveletTrees, showing the potential use of the $$ ext {ck}mathsf {^d} ext {-tree}$$ckd-tree for different types of 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 $$ ext {k}mathsf {^d} ext {-tree}$$kd-tree ($$ ext {ck}mathsf {^d} ext {-tree}$$ckd-tree) is capable of dealing with unclustered data with a good use of space. The $$ ext {ck}mathsf {^d} ext {-tree}$$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 $$ ext {ck}mathsf {^d} ext {-tree}$$ckd-tree with $$ ext {k}mathsf {^d} ext {-tree}$$kd-tree (the d-dimensional extension of the $$ ext {k}mathsf {^2} ext {-tree}$$k2-tree) and with other up-to-date compressed data structures based on inverted indexes and $$mathsf {Wavelet} ext { Tree}$$WaveletTrees, showing the potential use of the $$ ext {ck}mathsf {^d} ext {-tree}$$ckd-tree for different types of temporal graphs.