  Graph-based data structures have drawn great attention in recent years. The
large and rapidly growing trend on developing graph processing systems focuses
mostly on improving the performance by preprocessing the input graph and
modifying its layout. These systems usually take several hours to days to
complete processing a single graph on high-end machines, let alone the overhead
of pre-processing which most of the time can be dominant. Yet for most graph
applications the exact answer is not always crucial, and providing a rough
estimate of the final result is adequate. Approximate computing is introduced
to trade off accuracy of results for computation or energy savings that could
not be achieved by conventional techniques alone. In this work, we design,
implement and evaluate GraphGuess, inspired from the domain of approximate
graph theory and extend it to a general, practical graph processing system.
GraphGuess is essentially an approximate graph processing technique with
adaptive correction, which can be implemented on top of any graph processing
system. We build a vertex-centric processing system based on GraphGuess, where
it allows the user to trade off accuracy for better performance. Our
experimental studies show that using GraphGuess can significantly reduce the
processing time for large scale graphs while maintaining high accuracy.

Distributed, Parallel, and Cluster Computing