Optimal Representation of Large-Scale Graph Data Based on Grid Clustering and K2-Tree

Abstract EN

The application of appropriate graph data compression technology to store and manipulate graph data with tens of thousands of nodes and edges is a prerequisite for analyzing large-scale graph data.

The traditional K2-tree representation scheme mechanically partitions the adjacency matrix, which causes the dense interval to be split, resulting in additional storage overhead.

As the size of the graph data increases, the query time of K2-tree continues to increase.

In view of the above problems, we propose a compact representation scheme for graph data based on grid clustering and K2-tree.

Firstly, we divide the adjacency matrix into several grids of the same size.

Then, we continuously filter and merge these grids until grid density satisfies the given density threshold.

Finally, for each large grid that meets the density, K2-tree compact representation is performed.

On this basis, we further give the relevant node neighbor query algorithm.

The experimental results show that compared with the current best K2-BDC algorithm, our scheme can achieve better time/space tradeoff.