{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T13:08:12Z","timestamp":1775912892124,"version":"3.50.1"},"reference-count":66,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2016,7]]},"abstract":"<jats:p>Graph databases have become a common infrastructure component. Yet existing systems either operate on offline snapshots, provide weak consistency guarantees, or use expensive concurrency control techniques that limit performance.<\/jats:p>\n          <jats:p>In this paper, we introduce a new distributed graph database, called Weaver, which enables efficient, transactional graph analyses as well as strictly serializable ACID transactions on dynamic graphs. The key insight that allows Weaver to combine strict serializability with horizontal scalability and high performance is a novel request ordering mechanism called refinable timestamps. This technique couples coarse-grained vector timestamps with a fine-grained timeline oracle to pay the overhead of strong consistency only when needed. Experiments show that Weaver enables a Bitcoin blockchain explorer that is 8x faster than Blockchain.info, and achieves 10.9x higher throughput than the Titan graph database on social network workloads and 4x lower latency than GraphLab on offline graph traversal workloads.<\/jats:p>","DOI":"10.14778\/2983200.2983202","type":"journal-article","created":{"date-parts":[[2016,8,5]],"date-time":"2016-08-05T12:34:02Z","timestamp":1470400442000},"page":"852-863","source":"Crossref","is-referenced-by-count":35,"title":["Weaver"],"prefix":"10.14778","volume":"9","author":[{"given":"Ayush","family":"Dubey","sequence":"first","affiliation":[{"name":"Cornell University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Greg D.","family":"Hill","sequence":"additional","affiliation":[{"name":"Stanford University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Escriva","sequence":"additional","affiliation":[{"name":"Cornell University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emin G\u00fcn","family":"Sirer","sequence":"additional","affiliation":[{"name":"Cornell University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Blockchain. https:\/\/blockchain.info.  Blockchain. https:\/\/blockchain.info."},{"key":"e_1_2_1_2_1","unstructured":"The Plan to Build a Massive Online Brain for All the World's Robots. http:\/\/www.wired.com\/2014\/08\/robobrain.  The Plan to Build a Massive Online Brain for All the World's Robots. http:\/\/www.wired.com\/2014\/08\/robobrain."},{"key":"e_1_2_1_3_1","unstructured":"Apache Giraph. http:\/\/giraph.apache.org\/.  Apache Giraph. http:\/\/giraph.apache.org\/."},{"key":"e_1_2_1_4_1","unstructured":"Apache Hama. http:\/\/hama.apache.org\/.  Apache Hama. http:\/\/hama.apache.org\/."},{"key":"e_1_2_1_5_1","unstructured":"Facebook Graph Search. https:\/\/www.facebook.com\/about\/graphsearch.  Facebook Graph Search. https:\/\/www.facebook.com\/about\/graphsearch."},{"key":"e_1_2_1_6_1","unstructured":"Neo4j. http:\/\/neo4j.org.  Neo4j. http:\/\/neo4j.org."},{"key":"e_1_2_1_7_1","unstructured":"TPC-C. http:\/\/www.tpc.org\/tpcc.  TPC-C. http:\/\/www.tpc.org\/tpcc."},{"key":"e_1_2_1_8_1","unstructured":"Three and a half degrees of separation. https:\/\/research.facebook.com\/blog\/three-and-a-half-degrees-of-separation\/.  Three and a half degrees of separation. https:\/\/research.facebook.com\/blog\/three-and-a-half-degrees-of-separation\/."},{"key":"e_1_2_1_9_1","unstructured":"Titan. https:\/\/github.com\/thinkaurelius\/titan\/wiki.  Titan. https:\/\/github.com\/thinkaurelius\/titan\/wiki."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150412"},{"key":"e_1_2_1_11_1","first-page":"49","volume-title":"USENIX ATC","author":"Bronson N.","year":"2013","unstructured":"N. Bronson , Z. Amsden , G. Cabrera , P. Chakka , P. Dimov , H. Ding , J. Ferris , A. Giardullo , S. Kulkarni , H. Li , M. Marchukov , D. Petrov , L. Puzar , Y. J. Song , and V. Venkataramani . TAO: Facebook's Distributed Data Store for the Social Graph . USENIX ATC , pages 49 -- 60 , June 2013 . N. Bronson, Z. Amsden, G. Cabrera, P. Chakka, P. Dimov, H. Ding, J. Ferris, A. Giardullo, S. Kulkarni, H. Li, M. Marchukov, D. Petrov, L. Puzar, Y. J. Song, and V. Venkataramani. TAO: Facebook's Distributed Data Store for the Social Graph. USENIX ATC, pages 49--60, June 2013."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735471.2735477"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2391229.2391232"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741970"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168846"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824077"},{"key":"e_1_2_1_17_1","first-page":"251","volume-title":"OSDI","author":"Corbett J. C.","year":"2012","unstructured":"J. C. Corbett , J. Dean , M. Epstein , A. Fikes , C. Frost , J. J. Furman , S. Ghemawat , A. Gubarev , C. Heiser , P. Hochschild , W. Hsieh , S. Kanthak , E. Kogan , H. Li , A. Lloyd , S. Melnik , D. Mwaura , D. Nagle , S. Quinlan , R. Rao , L. Rolig , Y. Saito , M. Szymaniak , C. Taylor , R. Wang , and D. Woodford . Spanner: Google's Globally-Distributed Database . OSDI , pages 251 -- 264 , Oct. 2012 . J. C. Corbett, J. Dean, M. Epstein, A. Fikes, C. Frost, J. J. Furman, S. Ghemawat, A. Gubarev, C. Heiser, P. Hochschild, W. Hsieh, S. Kanthak, E. Kogan, H. Li, A. Lloyd, S. Melnik, D. Mwaura, D. Nagle, S. Quinlan, R. Rao, L. Rolig, Y. Saito, M. Szymaniak, C. Taylor, R. Wang, and D. Woodford. Spanner: Google's Globally-Distributed Database. OSDI, pages 251--264, Oct. 2012."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806777.2806837"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815425"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592822"},{"key":"e_1_2_1_21_1","volume-title":"Warp: Lightweight Multi-Key Transactions for Key-Value Stores. CoRR, abs\/1509.07815","author":"Escriva R.","year":"2015","unstructured":"R. Escriva , B. Wong , and E. G. Sirer . Warp: Lightweight Multi-Key Transactions for Key-Value Stores. CoRR, abs\/1509.07815 , 2015 . R. Escriva, B. Wong, and E. G. Sirer. Warp: Lightweight Multi-Key Transactions for Key-Value Stores. CoRR, abs\/1509.07815, 2015."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809981"},{"issue":"1","key":"e_1_2_1_23_1","first-page":"56","article-title":"Timestamps","volume":"10","author":"Fidge C. J.","year":"1988","unstructured":"C. J. Fidge . Timestamps in Message-Passing Systems That Preserve the Partial Ordering. Australian Computer Science Communications , 10 ( 1 ): 56 -- 66 , 1988 . C. J. Fidge. Timestamps in Message-Passing Systems That Preserve the Partial Ordering. Australian Computer Science Communications, 10(1):56--66, 1988.","journal-title":"Message-Passing Systems That Preserve the Partial Ordering. Australian Computer Science Communications"},{"key":"e_1_2_1_24_1","volume-title":"Database Systems","author":"Garcia-Molina H.","year":"2009","unstructured":"H. Garcia-Molina , J. D. Ullman , and J. Widom . Database Systems . Pearson Prentice Hall , 2009 . H. Garcia-Molina, J. D. Ullman, and J. Widom. Database Systems. Pearson Prentice Hall, 2009."},{"issue":"11","key":"e_1_2_1_25_1","volume":"26","author":"Gedik B.","year":"2014","unstructured":"B. Gedik and R. Bordawekar . Disk-Based Management of Interaction Graphs. IEEE Transactions on Knowledge and Data Engineering , 26 ( 11 ), 2014 . B. Gedik and R. Bordawekar. Disk-Based Management of Interaction Graphs. IEEE Transactions on Knowledge and Data Engineering, 26(11), 2014.","journal-title":"Disk-Based Management of Interaction Graphs. IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_26_1","first-page":"17","volume-title":"OSDI","author":"Gonzalez J. E.","year":"2012","unstructured":"J. E. Gonzalez , Y. Low , H. Gu , D. Bickson , and C. Guestrin . PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs . OSDI , pages 17 -- 30 , Oct. 2012 . J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin. PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs. OSDI, pages 17--30, Oct. 2012."},{"key":"e_1_2_1_27_1","volume-title":"OSDI","author":"Gonzalez J. E.","year":"2014","unstructured":"J. E. Gonzalez , R. S. Xin , A. Dave , D. Crankshaw , M. J. Franklin , and I. Stoica . GraphX: Graph Processing in a Distributed Dataflow Framework . OSDI , Oct. 2014 . J. E. Gonzalez, R. S. Xin, A. Dave, D. Crankshaw, M. J. Franklin, and I. Stoica. GraphX: Graph Processing in a Distributed Dataflow Framework. OSDI, Oct. 2014."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"J. N. Gray. Notes on Data Base Operating Systems. Springer 1978.  J. N. Gray. Notes on Data Base Operating Systems. Springer 1978.","DOI":"10.1007\/3-540-08755-9_9"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2777598.2777604"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592799"},{"key":"e_1_2_1_31_1","first-page":"25","volume-title":"WAIM","author":"Iordanov B.","year":"2010","unstructured":"B. Iordanov . HyperGraphDB : A Generalized Graph Database . WAIM , pages 25 -- 36 , July 2010 . B. Iordanov. HyperGraphDB: A Generalized Graph Database. WAIM, pages 25--36, July 2010."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465369"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/319566.319567"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_35_1","first-page":"31","volume-title":"OSDI","author":"Kyrola A.","year":"2012","unstructured":"A. Kyrola , G. E. Blelloch , and C. Guestrin . GraphChi: Large-Scale Graph Computation on Just a PC . OSDI , pages 31 -- 46 , Oct. 2012 . A. Kyrola, G. E. Blelloch, and C. Guestrin. GraphChi: Large-Scale Graph Computation on Just a PC. OSDI, pages 31--46, Oct. 2012."},{"key":"e_1_2_1_36_1","volume-title":"GraphChi-DB: Simple Design for a Scalable Graph Database System - on Just a PC. CoRR, abs\/1403.0701","author":"Kyrola A.","year":"2014","unstructured":"A. Kyrola and C. Guestrin . GraphChi-DB: Simple Design for a Scalable Graph Database System - on Just a PC. CoRR, abs\/1403.0701 , 2014 . A. Kyrola and C. Guestrin. GraphChi-DB: Simple Design for a Scalable Graph Database System - on Just a PC. CoRR, abs\/1403.0701, 2014."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/279227.279229"},{"key":"e_1_2_1_38_1","author":"Levandoski J.","year":"2015","unstructured":"J. Levandoski , D. Lomet , S. Sengupta , R. Stutsman , and R. Wang . High Performance Transactions in Deuteronomy. CIDR , Jan. 2015 . J. Levandoski, D. Lomet, S. Sengupta, R. Stutsman, and R. Wang. High Performance Transactions in Deuteronomy. CIDR, Jan. 2015.","journal-title":"High Performance Transactions in Deuteronomy. CIDR"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1181309.1181314"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815426"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_42_1","first-page":"548","volume-title":"NIPS","author":"McAuley J. J.","year":"2012","unstructured":"J. J. McAuley and J. Leskovec . Learning to Discover Social Circles in Ego Networks . NIPS , pages 548 -- 556 , Dec. 2012 . J. J. McAuley and J. Leskovec. Learning to Discover Social Circles in Ego Networks. NIPS, pages 548--556, Dec. 2012."},{"key":"e_1_2_1_43_1","volume-title":"HotOS Workshop","author":"McSherry F.","year":"2015","unstructured":"F. McSherry , M. Isard , and D. G. Murray . Scalability! But at what COST ? HotOS Workshop , May 2015 . F. McSherry, M. Isard, and D. G. Murray. Scalability! But at what COST? HotOS Workshop, May 2015."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522738"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557914.1557933"},{"key":"e_1_2_1_46_1","volume-title":"Bitcoin: A Peer-to-Peer Electronic Cash System","author":"Nakamoto S.","year":"2008","unstructured":"S. Nakamoto . Bitcoin: A Peer-to-Peer Electronic Cash System . 2008 . S. Nakamoto. Bitcoin: A Peer-to-Peer Electronic Cash System. 2008."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2749436"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487696"},{"key":"e_1_2_1_49_1","first-page":"41","volume-title":"USENIX ATC","author":"Prabhakaran V.","year":"2012","unstructured":"V. Prabhakaran , M. Wu , X. Weng , F. McSherry , L. Zhou , and M. Haridasan . Managing Large Graphs on Multi-Cores With Graph Awareness . USENIX ATC , pages 41 -- 52 , June 2012 . V. Prabhakaran, M. Wu, X. Weng, F. McSherry, L. Zhou, and M. Haridasan. Managing Large Graphs on Multi-Cores With Graph Awareness. USENIX ATC, pages 41--52, June 2012."},{"key":"e_1_2_1_51_1","unstructured":"M. A. Rodriguez and M. Broecheler. http:\/\/www.slideshare.net\/slidarko\/titan-the-rise-of-big-graph-data.  M. A. Rodriguez and M. Broecheler. http:\/\/www.slideshare.net\/slidarko\/titan-the-rise-of-big-graph-data."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522740"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484838.2484843"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/98163.98167"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2467799"},{"key":"e_1_2_1_57_1","unstructured":"P. Smith. Personal communication 2015.  P. Smith. Personal communication 2015."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339722"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723732"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732232.2732238"},{"key":"e_1_2_1_61_1","volume-title":"The Anatomy of the Facebook Social Graph. CoRR, abs\/1111.4503","author":"Ugander J.","year":"2011","unstructured":"J. Ugander , B. Karrer , L. Backstrom , and C. Marlow . The Anatomy of the Facebook Social Graph. CoRR, abs\/1111.4503 , 2011 . J. Ugander, B. Karrer, L. Backstrom, and C. Marlow. The Anatomy of the Facebook Social Graph. CoRR, abs\/1111.4503, 2011."},{"key":"e_1_2_1_62_1","first-page":"91","volume-title":"OSDI","author":"van Renesse R.","year":"2004","unstructured":"R. van Renesse and F. B. Schneider . Chain Replication for Supporting High Throughput and Availability . OSDI , pages 91 -- 104 , Dec. 2004 . R. van Renesse and F. B. Schneider. Chain Replication for Supporting High Throughput and Availability. OSDI, pages 91--104, Dec. 2004."},{"key":"e_1_2_1_63_1","first-page":"387","volume-title":"USENIX ATC","author":"Wang K.","year":"2015","unstructured":"K. Wang , G. Xu , Z. Su , and Y. D. Liu . GraphQ: Graph Query Processing with Abstraction Refinement--Scalable and Programmable Analytics over Very Large Graphs on a Single PC . USENIX ATC , pages 387 -- 401 , July 2015 . K. Wang, G. Xu, Z. Su, and Y. D. Liu. GraphQ: Graph Query Processing with Abstraction Refinement--Scalable and Programmable Analytics over Very Large Graphs on a Single PC. USENIX ATC, pages 387--401, July 2015."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556581"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733103"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741096"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735496.2735501"},{"key":"e_1_2_1_68_1","first-page":"375","volume-title":"USENIX ATC","author":"Zhu X.","year":"2015","unstructured":"X. Zhu , W. Han , and W. Chen . GridGraph: Large-Scale Graph Processing on a Single Machine Using 2-Level Hierarchical Partitioning . USENIX ATC , pages 375 -- 386 , July 2015 . X. Zhu, W. Han, and W. Chen. GridGraph: Large-Scale Graph Processing on a Single Machine Using 2-Level Hierarchical Partitioning. USENIX ATC, pages 375--386, July 2015."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2983200.2983202","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:28:37Z","timestamp":1672223317000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2983200.2983202"}},"subtitle":["a high-performance, transactional graph database based on refinable timestamps"],"short-title":[],"issued":{"date-parts":[[2016,7]]},"references-count":66,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2016,7]]}},"alternative-id":["10.14778\/2983200.2983202"],"URL":"https:\/\/doi.org\/10.14778\/2983200.2983202","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2016,7]]}}}