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

SHF：小型：大型演化图协同分析的变换

• 批准号: 1524852
• 负责人: Rajiv Gupta
• 金额: $ 40万
• 依托单位: University of California-Riverside
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-07-01 至 2020-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1524852&HistoricalAwards=false
• 关键词: SHF; Small; Transformations; Synergistic; Analysis

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.

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