GraphQ: graph query processing with abstraction refinement: scalable and programmable analytics over very large graphs on a single PC
Kai You Wang, Guoqing Harry Xu, Zhendong Su, Yu David Liu · 2015
This paper introduces GraphQ, a scalable querying framework for very large graphs. GraphQ is built on a key insight that many interesting graph properties — such as finding cliques of a certain size, or finding ver-tices with a certain page rank — can be effectively com-puted by exploring only a small fraction of the graph, and traversing the complete graph is an overkill. The center-piece of our framework is the novel idea of abstraction refinement, where the very large graph is represented as multiple levels of abstractions, and a query is processed through iterative refinement across graph abstraction lev-els. As a result, GraphQ enjoys several distinctive traits unseen in existing graph processing systems: query pro-cessing is naturally budget-aware, friendly for out-of-core processing when “Big Graphs ” cannot entirely fit into memory, and endowed with strong correctness prop-erties on query answers. With GraphQ, a wide range of complex analytical queries over very large graphs can be answered with resources affordable to a single PC, which complies with the recent trend advocating single-machine-based Big Data processing. Experiments show GraphQ can answer queries in graphs 4-6 times bigger than the memory capacity, only in several seconds to minutes. In contrast, GraphChi, a state-of-the-art graph processing system, takes hours to days to compute a whole-graph solution. An additional comparison with a modified version of GraphChi that ter-minates immediately when a query is answered shows that GraphQ is on average 1.6–13.4 × faster due to its ability to process partial graphs. 1