SHF: Small: Transformations for Synergistic Analysis of Large Evolving Graphs

随着图形分析的流行，图形处理的重要性也与日俱增。真实世界图的一个重要特征是它们在不断演变(例如，社交网络、模拟疾病传播的网络等)。对不断演变的图形进行图形分析需要对在不同时间点拍摄的图形的快照进行重复分析，以观察感兴趣的特征如何随时间变化。对于具有数百亿条边的大型现实世界图，演化图分析是高度计算和内存密集型的。通过开发重组计算和数据的转换，正在考虑在现代计算平台上快速发展的图形分析技术。许多学生正在接受这一重要领域的培训和教育。图形分析可以从现代并行机上可用的核心和存储空间中受益匪浅。然而，由于图计算中并行性的不规则性和数据局部性的缺乏，有效地利用资源仍然是一个巨大的挑战。这项工作利用两个关键特征，重叠工作集和计算值稳定性，来开发加速图形分析的技术。正在考虑的技术包括：优化磁盘上大图形的读和写，优化集群上的节点间通信，以及优化对进化图的多个版本的计算。这些优化被用来极大地提高多个流行的图形处理系统的性能。还计划公开传播这些软件改进。

The importance of graph processing has grown with the popularity of graph analytics. An important feature of real-world graphs is that they are constantly evolving (e.g., social networks, networks modeling spreading of a disease etc.). Graph analytics over an evolving graph entails repeating analysis over snapshots of a graph taken at different points in time to observe how features of interest change over time. For large real-world graphs with tens of billions of edges, evolving graph analysis is both highly compute- and memory-intensive. By developing transformations that reorganize the computation and data, techniques for rapid evolving graph analytics on modern computing platforms are being considered. Many students are being trained and educated in this important field.Graph analysis can greatly benefit from cores and storage available on modern parallel machines. However, effectively exploiting the resources remains an enormous challenge due to irregular nature of parallelism and lack of data locality in graph computations. This work is leveraging two key characteristics, overlapping working sets and computed value stability, to develop techniques for speeding up graph analytics. The techniques being considered include: optimization of reading and writing of large graphs on disk, optimizing inter-node communication on a cluster, and optimizing computation over multiple versions of an evolving graph. These optimizations are being used to greatly enhance the performance of multiple popular graph processing systems. Public dissemination of these software enhancements are also planned.