GPS: a graph processing system
GPS: a graph processing system
复制标题
DOI：
10.1145/2484838.2484843
复制
发表时间：
2013-07
期刊：
影响因子：
--
通讯作者：
S. Salihoglu;J. Widom
中科院分区：
文献类型：
--
作者：
S. Salihoglu;J. Widom
GPS（图形处理系统）是一个完整的开源系统，我们开发了可扩展的，容错的，易于编程的算法在非常大的图形上执行。本文具有描述GPS系统和介绍GPS等分布式图形处理系统中的图划分技术和实验结果的双重作用。GPS类似于Google专有的Pregel系统，具有三个新功能：（1）扩展的API，使全局计算更容易表达，更高效;（2）动态重新分区方案，在计算期间根据消息传递模式将顶点重新分配给不同的工作者;（3）优化，将高度顶点的邻接列表分布在所有计算节点上，以提高性能。除了介绍GPS及其新功能的实现，我们还提出了静态和动态图分区方案的性能影响的实验结果，我们描述了一个高层次的特定于域的编程语言的编译GPS，使复杂的算法容易表达。
GPS (for Graph Processing System) is a complete open-source system we developed for scalable, fault-tolerant, and easy-to-program execution of algorithms on extremely large graphs. This paper serves the dual role of describing the GPS system, and presenting techniques and experimental results for graph partitioning in distributed graph-processing systems like GPS. GPS is similar to Google's proprietary Pregel system, with three new features: (1) an extended API to make global computations more easily expressed and more efficient; (2) a dynamic repartitioning scheme that reassigns vertices to different workers during the computation, based on messaging patterns; and (3) an optimization that distributes adjacency lists of high-degree vertices across all compute nodes to improve performance. In addition to presenting the implementation of GPS and its novel features, we also present experimental results on the performance effects of both static and dynamic graph partitioning schemes, and we describe the compilation of a high-level domain-specific programming language to GPS, enabling easy expression of complex algorithms.