{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T23:24:11Z","timestamp":1777937051519,"version":"3.51.4"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,6,2]],"date-time":"2021-06-02T00:00:00Z","timestamp":1622592000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGOPS Oper. Syst. Rev."],"published-print":{"date-parts":[[2021,6,2]]},"abstract":"<jats:p>Subgraph matching is a fundamental task in many applications which identifies all the embeddings of a query pattern in an input graph. Compilation-based subgraph matching systems generate specialized implementations for the provided patterns and often substantially outperform other systems. However, the generated code causes significant computation redundancy and the compilation process incurs too much overhead to be used online, both due to the inherent symmetry in the structure of the query pattern.<\/jats:p>\n          <jats:p>In this paper, we propose an optimizing query compiler, named GraphZero, to completely address these limitations through symmetry breaking based on group theory. GraphZero implements three novel techniques. First, its schedule explorer efficiently prunes the schedule space without missing any high-performance schedule. Second, it automatically generates and enforces a set of restrictions to eliminate computation redundancy. Third, it generalizes orientation, a surprisingly effective optimization that was only used for clique patterns, to apply to arbitrary patterns. Evaluation on multiple query patterns shows that GraphZero outperforms two state-of-the-art compilation and non-compilation based systems by up to 40X and 2654X, respectively.<\/jats:p>","DOI":"10.1145\/3469379.3469383","type":"journal-article","created":{"date-parts":[[2021,6,6]],"date-time":"2021-06-06T12:43:56Z","timestamp":1622983436000},"page":"21-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":45,"title":["GraphZero"],"prefix":"10.1145","volume":"55","author":[{"given":"Daniel","family":"Mawhirter","sequence":"first","affiliation":[{"name":"Colorado School of Mines"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sam","family":"Reinehr","sequence":"additional","affiliation":[{"name":"Colorado School of Mines"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Connor","family":"Holmes","sequence":"additional","affiliation":[{"name":"Colorado School of Mines"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tongping","family":"Liu","sequence":"additional","affiliation":[{"name":"University of Massachusetts at Amherst"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bo","family":"Wu","sequence":"additional","affiliation":[{"name":"Colorado School of Mines"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,6]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"November 22","year":"2019"},{"key":"e_1_2_1_2_1","volume-title":"November 22","author":"Orkut","year":"2019"},{"key":"e_1_2_1_3_1","volume-title":"Emptyheaded: A relational engine for graph processing. ACM Transactions on Database Systems (TODS), 42(4):20","author":"Aberger C. R.","year":"2017"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.141"},{"key":"e_1_2_1_5_1","volume-title":"Graph-based anomaly detection and description: A survey. CoRR, abs\/1404.4679","author":"Akoglu L.","year":"2014"},{"issue":"6","key":"e_1_2_1_6_1","first-page":"691","article-title":"Distributed evaluation of subgraph queries using worstcase optimal and low-memory dataflows","volume":"11","author":"Ammar K.","year":"2018","journal-title":"PVLDB"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150412"},{"key":"e_1_2_1_8_1","first-page":"1447","volume-title":"Proceedings of the 2019 International Conference on Management of Data, SIGMOD Conference 2019","author":"Bhattarai B.","year":"2019"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3190508.3190545"},{"key":"e_1_2_1_12_1","first-page":"157","volume-title":"Proceedings of the 18th International Conference on Extending Database Technology, EDBT 2015","author":"Choudhury S.","year":"2015"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382577.2382581"},{"key":"e_1_2_1_14_1","first-page":"1357","volume-title":"Proceedings of the 2019 International Conference on Management of Data, SIGMOD Conference 2019","author":"dos Santos Dias V. V.","year":"2019"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732286.2732289"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96983-1_18"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3297753.3297754"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1758222.1758229"},{"key":"e_1_2_1_19_1","first-page":"1429","volume-title":"Proceedings of the 2019 International Conference on Management of Data, SIGMOD Conference 2019","author":"Han M.","year":"2019"},{"key":"e_1_2_1_20_1","first-page":"1429","volume-title":"Proceedings of the 2019 International Conference on Management of Data, SIGMOD Conference 2019","author":"Han M.","year":"2019"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465300"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btt717"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2189750.2151013"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2018.00017"},{"key":"e_1_2_1_25_1","first-page":"745","volume-title":"13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18)","author":"Iyer A. P.","year":"2018"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056445"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1997.1404"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2907294.2907312"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_30_1","first-page":"31","volume-title":"Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI'12","author":"Kyrola A.","year":"2012"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021937"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"M. Latapy. Main-memory triangle computations for very large (sparse (power-law)) graphs. Theor. Comput. Sci. 407(1--3):458--473 2008.  M. Latapy. Main-memory triangle computations for very large (sparse (power-law)) graphs. Theor. Comput. Sci. 407(1--3):458--473 2008.","DOI":"10.1016\/j.tcs.2008.07.017"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772756"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359633"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCGRID.2018.00080"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450342480"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983990.2984015"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149198"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522740"},{"key":"e_1_2_1_43_1","first-page":"278","volume-title":"2013 IEEE 29th International Conference on Data Engineering (ICDE)","author":"Seo J.","year":"2013"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588557"},{"key":"e_1_2_1_45_1","first-page":"317","volume-title":"12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016","author":"Shi J.","year":"2016"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113280"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00029"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311907"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815410"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2017.8091037"},{"key":"e_1_2_1_52_1","first-page":"507","volume-title":"2016 USENIX Annual Technical Conference (USENIX ATC 16)","author":"Vora K.","year":"2016"},{"key":"e_1_2_1_53_1","first-page":"763","volume-title":"13th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2018","author":"Wang K.","year":"2018"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00021"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl038"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2018.8508729"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3173162.3173208"},{"key":"e_1_2_1_58_1","first-page":"1","article-title":"Graphit: a high-performance graph DSL","volume":"121","author":"Zhang Y.","year":"2018","journal-title":"PACMPL, 2(OOPSLA)"},{"key":"e_1_2_1_59_1","volume-title":"Kaleido: An efficient out-of-core graph mining system on A single machine. CoRR, abs\/1905.09572","author":"Zhao C.","year":"2019"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2018.00100"},{"key":"e_1_2_1_61_1","first-page":"301","volume-title":"12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16)","author":"Zhu X.","year":"2016"},{"key":"e_1_2_1_62_1","first-page":"375","volume-title":"2015 USENIX Annual Technical Conference (USENIX ATC 15)","author":"Zhu X.","year":"2015"}],"container-title":["ACM SIGOPS Operating Systems Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3469379.3469383","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3469379.3469383","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:23Z","timestamp":1750195703000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3469379.3469383"}},"subtitle":["A High-Performance Subgraph Matching System"],"short-title":[],"issued":{"date-parts":[[2021,6,2]]},"references-count":62,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,6,2]]}},"alternative-id":["10.1145\/3469379.3469383"],"URL":"https:\/\/doi.org\/10.1145\/3469379.3469383","relation":{},"ISSN":["0163-5980"],"issn-type":[{"value":"0163-5980","type":"print"}],"subject":[],"published":{"date-parts":[[2021,6,2]]},"assertion":[{"value":"2021-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}