NDLI: KickStarter:Fast and Accurate Computations on Streaming Graphs via Trimmed Approximations (SIGP, Vol. 52, Issue. 4)

Content Provider	ACM Digital Library
Author	Gupta, Rajiv Vora, Keval Xu, Guoqing
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.
Starting Page	237
Ending Page	251
Page Count	15
File Format	PDF
ISSN	03621340 15581160
DOI	10.1145/3093336.3037748
Journal	ACM SIGPLAN Notices (SIGP)
Volume Number	52
Issue Number	4
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1983-05-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Graph processing Value dependence Streaming graphs
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

KickStarter:Fast and Accurate Computations on Streaming Graphs via Trimmed Approximations (CARN, Vol. 45, Issue. 1)

KickStarter:Fast and Accurate Computations on Streaming Graphs via Trimmed Approximations (OPSR, Vol. 51, Issue. 2)

KickStarter: Fast and Accurate Computations on Streaming Graphs via Trimmed Approximations

CoRAL:Confined Recovery in Distributed Asynchronous Graph Processing (SIGP, Vol. 52, Issue. 4)

Interprocedural slicing using dependence graphs (SIGP, Vol. 39, Issue. 4)

Kinetic Dependence Graphs (SIGP, Vol. 50, Issue. 4)

AMNESIAC:Amnesic Automatic Computer (SIGP, Vol. 52, Issue. 4)

Interprocedural slicing using dependence graphs (SIGP, Vol. 23, Issue. 7)

Analyzing Behavior Specialized Acceleration (SIGP, Vol. 51, Issue. 4)

KickStarter:Fast and Accurate Computations on Streaming Graphs via Trimmed Approximations (SIGP, Vol. 52, Issue. 4)

Similar Documents

KickStarter:Fast and Accurate Computations on Streaming Graphs via Trimmed Approximations (CARN, Vol. 45, Issue. 1)

KickStarter:Fast and Accurate Computations on Streaming Graphs via Trimmed Approximations (OPSR, Vol. 51, Issue. 2)

KickStarter: Fast and Accurate Computations on Streaming Graphs via Trimmed Approximations

CoRAL:Confined Recovery in Distributed Asynchronous Graph Processing (SIGP, Vol. 52, Issue. 4)

Interprocedural slicing using dependence graphs (SIGP, Vol. 39, Issue. 4)

Kinetic Dependence Graphs (SIGP, Vol. 50, Issue. 4)

AMNESIAC:Amnesic Automatic Computer (SIGP, Vol. 52, Issue. 4)

Interprocedural slicing using dependence graphs (SIGP, Vol. 23, Issue. 7)

Analyzing Behavior Specialized Acceleration (SIGP, Vol. 51, Issue. 4)

KickStarter:Fast and Accurate Computations on Streaming Graphs via Trimmed Approximations (SIGP, Vol. 52, Issue. 4)