{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T16:48:56Z","timestamp":1786639736902,"version":"build-2736575974"},"reference-count":97,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,11,30]],"date-time":"2019-11-30T00:00:00Z","timestamp":1575072000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1350766 1618706 1717774."],"award-info":[{"award-number":["1350766 1618706 1717774."]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2019,11,30]]},"abstract":"<jats:p>\n            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 G\n            <jats:sc>raph<\/jats:sc>\n            O\n            <jats:sc>ne<\/jats:sc>\n            , 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\n            <jats:italic>dual versioning<\/jats:italic>\n            to decouple graph computations from updates. Importantly, it presents a new data abstraction,\n            <jats:italic>GraphView<\/jats:italic>\n            , to enable data access at two different granularities of data ingestions (called\n            <jats:italic>data visibility<\/jats:italic>\n            ) for concurrent execution of diverse classes of real-time graph analytics with only a small data duplication. Experimental results show that G\n            <jats:sc>raph<\/jats:sc>\n            O\n            <jats:sc>ne<\/jats:sc>\n            is able to deliver 11.40\u00d7 and 5.36\u00d7 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.75\u00d7 and 4.14\u00d7 against LLAMA and 12.80\u00d7 and 3.18\u00d7 against Stinger for BFS and PageRank analytics (batch version), respectively. G\n            <jats:sc>raph<\/jats:sc>\n            O\n            <jats:sc>ne<\/jats:sc>\n            also gains over 2,000\u00d7 speedup against Kickstarter, a state-of-the-art stream analytics engine in ingesting the streaming edges and performing streaming BFS when treating first half as a base snapshot and rest as streaming edge in a synthetic graph. G\n            <jats:sc>raph<\/jats:sc>\n            O\n            <jats:sc>ne<\/jats:sc>\n            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.\n          <\/jats:p>","DOI":"10.1145\/3364180","type":"journal-article","created":{"date-parts":[[2020,4,4]],"date-time":"2020-04-04T10:48:51Z","timestamp":1585997331000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":63,"title":["G\n            <scp>raph<\/scp>\n            O\n            <scp>ne<\/scp>"],"prefix":"10.1145","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9314-4772","authenticated-orcid":false,"given":"Pradeep","family":"Kumar","sequence":"first","affiliation":[{"name":"Department of Computer Science, William and Mary, Williamsburg, VA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"H. Howie","family":"Huang","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, George Washington University, Washington, DC"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,1,16]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. Friendster Network Dataset\u2014KONECT. Retrieved from http:\/\/konect.uni-koblenz.de\/networks\/friendster.  [n.d.]. Friendster Network Dataset\u2014KONECT. Retrieved from http:\/\/konect.uni-koblenz.de\/networks\/friendster."},{"key":"e_1_2_1_2_1","unstructured":"[n.d.]. Titan Graph Database. Retrieved from https:\/\/github.com\/thinkaurelius\/titan.  [n.d.]. Titan Graph Database. Retrieved from https:\/\/github.com\/thinkaurelius\/titan."},{"key":"e_1_2_1_3_1","unstructured":"[n.d.]. Twitter (MPI) Network Dataset\u2014KONECT. Retrieved from http:\/\/konect.uni-koblenz.de\/networks\/twitter_mpi. http:\/\/konect.uni-koblenz.de\/networks\/twitter_mpi.  [n.d.]. Twitter (MPI) Network Dataset\u2014KONECT. Retrieved from http:\/\/konect.uni-koblenz.de\/networks\/twitter_mpi. http:\/\/konect.uni-koblenz.de\/networks\/twitter_mpi."},{"key":"e_1_2_1_4_1","unstructured":"[n.d.]. Web Graphs. Retrieved from http:\/\/webdatacommons.org\/hyperlinkgraph\/2012-08\/download.html. http:\/\/webdatacommons.org\/hyperlinkgraph\/2012-08\/download.html.  [n.d.]. Web Graphs. Retrieved from http:\/\/webdatacommons.org\/hyperlinkgraph\/2012-08\/download.html. http:\/\/webdatacommons.org\/hyperlinkgraph\/2012-08\/download.html."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the Conference on Innovative Data Systems Research (CIDR\u201905)","volume":"5","author":"Abadi Daniel J.","year":"2005"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-003-0095-z"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 2017 USENIX Annual Technical Conference (USENIX ATC\u201917)","author":"Ai Zhiyuan","year":"2017"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-014-0365-y"},{"key":"e_1_2_1_9_1","volume-title":"Internet: Diameter of the world-wide web. Nature 401, 6749 (9","author":"Albert Reka","year":"1999"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963495"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC\u201912)","author":"Beamer S."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 2019 International Conference on Management of Data (SIGMOD\u201919)","author":"Bhattarai Bibek"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the USENIX Annual Technical Conference. 49--60","author":"Bronson Nathan","year":"2013"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.43"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2741948.2741970"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168846"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 18th International Conference on Extending Database Technology (EDBT\u201915)","author":"Choudhury Sutanay","year":"2015"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168854"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3078597.3078606"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314598"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","volume-title":"Networks, Crowds, and Markets: Reasoning about a Highly Connected World","author":"Easley David","DOI":"10.1017\/CBO9780511761942"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 2012 IEEE Conference on High Performance Extreme Computing (HPEC\u201912)","author":"Ediger David"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/316188.316229"},{"key":"e_1_2_1_25_1","unstructured":"FlockDB. 2010. Retrieved from https:\/\/blog.twitter.com\/engineering\/en_us\/a\/2010\/introducing-flockdb.html.  FlockDB. 2010. Retrieved from https:\/\/blog.twitter.com\/engineering\/en_us\/a\/2010\/introducing-flockdb.html."},{"key":"e_1_2_1_26_1","unstructured":"Graph Compute with Neo4j. 2016. Retrieved from https:\/\/neo4j.com\/blog\/graph-compute-neo4j-algorithms-spark-extensions\/.  Graph Compute with Neo4j. 2016. Retrieved from https:\/\/neo4j.com\/blog\/graph-compute-neo4j-algorithms-spark-extensions\/."},{"key":"e_1_2_1_27_1","unstructured":"Graph500. [n.d.]. Retrieved from http:\/\/www.graph500.org\/.  Graph500. [n.d.]. Retrieved from http:\/\/www.graph500.org\/."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the European Conference on Computer Systems (EuroSys\u201914)","author":"Han Wentao","year":"2014"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487581"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Sungpack Hong Hassan Chafi Edic Sedlar and Kunle Olukotun. 2012. Green-Marl: A DSL for easy and efficient graph analysis. In ACM SIGARCH Computer Architecture News.  Sungpack Hong Hassan Chafi Edic Sedlar and Kunle Olukotun. 2012. Green-Marl: A DSL for easy and efficient graph analysis. In ACM SIGARCH Computer Architecture News.","DOI":"10.1145\/2150976.2151013"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 2017 IEEE High Performance Extreme Computing Conference (HPEC\u201917)","author":"Hu Yang"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis. IEEE Press, 14","author":"Hu Yang"},{"key":"e_1_2_1_33_1","volume-title":"Adamic","author":"Huberman Bernardo A.","year":"1999"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2960414.2960419"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1038\/35036627"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis. IEEE Press, 58","author":"Ji Yuede"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 2016 USENIX Annual Technical Conference (USENIX ATC\u201916)","author":"Ju Xiaoen"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020580"},{"key":"e_1_2_1_39_1","unstructured":"Alexander D. Kent. 2015. Comprehensive Multi-Source Cyber-Security Events. Los Alamos National Laboratory. DOI:https:\/\/doi.org\/10.17021\/1179829  Alexander D. Kent. 2015. Comprehensive Multi-Source Cyber-Security Events. Los Alamos National Laboratory. DOI:https:\/\/doi.org\/10.17021\/1179829"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cose.2014.09.001"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544892"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882905"},{"key":"e_1_2_1_43_1","volume-title":"Social Network Analysis","author":"Knoke David"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the International Workshop on Networking Meets Databases (NetDB\u201911)","author":"Kreps Jay","year":"2011"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC\u201916)","author":"Kumar Pradeep"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 2017 USENIX Annual Technical Conference (USENIX ATC\u201917)","author":"Kumar Pradeep"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the IEEE International Congress on Big Data (BigData Congress\u201917)","author":"Kumar Pradeep"},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the 17th USENIX Conference on File and Storage Technologies (FAST\u201919)","author":"Kumar Pradeep"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201912)","author":"Kyrola A."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293883.3299108"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2018.00059"},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC\u201915)","author":"Liu Hang"},{"key":"e_1_2_1_55_1","volume-title":"Proceedings of the 15th USENIX Conference on File and Storage Technologies (FAST\u201917)","author":"Liu Hang"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882959"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3064176.3064191"},{"key":"e_1_2_1_59_1","volume-title":"Proceedings of the 2015 IEEE 31st International Conference on Data Engineering (ICDE\u201915)","author":"Macko Peter"},{"key":"e_1_2_1_60_1","volume-title":"Proceedings of the 2017 USENIX Annual Technical Conference (USENIX ATC\u201917)","author":"Malicevic Jasmina","year":"2017"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3302424.3303974"},{"key":"e_1_2_1_62_1","volume-title":"Proceedings of the 1st Workshop on Parallel Programming for Analytics Applications (PPAA\u201914)","author":"McColl Robert Campbell"},{"key":"e_1_2_1_63_1","volume-title":"Proceedings of the 15th Workshop on Hot Topics in Operating Systems (HotOS XV).","author":"McSherry Frank"},{"key":"e_1_2_1_64_1","volume-title":"Proceedings of the Conference on Innovative Data Systems Research (CIDR\u201918)","author":"McSherry Frank","year":"2018"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522738"},{"key":"e_1_2_1_66_1","unstructured":"Neo4j Inc. 2016. Retrieved from https:\/\/neo4j.com\/.  Neo4j Inc. 2016. Retrieved from https:\/\/neo4j.com\/."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_2_1_68_1","unstructured":"Orient Database. 2016. Retrieved from https:\/\/orientdb.com\/.  Orient Database. 2016. Retrieved from https:\/\/orientdb.com\/."},{"key":"e_1_2_1_69_1","unstructured":"Lawrence Page Sergey Brin Rajeev Motwani and Terry Winograd. 1999. The pagerank citation ranking: Bringing order to the web. Stanford InfoLab.  Lawrence Page Sergey Brin Rajeev Motwani and Terry Winograd. 1999. The pagerank citation ranking: Bringing order to the web. Stanford InfoLab."},{"key":"e_1_2_1_70_1","volume-title":"Intel Threading Building Blocks (1 ed.). O\u2019Reilly 8 Associates","author":"Reinders James"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402713"},{"key":"e_1_2_1_72_1","unstructured":"Ian Robinson Jim Webber and Emil Eifrem. 2013. Graph Databases. O\u2019Reilly Media.  Ian Robinson Jim Webber and Emil Eifrem. 2013. Graph Databases. O\u2019Reilly Media."},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963503"},{"key":"e_1_2_1_74_1","volume-title":"Proceedings of the ACM Symposium on Operating Systems Principles (SOSP\u201915)","author":"Roy A."},{"key":"e_1_2_1_75_1","volume-title":"Proceedings of the ACM Symposium on Operating Systems Principles (SOSP\u201915)","author":"Roy A."},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.5555\/3014904.3014945"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556572"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007265"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2467799"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/3267809.3267811"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882950"},{"key":"e_1_2_1_82_1","volume-title":"Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP\u201913)","author":"Shun Julian"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.14778\/3090163.3090166"},{"key":"#cr-split#-e_1_2_1_84_1.1","doi-asserted-by":"crossref","unstructured":"M. J. M. Turcotte A. D. Kent and C. Hash. 2017. Unified host and network data set. In Data Science for Cyber-Security. World Scientific. DOI:10.1142\/9781786345646_001 10.1142\/9781786345646_001","DOI":"10.1142\/9781786345646_001"},{"key":"#cr-split#-e_1_2_1_84_1.2","doi-asserted-by":"crossref","unstructured":"M. J. M. Turcotte A. D. Kent and C. Hash. 2017. Unified host and network data set. In Data Science for Cyber-Security. World Scientific. DOI:10.1142\/9781786345646_001","DOI":"10.1142\/9781786345646_001"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037748"},{"key":"e_1_2_1_86_1","volume-title":"Proceedings of the Conference on Innovative Data Systems Research (CIDR\u201913)","volume":"13","author":"Wang Guozhang","year":"2013"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806777.2806849"},{"key":"e_1_2_1_88_1","volume-title":"Proceedings of the 2015 IEEE 31st International Conference on Data Engineering (ICDE\u201915)","author":"Xie Wenlei"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2743708"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535570.2488333"},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1145\/2858788.2688507"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCGRID.2018.00033"},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132777"},{"key":"e_1_2_1_94_1","volume-title":"Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST\u201915)","author":"Zheng Da"},{"key":"e_1_2_1_95_1","volume-title":"Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201916)","author":"Zhu Xiaowei","year":"2016"},{"key":"e_1_2_1_96_1","volume-title":"Proceedings of the USENIX Conference on Usenix Annual Technical Conference.","author":"Zhu Xiaowei","year":"2015"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3364180","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3364180","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3364180","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:26Z","timestamp":1750203866000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3364180"}},"subtitle":["A Data Store for Real-time Analytics on Evolving Graphs"],"short-title":[],"issued":{"date-parts":[[2019,11,30]]},"references-count":97,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,11,30]]}},"alternative-id":["10.1145\/3364180"],"URL":"https:\/\/doi.org\/10.1145\/3364180","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"value":"1553-3077","type":"print"},{"value":"1553-3093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,30]]},"assertion":[{"value":"2019-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-01-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}