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

Fengying Li, Enyi Yang, Anqiao Ma and Rongsheng Dong

Mathematical Problems in Engineering, 2020, vol. 2020, 1-8

Abstract:

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 K 2 -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 K 2 -tree continues to increase. In view of the above problems, we propose a compact representation scheme for graph data based on grid clustering and K 2 -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, K 2 -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 K 2 -BDC algorithm, our scheme can achieve better time/space tradeoff.

Date: 2020
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2020/2354875.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2020/2354875.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlmpe:2354875

DOI: 10.1155/2020/2354875

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().