The Trinity Graph Engine

作者: Bin Shao , Yatao Li , Haixun Wang

DOI:

关键词: Distributed memorySpecification languageTheoretical computer scienceDatabase schemaRandom accessCommunications protocolWorld Wide WebCloud computingAnalyticsComputer scienceData access

摘要: Computations performed by graph algorithms are data driven, and require a high degree of random access. Despite the great progresses made in disk technology, it still cannot provide level efficient access required computation. On other hand, memory-based approaches usually do not scale due to capacity limit single machines. In this paper, we introduce Trinity, general purpose engine over distributed memory cloud. Through optimized management network communication, Trinity supports fast exploration as well parallel computing. particular, leverages patterns both online offline computation optimize communication for best performance. These enable support query processing analytics on large graphs with just few commodity Furthermore, provides specification language called TSL users declare schema protocols, which brings ease-of-use Our experiments show Trinity’s performance low latency queries throughput web-scale, billion-node graphs.

参考文章(22)
Deepayan Chakrabarti, Christos Faloutsos, Yiping Zhan, R-MAT: A Recursive Model for Graph Mining siam international conference on data mining. pp. 442- 446 ,(2004)
Brad Fitzpatrick, Distributed caching with memcached Linux Journal. ,vol. 2004, pp. 5- ,(2004)
Borislav Iordanov, HyperGraphDB: a generalized graph database web-age information management. pp. 25- 36 ,(2010) , 10.1007/978-3-642-16720-1_3
Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, Robert E. Gruber, Bigtable ACM Transactions on Computer Systems. ,vol. 26, pp. 1- 26 ,(2008) , 10.1145/1365815.1365816
Y.H Tsin, Some remarks on distributed depth-first search Information Processing Letters. ,vol. 82, pp. 173- 178 ,(2002) , 10.1016/S0020-0190(01)00273-3
Diego Ongaro, Stephen M. Rumble, Ryan Stutsman, John Ousterhout, Mendel Rosenblum, Fast crash recovery in RAMCloud Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles - SOSP '11. pp. 29- 41 ,(2011) , 10.1145/2043556.2043560
J. Cohen, Graph Twiddling in a MapReduce World computational science and engineering. ,vol. 11, pp. 29- 41 ,(2009) , 10.1109/MCSE.2009.120
Thorsten Schütt, Florian Schintke, Alexander Reinefeld, Scalaris Proceedings of the 7th ACM SIGPLAN workshop on ERLANG - ERLANG '08. pp. 41- 48 ,(2008) , 10.1145/1411273.1411280
ANDREW LUMSDAINE, DOUGLAS GREGOR, BRUCE HENDRICKSON, JONATHAN BERRY, CHALLENGES IN PARALLEL GRAPH PROCESSING Parallel Processing Letters. ,vol. 17, pp. 5- 20 ,(2007) , 10.1142/S0129626407002843
Jiefeng Cheng, Jeffrey Xu Yu, Bolin Ding, Philip S. Yu, Haixun Wang, Fast Graph Pattern Matching international conference on data engineering. pp. 913- 922 ,(2008) , 10.1109/ICDE.2008.4497500