search

jasperzhong / read-papers-and-code

My paper/code reading notes in Chinese
43 stars 3 forks source link

Euro Par '16 | GraphIn: An Online High Performance Incremental Graph Processing Framework #301

Closed jasperzhong closed 2 years ago

jasperzhong commented 2 years ago

https://www.researchgate.net/profile/Theodore-Willke/publication/303786170_GraphIn_An_Online_High_Performance_Incremental_Graph_Processing_Framework/links/57521a5d08ae6807fafb769b/GraphIn-An-Online-High-Performance-Incremental-Graph-Processing-Framework.pdf

这是个CCF-C会议

jasperzhong commented 2 years ago

文章一开头的一段话解决了我一部分疑惑.

However, most current graph analytics on such dynamic graphs follow a store-and-static-compute model that involves storing batches of updates to a graph applied at different points in time and then repeatedly running static graph computations on the “snapshots” of the evolving graph. The key assumption made here is that the dynamic graph changes slower than the static processing rate.

当时的GraphLab, PowerGraph, GraphChi, X-Stream都是这么做的. 所以基本都还是静态图的算法. 有的系统会维护snapshot，有的只维护最新的图.

这篇paper提出了动态图的算法，Incremental-Gather-Apply-Scatter (I-GAS). 扫了一眼，主要是为了避免重复对整个图进行重新计算. 但这样incremental计算可能结果不准确.

他们采用了hybrid数据结构: edge list 保存incremental updates, CSR保存static version of the graph. edge list是为了保证fast update而不影响incremental computation，而SCR是为了更快进行计算. 在需要的时候会merge updates到static graph.

其他懒得看了.