{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T17:06:05Z","timestamp":1790787965748,"version":"4.1.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2024,12,18]],"date-time":"2024-12-18T00:00:00Z","timestamp":1734480000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"the National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62472156, U23A20317, 62172146"],"award-info":[{"award-number":["62472156, U23A20317, 62172146"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"the Creative Research Groups Program of the National Natural Science Foundation of China","award":["62321003"],"award-info":[{"award-number":["62321003"]}]},{"DOI":"10.13039\/501100004761","name":"the Natural Science Foundation of Hunan Province","doi-asserted-by":"crossref","award":["2023JJ10016"],"award-info":[{"award-number":["2023JJ10016"]}],"id":[{"id":"10.13039\/501100004761","id-type":"DOI","asserted-by":"crossref"}]},{"name":"the Key R\\&D Program of Hunan Province","award":["2023GK2002"],"award-info":[{"award-number":["2023GK2002"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,12,18]]},"abstract":"<jats:p>\n                    Graph pattern query is a powerful tool for extracting crucial information from property graphs. With the exponential growth of sizes, property graphs are typically divided into multiple subgraphs (referred to as\n                    <jats:italic toggle=\"yes\">partitions<\/jats:italic>\n                    ) and stored across various sites in distributed environments. Existing graph partitioning methods have not been efficiently optimized for pattern queries, resulting in numerous query matches across multiple partitions, called\n                    <jats:italic toggle=\"yes\">crossing matches.<\/jats:italic>\n                    Identifying these matches requires much inter-partition communication, which is the primary performance bottleneck in distributed query processing. To address this issue, this paper introduces a novel connectivity-oriented relationship-disjoint partitioning method, namely RCP (Relationship Connectivity Partitioning), aimed at enhancing the efficiency of graph pattern query processing by reducing crossing matches. By employing each weakly connected component of the subgraph, which is induced by different relationship labels, as a basic unit of partition, RCP ensures that matches for both\n                    <jats:italic toggle=\"yes\">variable-length path<\/jats:italic>\n                    and\n                    <jats:italic toggle=\"yes\">labeled graph pattern<\/jats:italic>\n                    queries are not crossing matches. Here,\n                    <jats:italic toggle=\"yes\">variable-length path<\/jats:italic>\n                    and\n                    <jats:italic toggle=\"yes\">labeled graph pattern<\/jats:italic>\n                    are two common components in graph pattern queries to identify paths meeting specific label constraints and retrieve subgraphs with consistent relationship types, respectively. Moreover, in the query processing phase, we further demonstrate that all graph pattern queries, belonging to these two basic queries or their extensions, can be executed independently under RCP, thereby avoiding crossing matches. In experiments, we implemented two prototype distributed property graph systems based on Neo4j and JanusGraph, which use declarative and functional query language, respectively. Experimental results on billion-scale datasets demonstrate that our approach brings a performance improvement of nearly two orders of magnitude over state-of-the-art partitioning methods.\n                  <\/jats:p>","DOI":"10.1145\/3698804","type":"journal-article","created":{"date-parts":[[2024,12,20]],"date-time":"2024-12-20T16:40:35Z","timestamp":1734712835000},"page":"1-26","source":"Crossref","is-referenced-by-count":3,"title":["Connectivity-Oriented Property Graph Partitioning for Distributed Graph Pattern Query Processing"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-1492-9697","authenticated-orcid":false,"given":"Min","family":"Shi","sequence":"first","affiliation":[{"name":"Hunan University, Changsha, Hunan, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8095-8061","authenticated-orcid":false,"given":"Peng","family":"Peng","sequence":"additional","affiliation":[{"name":"Hunan University, Changsha, Hunan, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1400-8375","authenticated-orcid":false,"given":"Xu","family":"Zhou","sequence":"additional","affiliation":[{"name":"Hunan University, Changsha, Hunan, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-8731-761X","authenticated-orcid":false,"given":"Jiayu","family":"Liu","sequence":"additional","affiliation":[{"name":"Hunan University, Changsha, Hunan, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5008-4829","authenticated-orcid":false,"given":"Guoqing","family":"Xiao","sequence":"additional","affiliation":[{"name":"Hunan University, Changsha, Hunan, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2635-7716","authenticated-orcid":false,"given":"Kenli","family":"Li","sequence":"additional","affiliation":[{"name":"Hunan University, Changsha, Hunan, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,12,20]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Daniel J. Abadi Adam Marcus Samuel R. Madden and Kate Hollenbach. 2007. Scalable Semantic Web Data Management Using Vertical Partitioning. In VLDB. VLDB Endowment 411--422."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3104031"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.2993117"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623660"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526057"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5486\/PMD.1959.6.3-4.12"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742786"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476369"},{"key":"e_1_2_1_9_1","first-page":"1","article-title":"Application-Driven Graph Partitioning","volume":"32","author":"Fan Wenfei","year":"2022","unstructured":"Wenfei Fan, Ruiqi Xu, Qiang Yin, Wenyuan Yu, and Jingren Zhou. 2022. Application-Driven Graph Partitioning. The VLDB Journal, Vol. 32, 1 (apr 2022), 149--172.","journal-title":"The VLDB Journal"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.24963\/kr.2020\/38"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190657"},{"key":"e_1_2_1_12_1","volume-title":"GraphX: Graph Processing in a Distributed Dataflow Framework","author":"Gonzalez Joseph E.","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 OSDI. USENIX Association, USA, 599--613."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3358701.3358706"},{"key":"e_1_2_1_14_1","volume-title":"PatMat: A Distributed Pattern Matching Engine with Cypher","author":"Hao Kongzhang","unstructured":"Kongzhang Hao, Zhengyi Yang, Longbin Lai, Zhengmin Lai, Xin Jin, and Xuemin Lin. 2019. PatMat: A Distributed Pattern Matching Engine with Cypher. In CIKM. Association for Computing Machinery, New York, NY, USA, 2921--2924."},{"key":"e_1_2_1_15_1","unstructured":"JanusGraph. 2023. Distributed open source massively scalable graph database. http:\/\/janusgraph.org\/"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3466685"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3078447.3078450"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.3233\/SW-140134"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824046"},{"key":"e_1_2_1_22_1","volume-title":"Spinner: Scalable Graph Partitioning in the Cloud. In 2017 IEEE 33rd International Conference on Data Engineering (ICDE). 1083--1094","author":"Martella Claudio","year":"2017","unstructured":"Claudio Martella, Dionysios Logothetis, Andreas Loukas, and Georgos Siganos. 2017. Spinner: Scalable Graph Partitioning in the Cloud. In 2017 IEEE 33rd International Conference on Data Engineering (ICDE). 1083--1094."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00242"},{"key":"e_1_2_1_24_1","unstructured":"Neo4j. 2024. The world's leading graph database as a fully-managed cloud service - zero-admin globally available and always-on. https:\/\/neo4j.com\/"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Haohan Pang Peng Gan Pingpeng Yuan Hai Jin and Qiangsheng Hua. 2019. Partitioning Large-Scale Property Graph for Efficient Distributed Query Processing. In HPCC\/SmartCity\/DSS. 1643--1650.","DOI":"10.1109\/HPCC\/SmartCity\/DSS.2019.00225"},{"key":"e_1_2_1_26_1","volume-title":"MPC: Minimum Property-Cut RDF Graph Partitioning. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). 192--204","author":"Peng Peng","year":"2022","unstructured":"Peng Peng, M. Tamer \u00d6zsu, Lei Zou, Cen Yan, and Chengjun Liu. 2022. MPC: Minimum Property-Cut RDF Graph Partitioning. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). 192--204."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806424"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815072.2815073"},{"key":"e_1_2_1_29_1","volume-title":"Chaos: Scale-out Graph Processing from Secondary Storage","author":"Roy Amitabha","year":"2015","unstructured":"Amitabha Roy, Laurent Bindschaedler, Jasmina Malicevic, and Willy Zwaenepoel. 2015. Chaos: Scale-out Graph Processing from Secondary Storage. In SOSP. Association for Computing Machinery, New York, NY, USA, 410--424."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434642"},{"key":"e_1_2_1_31_1","volume-title":"Sempala: Interactive SPARQL Query Processing on Hadoop","author":"Sch\u00e4tzle Alexander","year":"2014","unstructured":"Alexander Sch\u00e4tzle, Martin Przyjaciel-Zablocki, Antony Neu, and Georg Lausen. 2014. Sempala: Interactive SPARQL Query Processing on Hadoop. In ISWC. Springer-Verlag, Berlin, Heidelberg, 164--179."},{"key":"e_1_2_1_32_1","first-page":"10","article-title":"S2RDF","volume":"9","author":"Sch\u00e4tzle Alexander","year":"2016","unstructured":"Alexander Sch\u00e4tzle, Martin Przyjaciel-Zablocki, Simon Skilevic, and Georg Lausen. 2016. S2RDF: RDF Querying with SPARQL on Spark. Proc. VLDB Endow., Vol. 9, 10 (jun 2016), 804--815.","journal-title":"RDF Querying with SPARQL on Spark. Proc. VLDB Endow."},{"key":"e_1_2_1_33_1","volume-title":"Trinity: A Distributed Graph Engine on a Memory Cloud","author":"Shao Bin","year":"2013","unstructured":"Bin Shao, Haixun Wang, and Yatao Li. 2013. Trinity: A Distributed Graph Engine on a Memory Cloud. In SIGMOD. Association for Computing Machinery, New York, NY, USA, 505--516."},{"key":"e_1_2_1_34_1","volume-title":"Sparklify: A Scalable Software Component for Efficient Evaluation of SPARQL Queries over Distributed RDF Datasets","author":"Stadler Claus","year":"2019","unstructured":"Claus Stadler, Gezim Sejdiu, Damien Graux, and Jens Lehmann. 2019. Sparklify: A Scalable Software Component for Efficient Evaluation of SPARQL Queries over Distributed RDF Datasets. In ISWC. Springer-Verlag, Berlin, Heidelberg, 293--308."},{"key":"e_1_2_1_35_1","volume-title":"SQLGraph: An Efficient Relational-Based Property Graph Store","author":"Sun Wen","year":"1887","unstructured":"Wen Sun, Achille Fokoue, Kavitha Srinivas, Anastasios Kementsietsidis, Gang Hu, and Guotong Xie. 2015. SQLGraph: An Efficient Relational-Based Property Graph Store. In SIGMOD. Association for Computing Machinery, New York, NY, USA, 1887--1901."},{"key":"e_1_2_1_36_1","volume-title":"Nebula Graph: An open source distributed graph database. arxiv: 2206.07278 [cs.DB]","author":"Wu Min","year":"2022","unstructured":"Min Wu, Xinglu Yi, Hui Yu, Yu Liu, and Yujue Wang. 2022. Nebula Graph: An open source distributed graph database. arxiv: 2206.07278 [cs.DB]"},{"key":"e_1_2_1_37_1","volume-title":"Distributed Power-Law Graph Computing: Theoretical and Empirical Analysis","author":"Xie Cong","unstructured":"Cong Xie, Ling Yan, Wu-Jun Li, and Zhihua Zhang. 2014. Distributed Power-Law Graph Computing: Theoretical and Empirical Analysis. In NIPS. MIT Press, Cambridge, MA, USA, 1673--1681."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781009122115"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00193"},{"key":"e_1_2_1_40_1","volume-title":"Zhihao Gavin Tang, and Zhenguo Li","author":"Zhang Chenzi","year":"2017","unstructured":"Chenzi Zhang, Fan Wei, Qin Liu, Zhihao Gavin Tang, and Zhenguo Li. 2017. Graph Edge Partitioning via Neighborhood Heuristic. In SIGKDD. Association for Computing Machinery, New York, NY, USA, 605--614."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544856"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687727"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3698804","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3698804","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T17:47:03Z","timestamp":1774979223000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3698804"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,18]]},"references-count":42,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12,18]]}},"alternative-id":["10.1145\/3698804"],"URL":"https:\/\/doi.org\/10.1145\/3698804","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,18]]}}}