Research On Hierarchical Clustering Sort Based Graph Compression Algorithm

The growing size of graphs makes it challenging to store graph data and perform graph calculations efficiently.Lossless compression is a common way to reduce the size of the graph to fit the memory.The compression method is very important to reduce the cost of large-scale graph computation.However,the existing graph compression technology still has the problems of low compression ratio and high decompression cost.To solve the problem of low compression ratio,the localization of graph data can be mined by sorting graph nodes to improve the compression ratio.To solve the problem of high decompression cost in computation,a new encoding method is chosen to reduce the decompression cost while ensuring the compression effect.Therefore,a new graph compression framework is proposed in this study.Using the IndexedBitArrayEdges encoding method that can support the graph application algorithm to run directly,the space loss function is established,and a sorting algorithm HCSA for edge aggregation degree mining is proposed.Hierarchical clustering is used to sort the nodes with high similarity into the same class.The main idea of HCSA is to cluster the nodes with high similarity in the same category.In order to minimize the space loss function and reduce the storage number of non-empty blocks,a new measurement method using non-common neighbor number as the distance between sets is proposed,which provides an accurate measurement basis for clustering algorithm.The HCSA sorting algorithm proposed in this study can improve the locality of graph data and the compression rate of graph data.At the same time,in the basic operation,the compressed graph data and the sparse matrix storage format have the same time order,so as to ensure the efficiency of the graph application algorithm.The test results show that the compression rate of HCSA algorithm is l0%?40% higher than that of Log(Graph),and 10%?33% higher than that of DNRGC sorting algorithm.The execution efficiency of BFS algorithm and Page Rank algorithm is significantly higher than that of Slash Burn 10%?44%,and only slightly lower than that of Log(Graph)and original graph structure in a few graph data.