一种大规模图数据的压缩存储方法

摘要

本发明公开了一种大规模图数据的压缩存储方法，包括：（1）将原始图数据以行为单位用二进制邻接矩阵M存储；（2）根据邻接矩阵M中每行的偏移值建立散列索引；（3）将邻接矩阵M中每行中的起点按照出度进行升序排序；（4）记录入度为0的节点记为根节点，将根节点按照出度进行降序排序，记为根节点序列；（5）对于根节点序列中的每个节点，以根节点为开始节点，按深度优先策略依次分配ID；（6）遍历邻接矩阵M，将矩阵按照新分配的ID进行转换，以边序列格式存储；（7）对边序列格式数据进行排序；（8）将边序列格式数据按行进行压缩存储。本发明需要的数据存储空间小，随机读取次数少且线程并行度高。

主权项

一种大规模图数据的压缩存储方法，包括以下步骤：(1)将邻接矩阵格式的原始图数据进行处理，以行为单位用二进制邻接矩阵形式存储，邻接矩阵设为变量M，记录每个节点的出度；(2)根据邻接矩阵M中每行的偏移值建立散列索引HashIndex，其中每一行存储信息为起点、终点数目和起点对应的终点序列；(3)遍历邻接矩阵M，将邻接矩阵M中按照每行中起点的出度进行升序排序；(4)遍历图中结点，记录入度为0的节点记为根节点，将根节点按照出度进行降序排序，记为根节点序列rootList；(5)对于根节点序列中的每个节点，以根节点为开始节点，按深度优先策略依次分配ID；(6)遍历邻接矩阵M，将矩阵按照新分配的ID进行转换，以边序列格式(Edge List Format)存储；(7)对边序列格式数据进行排序，排序策略为终点优先起点其次，排序方式为并行多路归并的外部排序；(8)将边序列格式数据按行进行压缩存储。