Compressed kd-tree for temporal graphs
Compressed kd-tree for temporal graphs
复制标题
时间图的压缩 kd 树
DOI：
--
复制
发表时间：
2016
影响因子：
2.7
通讯作者：
A. Fariña
中科院分区：
文献类型：
--
作者：
Diego Caro;M. A. Rodríguez;N. Brisaboa;A. Fariña
时态图表示随时间沿着变化的顶点和二元关系。本文的工作提出了将时间图表示为4D二进制矩阵中的单元：两个维度表示边缘的极端顶点，两个维度表示边缘存在时的时间间隔。该策略推广了邻接矩阵存储静态图的思想。所提出的结构被称为压缩kd-tree（ckd-tree）是能够处理未聚类的数据与空间的良好利用。ckd树使用与4D二进制矩阵中存储单元的（最坏情况）下限渐近相同的空间，而不考虑任何规律性。将叶子分组到桶中并压缩具有少量子节点的节点的技术显示出在时间和空间上的性能改善。实验评估比较了ckd树与kd树（k2树的d维扩展）和其他最新的基于倒排索引和小波树的压缩数据结构，显示了ckd树对不同类型的时态图的潜在用途。
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) andwith other up-to-date compressed data structures based on inverted indexes andWavelet Trees, showing the potential use of the ckd-tree for different types of temporal graphs.