Auto-approximation of graph computing

Z Shang, JX Yu - Proceedings of the VLDB Endowment, 2014 - dl.acm.org
Proceedings of the VLDB Endowment, 2014dl.acm.org
In the big data era, graph computing is one of the challenging issues because there are
numerous large graph datasets emerging from real applications. A question is: do we need
to know the final exact answer for a large graph? When it is impossible to know the exact
answer in a limited time, is it possible to approximate the final answer in an automatic and
systematic way without having to designing new approximate algorithms? The main idea
behind the question is: it is more important to find out something meaningful quick from a …
In the big data era, graph computing is one of the challenging issues because there are numerous large graph datasets emerging from real applications. A question is: do we need to know the final exact answer for a large graph? When it is impossible to know the exact answer in a limited time, is it possible to approximate the final answer in an automatic and systematic way without having to designing new approximate algorithms? The main idea behind the question is: it is more important to find out something meaningful quick from a large graph, and we should focus on finding a way of making use of large graphs instead of spending time on designing approximate algorithms. In this paper, we give an innovative approach which automatically and systematically synthesizes a program to approximate the original program. We show that we can give users some answers with reasonable accuracy and high efficiency for a wide spectrum of graph algorithms, without having to know the details of graph algorithms. We have conducted extensive experimental studies using many graph algorithms that are supported in the existing graph systems and large real graphs. Our extensive experimental results reveal that our automatically approximating approach is highly feasible.
ACM Digital Library