Projects per year
Abstract
The incremental problem for a class Q of graph queries aims to compute, given a query Q 2 Q, graph G, output Q(G) and updates G to G as input, changes O to Q(G) such that Q(GG) = Q(G)O. It is called bounded if its cost can be expressed as a polynomial function in the sizes of Q, G and O. It is to reduce computations on possibly big G to small G and 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 G instead of the entire G; and (b) bounded relative to a batch algorithm T , if the cost is determined by the sizes of 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 reallife graphs, we experimentally verify the effectiveness of our algorithms.
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 G instead of the entire G; and (b) bounded relative to a batch algorithm T , if the cost is determined by the sizes of 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 reallife graphs, we experimentally verify the effectiveness of our algorithms.
Original language  English 

Title of host publication  SIGMOD '17 Proceedings of the 2017 ACM International Conference on Management of Data 
Publisher  ACM 
Pages  155169 
Number of pages  15 
ISBN (Print)  9781450341974 
DOIs  
Publication status  Published  9 May 2017 
Event  2017 ACM International Conference on Management of Data  Chicago, United States Duration: 14 May 2017 → 19 May 2017 http://sigmod2017.org/ 
Conference
Conference  2017 ACM International Conference on Management of Data 

Abbreviated title  SIGMOD/PODS 2017 
Country  United States 
City  Chicago 
Period  14/05/17 → 19/05/17 
Internet address 
Fingerprint Dive into the research topics of 'Incremental Graph Computations: Doable and Undoable'. Together they form a unique fingerprint.
Projects


VADA: Value Added Data Systems: Principles and Architecture
Libkin, L., Buneman, P., Fan, W. & Pieris, A.
1/04/15 → 30/09/20
Project: Research