{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T04:10:56Z","timestamp":1767845456564,"version":"3.49.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,10]]},"abstract":"<jats:p>\n            Subgraph matching finds a set\n            <jats:italic>I<\/jats:italic>\n            of all occurrences of a pattern graph in a target graph. It has a wide range of applications while suffers an expensive computation. This efficiency issue has been studied extensively. All existing approaches, however, turn a blind eye to the\n            <jats:italic>output crisis<\/jats:italic>\n            , that is, when the system has to materialize\n            <jats:italic>I<\/jats:italic>\n            as a preprocessing\/intermediate\/final result or an index, the cost of the export of\n            <jats:italic>I<\/jats:italic>\n            dominates the overall cost, which could be prohibitive even for a small pattern graph.\n          <\/jats:p>\n          <jats:p>\n            This paper studies subgraph matching via two problems. 1) Is there an ideal compression of\n            <jats:italic>I<\/jats:italic>\n            ? 2) Will the compression of\n            <jats:italic>I<\/jats:italic>\n            reversely boost the computation of\n            <jats:italic>I<\/jats:italic>\n            ? For the problem 1), we propose a technique called VCBC to compress\n            <jats:italic>I<\/jats:italic>\n            to code (\n            <jats:italic>I<\/jats:italic>\n            ) which serves effectively the same as\n            <jats:italic>I.<\/jats:italic>\n            For problem 2), we propose a subgraph matching computation framework CBF which computes code(\n            <jats:italic>I<\/jats:italic>\n            )instead of\n            <jats:italic>I<\/jats:italic>\n            to bring down the output cost. CBF further reduces the overall cost by reducing the intermediate results. Extensive experiments show that the compression ratio of VCBC can be up to 10\n            <jats:sup>5<\/jats:sup>\n            which also significantly lowers the output cost of CBF. Extensive experiments show the superior performance of CBF over existing approaches.\n          <\/jats:p>","DOI":"10.14778\/3149193.3149198","type":"journal-article","created":{"date-parts":[[2017,12,12]],"date-time":"2017-12-12T18:33:38Z","timestamp":1513103618000},"page":"176-188","source":"Crossref","is-referenced-by-count":66,"title":["Subgraph matching"],"prefix":"10.14778","volume":"11","author":[{"given":"Miao","family":"Qiao","sequence":"first","affiliation":[{"name":"Massey University, New Zealand"}]},{"given":"Hao","family":"Zhang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong"}]},{"given":"Hong","family":"Cheng","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong"}]}],"member":"320","published-online":{"date-parts":[[2017,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544814"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535570.2488334"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/29601.29641"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btn163"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1038\/nrg2102"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915236"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142388"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020513"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1050985"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_1_12_1","volume-title":"Introduction to Graph Theory","author":"Douglas W. B.","year":"2000","unstructured":"W. B. Douglas . Introduction to Graph Theory . Prentice Hall , 2 edition, 9 2000 . W. B. Douglas. Introduction to Graph Theory. Prentice Hall, 2 edition, 9 2000."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.44"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213855"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71681-5_7"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.05.005"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2691190.2691193"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2124295.2124374"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915209"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794368"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021937"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448946"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/11731139_44"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213565"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142384"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594552"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939757"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735493"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588557"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13040-014-0029-x"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3149193.3149198","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:33:07Z","timestamp":1672219987000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3149193.3149198"}},"subtitle":["on compression and computation"],"short-title":[],"issued":{"date-parts":[[2017,10]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["10.14778\/3149193.3149198"],"URL":"https:\/\/doi.org\/10.14778\/3149193.3149198","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2017,10]]}}}