GRAPHONE: A Data Store for Real-time Analytics on Evolving Graphs

被引:37
作者
Kumar, Pradeep [1 ]
Huang, H. Howie [2 ]
机构
[1] William & Mary, Dept Comp Sci, 251 Jamestown Rd, Williamsburg, VA 23185 USA
[2] George Washington Univ, Dept Elect & Comp Engn, 800 22nd St NW, Washington, DC 20052 USA
基金
美国国家科学基金会;
关键词
Graph systems; graph data management; unified graph data store; batch analytics; stream analytics; INTERNET; ALGORITHM;
D O I
10.1145/3364180
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
There is a growing need to perform a diverse set of real-time analytics (batch and stream analytics) on evolving graphs to deliver the values of big data to users. The key requirement from such applications is to have a data store to support their diverse data access efficiently, while concurrently ingesting fine-grained updates at a high velocity. Unfortunately, current graph systems, either graph databases or analytics engines, are not designed to achieve high performance for both operations; rather, they excel in one area that keeps a private data store in a specialized way to favor their operations only. To address this challenge, we have designed and developed GRAPHONE, a graph data store that abstracts the graph data store away from the specialized systems to solve the fundamental research problems associated with the data store design. It combines two complementary graph storage formats (edge list and adjacency list) and uses dual versioning to decouple graph computations from updates. Importantly, it presents a new data abstraction, GraphView, to enable data access at two different granularities of data ingestions (called data visibility) for concurrent execution of diverse classes of real-time graph analytics with only a small data duplication. Experimental results show that GRAPHONE is able to deliver 11.40x and 5.36x average speedup in ingestion rate against LLAMA and Stinger, the two state-of-the-art dynamic graph systems, respectively. Further, they achieve an average speedup of 8.75x and 4.14x against LLAMA and 12.80x and 3.18x against Stinger for BFS and PageRank analytics (batch version), respectively. GRAPHONE also gains over 2,000x speedup against Kickstarter, a state-of-the-art stream analytics engine in ingesting the streaming edges and performing streaming BPS when treating first half as a base snapshot and rest as streaming edge in a synthetic graph. GRAPHONE also achieves an ingestion rate of two to three orders of magnitude higher than graph databases. Finally, we demonstrate that it is possible to run concurrent stream analytics from the same data store.
引用
收藏
页数:40
相关论文
共 87 条
[1]   Aurora: a new model and architecture for data stream management [J].
Abadi, DJ ;
Carney, D ;
Cetintemel, U ;
Cherniack, M ;
Convey, C ;
Lee, S ;
Stonebraker, M ;
Tatbul, N ;
Zdonik, S .
VLDB JOURNAL, 2003, 12 (02) :120-139
[2]  
Abadi DJ, 2005, In CIDR, P277
[3]  
Ai LY, 2017, 2017 USENIX ANNUAL TECHNICAL CONFERENCE (USENIX ATC '17), P125
[4]   Graph based anomaly detection and description: a survey [J].
Akoglu, Leman ;
Tong, Hanghang ;
Koutra, Danai .
DATA MINING AND KNOWLEDGE DISCOVERY, 2015, 29 (03) :626-688
[5]   Internet -: Diameter of the World-Wide Web [J].
Albert, R ;
Jeong, H ;
Barabási, AL .
NATURE, 1999, 401 (6749) :130-131
[6]  
Anicic Darko., 2011, Proceedings of the 20th international conference on World wide web, P635, DOI DOI 10.1145/1963405.1963495
[7]  
[Anonymous], 2016, P 4 INT WORKSH GRAPH
[8]  
[Anonymous], 2008, SOCIAL NETWORK ANAL
[9]  
Beamer S, 2012, INT CONF HIGH PERFOR
[10]  
Bhattarai Bibek, 2019, P 2019 INT C MAN DAT