3.8 Proceedings Paper

Incremental Graph Computations: Doable and Undoable

出版社

ASSOC COMPUTING MACHINERY
DOI: 10.1145/3035918.3035944

关键词

incremental computation; graph data management; query optimization

资金

  1. ERC [652976]
  2. 973 Program [2014CB340302]
  3. NSFC [61602023, 61133002, 61421003]
  4. EPSRC [EP/M025268/1]
  5. Shenzhen Peacock Program [1105100030834361]
  6. Guangdong Innovative Research Team Program [2011D005]
  7. Foundation for Innovative Research Groups of NSFC
  8. Beijing Advanced Innovation Center for Big Data and Brain Computing
  9. EPSRC [EP/M025268/1] Funding Source: UKRI

向作者/读者索取更多资源

The incremental problem for a class Q of graph queries aims to compute, given a query Q is an element of Q, graph G, output Q(G) and updates Delta G to G as input, changes Delta O to Q(G) such that Q(G circle plus Delta G) = Q(G)circle plus Delta O. It is called bounded if its cost can be expressed as a polynomial function in the sizes of Q, Delta G and Delta O. It is to reduce computations on possibly big G to small Delta G and Delta O. No matter how desirable, however, our first results are negative: for common graph queries such as graph traversal, connectivity, keyword search and pattern matching, their incremental problems are unbounded. In light of the negative results, we propose two characterizations for the effectiveness of incremental computation: (a) localizable, if its cost is decided by small neighbors of nodes in Delta G instead of the entire G; and (b) bounded relative to a batch algorithm T, if the cost is determined by the sizes of Delta G and changes to the affected area that is necessarily checked by T. We show that the incremental computations above are either localizable or relatively bounded, by providing corresponding incremental algorithms. That is, we can either reduce the incremental computations on big graphs to small data, or incrementalize batch algorithms by minimizing unnecessary recomputation. Using real-life graphs, we experimentally verify the effectiveness of our algorithms.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

3.8
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据