Edinburgh Research Explorer

Incremental Graph Computations: Doable and Undoable

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Related Edinburgh Organisations

Open Access permissions

Open

Documents

http://dl.acm.org/citation.cfm?id=3035944
Original languageEnglish
Title of host publicationSIGMOD '17 Proceedings of the 2017 ACM International Conference on Management of Data
PublisherACM
Pages155-169
Number of pages15
ISBN (Print)978-1-4503-4197-4
DOIs
Publication statusPublished - 9 May 2017
Event2017 ACM International Conference on Management of Data - Chicago, United States
Duration: 14 May 201719 May 2017
http://sigmod2017.org/

Conference

Conference2017 ACM International Conference on Management of Data
Abbreviated titleSIGMOD/PODS 2017
CountryUnited States
CityChicago
Period14/05/1719/05/17
Internet address

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 real-life graphs, we experimentally verify the effectiveness of our algorithms.

Event

2017 ACM International Conference on Management of Data

14/05/1719/05/17

Chicago, United States

Event: Conference

Download statistics

No data available

ID: 31186612