QQ客服 官方微博 反馈留言

	LogGP: A logbased dynamic graph partitioning method
	Xu, Ning ; Chen, Lei ; Cui, Bin
	2014
英文摘要	With the increasing availability and scale of graph data from Web 2.0, graph partitioning becomes one of efficient preprocessing techniques to balance the computing workload. Since the cost of partitioning the entire graph is strictly prohibitive, there are some recent tentative works towards streaming graph partitioning which can run faster, be easily paralleled, and be incrementally updated. Unfortunately, the experiments show that the running time of each partitioning is still unbalanced due to the variation of workload access pattens during the supersteps. In addition, the onepass streaming partitioning result is not always satisfactory for the algorithms' local view of the graph. In this paper, we present LogGP, a log-based graph partitioning system that records, analyzes and reuses the historical statistical information to refine the partitioning result. LogGP can be used as a middle-ware and deployed to many state-of-the-art paralleled graph processing systems easily. LogGP utilizes the historical partitioning results to generate a hyper-graph and uses a novel hyper-graph streaming partitioning approach to generate a better initial streaming graph partitioning result. During the execution, the system uses running logs to optimize graph partitioning which prevents performance degradation. Moreover, LogGP can dynamically repartition the massive graphs in accordance with the structural changes. Extensive experiments conducted on a moderate size of computing cluster with realworld graph datasets demonstrate the superiority of our approach against the state-of-the-art solutions. ? 2014 VLDB Endowment 21508097/14/10.; EI; 14; 1917-1928; 7
语种	英语
出处	3rd Workshop on Spatio-Temporal Database Management, STDBM 2006, Co-located with the 32nd International Conference on Very Large Data Bases, VLDB 2006
内容类型	其他
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/423785]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Xu, Ning,Chen, Lei,Cui, Bin. LogGP: A logbased dynamic graph partitioning method. 2014-01-01.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。