错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Ingress: an automated incremental graph processing system

  • Shufeng Gong,
  • Chao Tian,
  • Qiang Yin,
  • Zhengdong Wang,
  • Song Yu,
  • Yanfeng Zhang,
  • Wenyuan Yu,
  • Liang Geng,
  • Chong Fu,
  • Ge Yu,
  • Jingren Zhou

摘要

The graph data keep growing over time in real life. The ever-growing amount of dynamic graph data demands efficient techniques of incremental graph computation. However, incremental graph algorithms are challenging to develop. Existing approaches usually require users to manually design nontrivial incremental operators, or choose different memoization strategies for certain specific types of computation, limiting the usability and generality. In light of these challenges, we propose \(\textsf{Ingress}\) Ingress , an automated system for incremental graph proc essing. \(\textsf{Ingress}\) Ingress is able to deduce the incremental counterpart of a batch vertex-centric algorithm, without the need of redesigned logic or data structures from users. Underlying \(\textsf{Ingress}\) Ingress is an automated incrementalization framework equipped with four different memoization policies, to support all kinds of vertex-centric computations with optimized memory utilization. We identify sufficient conditions for the applicability of these policies. \(\textsf{Ingress}\) Ingress chooses the best-fit policy for a given algorithm automatically by verifying these conditions. In addition to the ease-of-use and generalization, \(\textsf{Ingress}\) Ingress outperforms state-of-the-art incremental graph systems by \(12.14\times \) 12.14 × on average (up to \(49.23\times \) 49.23 × ) in efficiency.