KickStarter
Authors:
Open Access
- 4 April 2017
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 237-251
Abstract
Continuous processing of a streaming graph maintains an approximate result of the iterative computation on a recent version of the graph. Upon a user query, the accurate result on the current graph can be quickly computed by feeding the approximate results to the iterative computation --- a form of incremental computation that corrects the (small amount of) error in the approximate result. Despite the effectiveness of this approach in processing growing graphs, it is generally not applicable when edge deletions are present --- existing approximations can lead to either incorrect results (e.g., monotonic computations terminate at an incorrect minima/maxima) or poor performance (e.g., with approximations, convergence takes longer than performing the computation from scratch). This paper presents KickStarter, a runtime technique that can trim the approximate values for a subset of vertices impacted by the deleted edges. The trimmed approximation is both safe and profitable, enabling the computation to produce correct results and converge quickly. KickStarter works for a class of monotonic graph algorithms and can be readily incorporated in any existing streaming graph system. Our experiments with four streaming algorithms on five large graphs demonstrate that trimming not only produces correct results but also accelerates these algorithms by 8.5--23.7x.Keywords
Funding Information
- Amazon Web Services
- National Science Foundation (CCF-1524852, CCF-1318103, CNS-1321179, CCF-1409829, CNS-1613023)
- Office of Naval Research (N00014-14-1-0549, N00014-16-1-2913)
This publication has 36 references indexed in Scilit:
- G ra M2015
- X-Stream2013
- Efficient processing of streaming graphs for evolution-aware clustering2013
- Photon2013
- Streaming graph partitioning for large distributed graphs2012
- Kineograph2012
- Distributed GraphLabProceedings of the VLDB Endowment, 2012
- Retrospective on AuroraThe VLDB Journal, 2004
- Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary BiologyAlgorithmica, 1999
- An On-Line Edge-Deletion ProblemJournal of the ACM, 1981