{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T02:18:29Z","timestamp":1773886709902,"version":"3.50.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:p>\n            Graph query services (GQS) are widely used today to interactively answer graph traversal queries on large-scale graph data. Existing graph query engines focus largely on optimizing the latency of a single query. This ignores significant challenges posed by GQS, including fine-grained control and scheduling during query execution, as well as performance isolation and load balancing in various levels from across user to intra-query. To tackle these control and scheduling challenges, we propose a novel\n            <jats:italic>scoped<\/jats:italic>\n            dataflow for modeling graph traversal queries, which explicitly exposes concurrent execution and control of any subquery to the finest granularity. We implemented Banyan, an engine based on the scoped dataflow model for GQS. Banyan focuses on scaling up the performance on a single machine, and provides the ability to easily scale out. Extensive experiments on multiple benchmarks show that Banyan improves performance by up to three orders of magnitude over state-of-the-art graph query engines, while providing performance isolation and load balancing.\n          <\/jats:p>","DOI":"10.14778\/3547305.3547311","type":"journal-article","created":{"date-parts":[[2022,9,7]],"date-time":"2022-09-07T16:09:53Z","timestamp":1662566993000},"page":"2045-2057","source":"Crossref","is-referenced-by-count":6,"title":["Banyan"],"prefix":"10.14778","volume":"15","author":[{"given":"Li","family":"Su","sequence":"first","affiliation":[{"name":"Alibaba Group"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaoming","family":"Qin","sequence":"additional","affiliation":[{"name":"Alibaba Group"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zichao","family":"Zhang","sequence":"additional","affiliation":[{"name":"Alibaba Group"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rui","family":"Yang","sequence":"additional","affiliation":[{"name":"University of Illinois Urbana-Champaign"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Le","family":"Xu","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Indranil","family":"Gupta","sequence":"additional","affiliation":[{"name":"University of Illinois Urbana-Champaign"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenyuan","family":"Yu","sequence":"additional","affiliation":[{"name":"Alibaba Group"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kai","family":"Zeng","sequence":"additional","affiliation":[{"name":"UESTC"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingren","family":"Zhou","sequence":"additional","affiliation":[{"name":"Alibaba Group"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,9,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Distributed evaluation of subgraph queries using worstcase optimal lowmemory dataflows. arXiv preprint arXiv:1802.03760","author":"Ammar Khaled","year":"2018","unstructured":"Khaled Ammar , Frank McSherry , Semih Salihoglu , and Manas Joglekar . 2018. Distributed evaluation of subgraph queries using worstcase optimal lowmemory dataflows. arXiv preprint arXiv:1802.03760 ( 2018 ). Khaled Ammar, Frank McSherry, Semih Salihoglu, and Manas Joglekar. 2018. Distributed evaluation of subgraph queries using worstcase optimal lowmemory dataflows. arXiv preprint arXiv:1802.03760 (2018)."},{"key":"e_1_2_1_2_1","volume-title":"J\u00e1nos Benjamin Antal, et al","author":"Angles Renzo","year":"2020","unstructured":"Renzo Angles , J\u00e1nos Benjamin Antal, et al . 2020 . The LDBC Social Network Benchmark. CoRR abs\/2001.02299 (2020). arXiv:2001.02299 http:\/\/arxiv.org\/abs\/2001.02299 Renzo Angles, J\u00e1nos Benjamin Antal, et al. 2020. The LDBC Social Network Benchmark. CoRR abs\/2001.02299 (2020). arXiv:2001.02299 http:\/\/arxiv.org\/abs\/2001.02299"},{"key":"e_1_2_1_3_1","unstructured":"Apache Flink 2021. Apache Flink. https:\/\/flink.apache.org\/.  Apache Flink 2021. Apache Flink. https:\/\/flink.apache.org\/."},{"key":"e_1_2_1_4_1","unstructured":"Apache Hadoop 2021. Apache Hadoop. https:\/\/github.com\/apache\/hadoop.  Apache Hadoop 2021. Apache Hadoop. https:\/\/github.com\/apache\/hadoop."},{"key":"e_1_2_1_5_1","unstructured":"Apache Spark 2021. Apache Spark. https:\/\/spark.apache.org\/.  Apache Spark 2021. Apache Spark. https:\/\/spark.apache.org\/."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/209937.209958"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/214451.214456"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357223.3362715"},{"key":"e_1_2_1_9_1","volume-title":"Retrieved","author":"Cypher","year":"2021","unstructured":"Cypher 2021 . Cypher Query Language . Retrieved Dec 20, 2021 from https:\/\/neo4j.com\/developer\/cypher\/ Cypher 2021. Cypher Query Language. Retrieved Dec 20, 2021 from https:\/\/neo4j.com\/developer\/cypher\/"},{"key":"e_1_2_1_10_1","unstructured":"DGraph 2021. DGraph: Not everything can fit in rows and columns. https:\/\/dgraph.io.  DGraph 2021. DGraph: Not everything can fit in rows and columns. https:\/\/dgraph.io."},{"key":"e_1_2_1_11_1","volume-title":"Powergraph: Distributed graph-parallel computation on natural graphs. In Presented as part of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI'12). 17--30.","author":"Gonzalez Joseph E","year":"2012","unstructured":"Joseph E Gonzalez , Yucheng Low , Haijie Gu , Danny Bickson , and Carlos Guestrin . 2012 . Powergraph: Distributed graph-parallel computation on natural graphs. In Presented as part of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI'12). 17--30. Joseph E Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. 2012. Powergraph: Distributed graph-parallel computation on natural graphs. In Presented as part of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI'12). 17--30."},{"key":"e_1_2_1_12_1","volume-title":"11th USENIX Symposium on Operating Systems Design and Implementation (OSDI'14)","author":"Gonzalez Joseph E","year":"2014","unstructured":"Joseph E Gonzalez , Reynold S Xin , Ankur Dave , Daniel Crankshaw , Michael J Franklin , and Ion Stoica . 2014 . Graphx: Graph processing in a distributed dataflow framework . In 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI'14) . 599--613. Joseph E Gonzalez, Reynold S Xin, Ankur Dave, Daniel Crankshaw, Michael J Franklin, and Ion Stoica. 2014. Graphx: Graph processing in a distributed dataflow framework. In 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI'14). 599--613."},{"key":"e_1_2_1_13_1","volume-title":"Graph Database Market Size, Share and Global Market Forecast to","author":"Annual DB","year":"2024","unstructured":"Graph DB Annual Growth 2021. Graph Database Market Size, Share and Global Market Forecast to 2024 . GraphDB Annual Growth 2021. Graph Database Market Size, Share and Global Market Forecast to 2024."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272996.1273005"},{"key":"e_1_2_1_15_1","unstructured":"Janusgraph 2021. JanusGraph: Distributed open source massively scalable graph database. https:\/\/janusgraph.org.  Janusgraph 2021. JanusGraph: Distributed open source massively scalable graph database. https:\/\/janusgraph.org."},{"key":"e_1_2_1_16_1","unstructured":"Janusgraph 2021. JanusGraph Transactions. https:\/\/docs.janusgraph.org\/basics\/transactions\/.  Janusgraph 2021. JanusGraph Transactions. https:\/\/docs.janusgraph.org\/basics\/transactions\/."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021937"},{"key":"e_1_2_1_18_1","volume-title":"Proc. VLDB Endow.","author":"Lai Longbin","year":"2019","unstructured":"Longbin Lai , Zhu Qing , Zhengyi Yang , Xin Jin , Zhengmin Lai , Ran Wang , Kongzhang Hao , Xuemin Lin , Lu Qin , Wenjie Zhang , Ying Zhang , Zhengping Qian , and Jingren Zhou . 2019 . Distributed Subgraph Matching on Timely Datalow . Proc. VLDB Endow. (2019). Longbin Lai, Zhu Qing, Zhengyi Yang, Xin Jin, Zhengmin Lai, Ran Wang, Kongzhang Hao, Xuemin Lin, Lu Qin, Wenjie Zhang, Ying Zhang, Zhengping Qian, and Jingren Zhou. 2019. Distributed Subgraph Matching on Timely Datalow. Proc. VLDB Endow. (2019)."},{"key":"e_1_2_1_19_1","unstructured":"LDBC Benchmark 2021. LDBC. http:\/\/ldbcouncil.org.  LDBC Benchmark 2021. LDBC. http:\/\/ldbcouncil.org."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522738"},{"key":"e_1_2_1_24_1","volume-title":"Proc. 8th ACM\/USENIX Symposium on Networked Systems Design and Implementation. 113--126","author":"Murray Derek G","year":"2011","unstructured":"Derek G Murray , Malte Schwarzkopf , Christopher Smowton , Steven Smith , Anil Madhavapeddy , and Steven Hand . 2011 . Ciel: a universal execution engine for distributed data-flow computing . In Proc. 8th ACM\/USENIX Symposium on Networked Systems Design and Implementation. 113--126 . Derek G Murray, Malte Schwarzkopf, Christopher Smowton, Steven Smith, Anil Madhavapeddy, and Steven Hand. 2011. Ciel: a universal execution engine for distributed data-flow computing. In Proc. 8th ACM\/USENIX Symposium on Networked Systems Design and Implementation. 113--126."},{"key":"e_1_2_1_25_1","unstructured":"Neo4j 2021. Neo4j Execution Plans. https:\/\/neo4j.com\/docs\/developer-manual\/3.0\/cypher\/execution-plans\/.  Neo4j 2021. Neo4j Execution Plans. https:\/\/neo4j.com\/docs\/developer-manual\/3.0\/cypher\/execution-plans\/."},{"key":"e_1_2_1_26_1","unstructured":"Neo4j 2021. Neo4j: The Fastest Path To Graph Success. https:\/\/neo4j.com.  Neo4j 2021. Neo4j: The Fastest Path To Graph Success. https:\/\/neo4j.com."},{"key":"e_1_2_1_27_1","unstructured":"Neptune 2021. AWS Neptune. https:\/\/aws.amazon.com\/neptune\/.  Neptune 2021. AWS Neptune. https:\/\/aws.amazon.com\/neptune\/."},{"key":"e_1_2_1_28_1","unstructured":"Neptune 2021. Query queuing in Amazon Neptune. https:\/\/docs.aws.amazon.com\/neptune\/latest\/userguide\/access-graph-queuing.html.  Neptune 2021. Query queuing in Amazon Neptune. https:\/\/docs.aws.amazon.com\/neptune\/latest\/userguide\/access-graph-queuing.html."},{"key":"e_1_2_1_29_1","volume-title":"Berkeley DB 2017","author":"Oracle","year":"2021","unstructured":"Oracle Berkeley DB 2017 . BerkeleyJE 7.5.11. Retrieved Dec 20, 2021 from https:\/\/docs.oracle.com\/cd\/E17277_02\/html\/index.html Oracle Berkeley DB 2017. BerkeleyJE 7.5.11. Retrieved Dec 20, 2021 from https:\/\/docs.oracle.com\/cd\/E17277_02\/html\/index.html"},{"key":"e_1_2_1_30_1","volume-title":"Berkeley DB","author":"Oracle","year":"2021","unstructured":"Oracle Berkeley DB 2021 . BerkeleyDB 18.1.32. https:\/\/www.oracle.com\/database\/technologies\/related\/berkeleydb-downloads.html. Oracle Berkeley DB 2021. BerkeleyDB 18.1.32. https:\/\/www.oracle.com\/database\/technologies\/related\/berkeleydb-downloads.html."},{"key":"e_1_2_1_31_1","unstructured":"OrientDB 2021. OrientDB. https:\/\/www.orientdb.org.  OrientDB 2021. OrientDB. https:\/\/www.orientdb.org."},{"key":"e_1_2_1_32_1","volume-title":"18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21)","author":"Qian Zhengping","year":"2021","unstructured":"Zhengping Qian , Chenqiang Min , 2021 . GAIA: A System for Interactive Analysis on Distributed Graphs Using a High-Level Language . In 18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21) . USENIX Association. Zhengping Qian, Chenqiang Min, et al. 2021. GAIA: A System for Interactive Analysis on Distributed Graphs Using a High-Level Language. In 18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21). USENIX Association."},{"key":"e_1_2_1_33_1","volume-title":"Fast and robust distributed subgraph enumeration. arXiv preprint","author":"Ren Xuguang","year":"2019","unstructured":"Xuguang Ren , Junhu Wang , Wook-Shin Han , and Jeffrey Xu Yu. 2019. Fast and robust distributed subgraph enumeration. arXiv preprint ( 2019 ). Xuguang Ren, Junhu Wang, Wook-Shin Han, and Jeffrey Xu Yu. 2019. Fast and robust distributed subgraph enumeration. arXiv preprint (2019)."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2396806"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2467799"},{"key":"e_1_2_1_36_1","volume-title":"12th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 16). 317--332.","author":"Shi Jiaxin","unstructured":"Jiaxin Shi , Youyang Yao , Rong Chen , Haibo Chen , and Feifei Li. 2016. Fast and concurrent {RDF} queries with RDMA-based distributed graph exploration . In 12th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 16). 317--332. Jiaxin Shi, Youyang Yao, Rong Chen, Haibo Chen, and Feifei Li. 2016. Fast and concurrent {RDF} queries with RDMA-based distributed graph exploration. In 12th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 16). 317--332."},{"key":"e_1_2_1_37_1","volume-title":"Proc. VLDB Endow.","author":"Sun Shixuan","year":"2020","unstructured":"Shixuan Sun , Xibo Sun , Yulin Che , Qiong Luo , and Bingsheng He . 2020 . Rapid-Match: A Holistic Approach to Subgraph Query Processing . Proc. VLDB Endow. (2020). Shixuan Sun, Xibo Sun, Yulin Che, Qiong Luo, and Bingsheng He. 2020. Rapid-Match: A Holistic Approach to Subgraph Query Processing. Proc. VLDB Endow. (2020)."},{"key":"e_1_2_1_38_1","unstructured":"The SNAP datasets 2022. Stanford SNAP. http:\/\/snap.stanford.edu\/data\/index.  The SNAP datasets 2022. Stanford SNAP. http:\/\/snap.stanford.edu\/data\/index."},{"key":"e_1_2_1_39_1","unstructured":"TigerGraph 2021. TigerGraph 3.1.0. https:\/\/www.tigergraph.com.  TigerGraph 2021. TigerGraph 3.1.0. https:\/\/www.tigergraph.com."},{"key":"e_1_2_1_40_1","unstructured":"Tinkerpop 2021. Apache Tinkerpop. http:\/\/tinkerpop.apache.org\/.  Tinkerpop 2021. Apache Tinkerpop. http:\/\/tinkerpop.apache.org\/."},{"key":"e_1_2_1_41_1","volume-title":"Retrieved","author":"Tinkerpopo","year":"2021","unstructured":"Tinkerpopo 2021 . Tinkerpopo Threaded Transactions . Retrieved Dec 20, 2021 from http:\/\/tinkerpop.apache.org\/docs\/current\/reference\/#_threaded_transactions Tinkerpopo 2021. Tinkerpopo Threaded Transactions. Retrieved Dec 20, 2021 from http:\/\/tinkerpop.apache.org\/docs\/current\/reference\/#_threaded_transactions"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00021"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/2904483.2904488"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457237"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535570.2488333"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920887"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3547305.3547311","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:11:54Z","timestamp":1672225914000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3547305.3547311"}},"subtitle":["a scoped dataflow engine for graph query service"],"short-title":[],"issued":{"date-parts":[[2022,6]]},"references-count":45,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["10.14778\/3547305.3547311"],"URL":"https:\/\/doi.org\/10.14778\/3547305.3547311","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,6]]}}}