Graph-based data structures have drawn great attention in recent years. The large and rapidly growing trend on developing graph processing systems focus 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 of 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. Although various computing platforms and application domains benefit from approximate computing, it has not been thoroughly explored yet in the context of graph processing systems. 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.
翻译:近年来,以图表为基础的数据结构引起了人们的极大注意。在开发图表处理系统方面,大量且迅速增长的趋势主要侧重于通过预处理输入图和修改其布局来改进性能。这些系统通常需要几个小时到几天的时间才能完成高端机器的单一图表的处理,更不用说大部分时间都可能占主导地位的预处理的间接费用。然而,对于大多数图表应用来说,准确的答案并不总是关键,而且对最终结果的粗略估计是充分的。引入近似计算是为了交换计算结果的准确性或仅靠常规技术无法实现的节能。虽然各种计算平台和应用领域都得益于近似计算,但还没有在图形处理系统的范围内进行彻底的探索。在这项工作中,我们设计、执行和评价GapGuess,这是从近似图形理论的领域出发,将其扩展到一个一般的实用的图表处理系统。GreaphGuess基本上是一个具有适应性调整性的近似图形处理技术,可以在任何图形处理系统顶部实施。我们建立了一个基于GreagGuess的脊椎中心处理系统,使用户能够大大降低时间的精确度,而同时显示高度的精确度。我们的实验性研究可以显示。