A Scalable Association-Oriented Streaming Graph Data Partitioning Method

Abstract

The invention discloses an extensible partition method for associated flow graph data, comprising the following steps: (1) preprocessing graph data and converting a node as the node ID; (2) adding each preprocessed side which is existed in an ID form in FIFO and waiting to enter into a sliding window to process; 3) completing the sliding window and calculating the PageRank value of each node according to a mixing approximation PageRank method; (4), tracking the collection of the initial node corresponded by each node in a subgraph, which is composed of sides in the sliding window and obtaining associated value of each node; (5) obtaining a plurality of centroids and corresponding clusters by adopting an affinity propagation clustering algorithm to all nodes in the window; (6) obtaining a plurality of partitioning results which are not of uniform size via associating repeated iteration of a clustering method and storing the partitioning results whose scales are less than threshold value in the sliding window; (7) transmitting the partitioning results whose scales reach or exceed the threshold value to the appropriate storage node by using a data distribution method; and finishing the graph data partitioning. Compared with the prior art, the method provided by the invention has higher partitioning quality.

Description

technical field [0001] The invention belongs to the field of big data processing, and more specifically, relates to a scalable association-oriented stream graph data division method. Background technique [0002] With the advent of the Internet era, the scale of streaming graph data, including social networks and wireless sensor networks, continues to increase. Streaming graph data is continuous and fast, and a single machine is already stretched in terms of storage capacity and processing efficiency. Therefore, it is necessary to consider dividing the streaming graph data into clusters for processing. [0003] For the partition processing of large-scale stream graph data, existing technologies include heuristic partition and parallel hierarchical partition; the heuristic method is to provide an objective function, and then partition around the optimal direction of this function. The difficulty lies in the selection of the objective function The parallel hierarchical divisi...

AI Technical Summary

Problems solved by technology

[0005] Aiming at the above defects or improvement needs of the prior art, the present invention provides a scalable association-oriented flow graph data partition method, the purpose of which is to obtain the PageRank value of the nodes of the flow graph data and sort the nodes accordingly, and The nodes are gradually aggregated according to the node sorting and the degree of association between the nodes, and a reasonable graph partition result is obtained when the aggregation reaches the termination condition, which solves the problem of low quality of the existing stream graph data partition methods

Images