.png){kind=icon}
返回
Efficient Graph Processing with Invalid Update Filtration
.png){kind=icon}
PRE
AI
DOI：10.1109/TBDATA.2019.2921358.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Most of existing graph processing systems essentially follow pull-based computation model to handle compute-intensive parts of graph iteration for high parallelism. Considering all vertices and edges are processed in each iteration, pull model may suffers from a large number of invalid (vertex/edge) operations that do not contribute to graph convergence, leading to potential performance degradation. In this paper, we have the insight that these invalid operations can be filtered by leveraging a small fraction of critical information. However, most of critical information are often beyond the visibility of active vertices being processed. We present two novel filtration approaches to (cooperatively) identify out-of-visibility critical information with boundary-cut heuristics and speculative prediction for many graph algorithms. We have integrated both approaches and their hybrid solution into three state-of-art graph processing systems (including Ligra, Gemini, and Polymer). Experimental results using a wide variety of graph algorithms on both real-world and synthetic graph datasets show that neither of these approaches can have an absolute win for all graph algorithms. Boundary-cut, predictive, and hybrid approaches can improve the performance by 115.1, 38.1, and 136.6 percent on average.
Keyword:
Convergence
Computational modeling
Big Data
Prediction algorithms
Schedules
Programming
Degradation
Graph processing
pull computation model
invalid update
performance
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
I
IF:
5.7
论文数:
892
被引数:
3.0K
机构
暂无机构信息
引用论文
.png){kind=icon}
分享收藏
查看更多内容