USENIX ATC '15 - GraphQ: Graph Query Processing with Abstraction Refinement
GraphQ: Graph Query Processing with Abstraction Refinement—Scalable and Programmable Analytics over Very Large Graphs on a Single PC
Kai Wang and Guoqing Xu, University of California, Irvine; Zhendong Su, University of California, Davis; Yu David Liu, SUNY at Binghamton
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 vertices with a certain page rank—can be effectively computed by exploring only a small fraction of the graph, and traversing the complete graph is an overkill. The centerpiece 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 levels. As a result, GraphQ enjoys several distinctive traits unseen in existing graph processing systems: query processing is naturally budget-aware, friendly for out-ofcore processing when “Big Graphs” cannot entirely fit into memory, and endowed with strong correctness properties 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 singlemachine- 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 terminates immediately when a query is answered shows that GraphQ is on average 1.6–13.4x faster due to its ability to process partial graphs.
View the full USENIX ATC '15 program at https://www.usenix.org/conference/atc...
Watch video USENIX ATC '15 - GraphQ: Graph Query Processing with Abstraction Refinement online without registration, duration hours minute second in high quality. This video was added by user USENIX 01 December 2021, don't forget to share it with your friends and acquaintances, it has been viewed on our site 72 once and liked it 0 people.