Research And Implementation Of Subgraph Clustering Self-Adapting Synchronous And Asynchronous Large Graphs Iterative Processing Technology

With the rapid development of Internet and Internet of things technology,large amounts of data are growing quickly,which leads to raw data increasing the scale."The Big Data Age"became the most powerful summary of current information society.Therefore,the effective management and efficient processing of tremendous information data have become a challenge to the academy and the industry.In data structure graph has complex structure and can express rich semantics,Processing graph data,especially for large-scale graph data,has become an extremely hot area of big data processing.At the memont,large-scale graph processing system exits two kinds of processing mechanism:vertex-centric and graph-centric.Since these two processing mechanisms exist boundedness,both depends on initial partition.But graph partition is a NP-Hard problem,too.Therefore,how to reduce the dependence on graph partitioning and adaptively choosing iterative mechanisms according to actual situation has become an important research topic.In order to solve those problems,we make self-adapting synchronous and asynchronous large graphs iterative processing mechanism and make the system supporting both the vertex centric and graph-centic mechanism.Firstly,add input evaluation mechanism at the completion of each task data loading and after graph partition phase,select the initial handling of the job based on the evaluation results.Define the vertex ownership factor,establish calculation of instable vertex list,as the index of standby migration vertices.Secondly,we design the vertex migration mechanism,set vertex migration of related parameter based on the evaluation of input graph,guarantee that migration of vertex can effectively reduce the communication edge scale,design the global routing table update strategy,ensure migrated vertex can participate in subsequent calculations immediately,make the overall impact of vertex migration as low as possible.Thirdly,we implement the computational framework that supports both vertex-centric and graph centric,design the function of self-Adapting calculation swtich.Finally,we implement the techniques proposed in this thesis in the framework of BC-BSP,a graph processing system and design the API for users.We take a series of experiments.The experiment proved that the mechanism has achieved the desired results.The experimental results conducted with the connection component algorithm prove that our implementation is of high performance and the iteration number of consumption and communication costs have a definite improvement.