Not logged in.

Contribution Details

Type Journal Article
Scope Discipline-based scholarship
Title Signal/collect12: processing large graphs in seconds
Organization Unit
  • Philip Stutz
  • Daniel Strebel
  • Abraham Bernstein
Item Subtype Original Work
Refereed Yes
Status Published in final form
  • English
Journal Title Semantic Web
Publisher I O S Press
Geographical Reach international
ISSN 1570-0844
Volume 7
Number 2
Page Range 139 - 166
Date 2016
Abstract Text Both researchers and industry are confronted with the need to process increasingly large amounts of data, much of which has a natural graph representation. Some use MapReduce for scalable processing, but this abstraction is not designed for graphs and has shortcomings when it comes to both iterative and asynchronous processing, which are particularly important for graph algorithms. This paper presents the Signal/Collect programming model for scalable synchronous and asynchronous graph processing. We show that this abstraction can capture the essence of many algorithms on graphs in a concise and elegant way by giving Signal/Collect adaptations of algorithms that solve tasks as varied as clustering, inferencing, ranking, classification, constraint optimisation, and even query processing. Furthermore, we built and evaluated a parallel and distributed framework that executes algorithms in our programming model. We empirically show that our framework efficiently and scalably parallelises and distributes algorithms that are expressed in the programming model. We also show that asynchronicity can speed up execution times. Our framework can compute a PageRank on a large (>1.4 billion vertices, >6.6 billion edges) real-world graph in 112 seconds on eight machines, which is competitive with other graph processing approaches.
Free access at Related URL
Official URL
Related URLs
Digital Object Identifier 10.3233/SW-150176
Other Identification Number merlin-id:12958
PDF File Download from ZORA
Export BibTeX