{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T04:44:21Z","timestamp":1768106661791,"version":"3.49.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T00:00:00Z","timestamp":1685059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,5,26]]},"abstract":"<jats:p>Subgraph matching is one of the most important problems in graph analytics. Many algorithms and systems have been proposed for subgraph matching. Most of these works follow Ullmann's backtracking approach as it is memory-efficient in handling an explosive number of intermediate matching results. However, they have largely overlooked an intrinsic problem of backtracking, namely repeated computation, which contributes to a large portion of the heavy computation in subgraph matching. This paper proposes a subgraph matching system, Circinus, which enables effective computation sharing by a new compression-based backtracking method. Our extensive experiments show that Circinus significantly reduces repeated computation, which transfers to up to several orders of magnitude performance improvement.<\/jats:p>","DOI":"10.1145\/3588692","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T17:42:05Z","timestamp":1685468525000},"page":"1-26","source":"Crossref","is-referenced-by-count":25,"title":["Circinus: Fast Redundancy-Reduced Subgraph Matching"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7596-1146","authenticated-orcid":false,"given":"Tatiana","family":"Jin","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong &amp; Kasma Pte Ltd., Hong Kong, Hong Kong"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7572-5653","authenticated-orcid":false,"given":"Boyang","family":"Li","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, Hong Kong"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4657-0901","authenticated-orcid":false,"given":"Yichao","family":"Li","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong &amp; Kasma Pte Ltd., Hong Kong, Hong Kong"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8927-3325","authenticated-orcid":false,"given":"Qihui","family":"Zhou","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, Hong Kong"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-6086-764X","authenticated-orcid":false,"given":"Qianli","family":"Ma","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, Hong Kong"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5486-331X","authenticated-orcid":false,"given":"Yunjian","family":"Zhao","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, Hong Kong"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0085-3463","authenticated-orcid":false,"given":"Hongzhi","family":"Chen","sequence":"additional","affiliation":[{"name":"Kasma Pte Ltd., Singapore, Singapore"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6313-6288","authenticated-orcid":false,"given":"James","family":"Cheng","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, Hong Kong"}]}],"member":"320","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/3184470.3184473"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300086"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915236"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471--2105--14-S7-S13"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920873"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357223.3362715"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3190508.3190545"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389137"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_2_10_1","volume-title":"Lee","author":"Deutsch Alin","year":"2019","unstructured":"Alin Deutsch, Yu Xu, Mingxi Wu, and Victor E. Lee. 2019. TigerGraph: A Native MPP Graph Database. CoRR, Vol. abs\/1901.08248 (2019). showeprint[arXiv]1901.08248 http:\/\/arxiv.org\/abs\/1901.08248"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319875"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389699"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3035564"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319880"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465300"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376660"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3342195.3387548"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.02.018"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056445"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457265"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021937"},{"key":"e_1_2_2_22_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3469379.3469383"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359633"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342643"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149198"},{"key":"e_1_2_2_29_1","unstructured":"RedisLabs. 2021. RedisGraph - a graph database module for Redis. https:\/\/oss.redislabs.com\/redisgraph\/"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735493"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-016-0968--2"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164139"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453899"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC41405.2020.00104"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467--9531.2006.00176.x"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380581"},{"key":"e_1_2_2_37_1","unstructured":"The Neo4J Team. 2021. Neo4J. https:\/\/neo4j.com\/"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815410"},{"key":"e_1_2_2_39_1","volume-title":"2021 USENIX Annual Technical Conference, USENIX ATC 2021","author":"Trigonakis Vasileios","year":"2021","unstructured":"Vasileios Trigonakis, Jean-Pierre Lozi, Tom\u00e1 s Falt'i n, Nicholas P. Roth, Iraklis Psaroudakis, Arnaud Delamare, Vlad Haprian, Calin Iorgulescu, Petr Koupy, Jinsoo Lee, Sungpack Hong, and Hassan Chafi. 2021. aDFS: An Almost Depth-First-Search Distributed Graph-Querying System. In 2021 USENIX Annual Technical Conference, USENIX ATC 2021, July 14--16, 2021, Irina Calciu and Geoff Kuenning (Eds.). USENIX Association, 209--224. https:\/\/www.usenix.org\/conference\/atc21\/presentation\/trigonakis"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_2_41_1","volume-title":"Leapfrog Triejoin: a worst-case optimal join algorithm. CoRR","author":"Veldhuizen Todd L.","year":"2012","unstructured":"Todd L. Veldhuizen. 2012. Leapfrog Triejoin: a worst-case optimal join algorithm. CoRR, Vol. abs\/1210.0481 (2012). arxiv: 1210.0481 http:\/\/arxiv.org\/abs\/1210.0481"},{"key":"e_1_2_2_42_1","volume-title":"RStream: Marrying Relational Algebra with Streaming for Efficient Graph Mining on A Single Machine. In 13th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2018","author":"Wang Kai","year":"2018","unstructured":"Kai Wang, Zhiqiang Zuo, John Thorpe, Tien Quang Nguyen, and Guoqing Harry Xu. 2018. RStream: Marrying Relational Algebra with Streaming for Efficient Graph Mining on A Single Machine. In 13th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2018, Carlsbad, CA, USA, October 8--10, 2019, Andrea C. Arpaci-Dusseau and Geoff Voelker (Eds.). USENIX Association, 763--782. https:\/\/www.usenix.org\/conference\/osdi18\/presentation\/wang"},{"key":"e_1_2_2_43_1","volume-title":"The Free Encyclopedia. https:\/\/en.wikipedia.org\/w\/index.php?title=Box_plot&oldid=1059408900 [Online","author":"Wikipedia","year":"2021","unstructured":"Wikipedia contributors. 2021. Box plot -- Wikipedia, The Free Encyclopedia. https:\/\/en.wikipedia.org\/w\/index.php?title=Box_plot&oldid=1059408900 [Online; accessed 11-December-2021]."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00122"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007607"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457237"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920887"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588692","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588692","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:13Z","timestamp":1750178833000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588692"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588692"],"URL":"https:\/\/doi.org\/10.1145\/3588692","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}