Paper Info
Title
Signal/collect: graph algorithms for the (semantic) web
Abstract
The Semantic Web graph is growing at an incredible pace, enabling opportunities to discover new knowledge by interlinking and analyzing previously unconnected data sets. This confronts researchers with a conundrum: Whilst the data is available the programming models that facilitate scalability and the infrastructure to run various algorithms on the graph are missing. Some use MapReduce - a good solution for many problems. However, even some simple iterative graph algorithms do not map nicely to that programming model requiring programmers to shoehorn their problem to the MapReduce model. This paper presents the Signal/Collect programming model for synchronous and asynchronous graph algorithms. We demonstrate that this abstraction can capture the essence of many algorithms on graphs in a concise and elegant way by giving Signal/Collect adaptations of various relevant algorithms. Furthermore, we built and evaluated a prototype Signal/Collect framework that executes algorithms in our programming model. We empirically show that this prototype transparently scales and that guiding computations by scoring as well as asynchronicity can greatly improve the convergence of some example algorithms. We released the framework under the Apache License 2.0 (at http://www.ifi.uzh.ch/ddis/research/sc).
Year
Venue
Keywords
2010
International Semantic Web Conference (1)
semantic web graph,collect programming model,collect framework,simple iterative graph algorithm,asynchronous graph algorithm,use mapreduce,unconnected data set,mapreduce model,programming model,prototype signal,semantic web
Field
DocType
Volume
Data mining,Asynchronous communication,Data set,Programming paradigm,Computer science,Semantic Web,Theoretical computer science,SPARQL,Bulk synchronous parallel,Database,Computation,Scalability
Conference
6496
ISSN
ISBN
Citations 
0302-9743
3-642-17745-X
46
PageRank 
References 
Authors
2.47
11
3
Name
Order
Citations
PageRank
Philip Stutz1472.82
Abraham Bernstein215613.80
William W. Cohen3101781243.74