{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T18:55:34Z","timestamp":1771700134471,"version":"3.50.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,1]]},"abstract":"\n Driven by many real applications, graph pattern matching has attracted a great deal of attention recently. Consider that a twig-pattern matching may result in an extremely large number of matches in a graph; this may not only confuse users by providing too many results but also lead to high computational costs. In this paper, we study the problem of top-\n k<\/jats:italic>\n tree pattern matching; that is, given a rooted tree\n T<\/jats:italic>\n , compute its top-\n k<\/jats:italic>\n matches in a directed graph\n G<\/jats:italic>\n based on the twig-pattern matching semantics. We firstly present a novel and optimal enumeration paradigm based on the principle of Lawler's procedure. We show that our enumeration algorithm runs in\n O<\/jats:italic>\n (\n n<\/jats:italic>\n \n T<\/jats:italic>\n <\/jats:sub>\n + log\n k<\/jats:italic>\n ) time in each round where\n n<\/jats:italic>\n \n T<\/jats:italic>\n <\/jats:sub>\n is the number of nodes in\n T.<\/jats:italic>\n Considering that the time complexity to output a match of\n T<\/jats:italic>\n is\n O<\/jats:italic>\n (\n n<\/jats:italic>\n \n T<\/jats:italic>\n <\/jats:sub>\n ) and\n n<\/jats:italic>\n \n T<\/jats:italic>\n <\/jats:sub>\n \u2265 log\n k<\/jats:italic>\n in practice, our enumeration technique is optimal. Moreover, the cost of generating top-1 match of\n T<\/jats:italic>\n in our algorithm is\n O<\/jats:italic>\n (\n m<\/jats:italic>\n \n R<\/jats:italic>\n <\/jats:sub>\n ) where\n m<\/jats:italic>\n \n R<\/jats:italic>\n <\/jats:sub>\n is the number of edges in the transitive closure of a data graph\n G<\/jats:italic>\n involving all relevant nodes to\n T. O<\/jats:italic>\n (\n m<\/jats:italic>\n \n R<\/jats:italic>\n <\/jats:sub>\n ) is also optimal in the worst case without pre-knowledge of\n G.<\/jats:italic>\n Consequently, our algorithm is optimal with the running time\n O<\/jats:italic>\n (\n m<\/jats:italic>\n \n R<\/jats:italic>\n <\/jats:sub>\n +\n k<\/jats:italic>\n (\n n<\/jats:italic>\n \n T<\/jats:italic>\n <\/jats:sub>\n + log\n k<\/jats:italic>\n )) in contrast to the time complexity\n O<\/jats:italic>\n (\n m<\/jats:italic>\n \n R<\/jats:italic>\n <\/jats:sub>\n log\n k<\/jats:italic>\n +\n kn<\/jats:italic>\n \n T<\/jats:italic>\n <\/jats:sub>\n (log\n k<\/jats:italic>\n +\n d<\/jats:italic>\n \n T<\/jats:italic>\n <\/jats:sub>\n )) of the existing technique where\n d<\/jats:italic>\n \n T<\/jats:italic>\n <\/jats:sub>\n is the maximal node degree in\n T.<\/jats:italic>\n Secondly, a novel priority based access technique is proposed, which greatly reduces the number of edges accessed and results in a significant performance improvement. Finally, we apply our techniques to the general form of top-\n k<\/jats:italic>\n graph pattern matching problem (i.e., query is a graph) to improve the existing techniques. Comprehensive empirical studies demonstrate that our techniques may improve the existing techniques by orders of magnitude.\n <\/jats:p>","DOI":"10.14778\/2735479.2735486","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"533-544","source":"Crossref","is-referenced-by-count":16,"title":["Optimal enumeration"],"prefix":"10.14778","volume":"8","author":[{"given":"Lijun","family":"Chang","sequence":"first","affiliation":[{"name":"University of New South Wales, Australia"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"East China Normal University, China and University of New South Wales, Australia"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of New South Wales, Australia"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, China"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Technology, Sydney, Australia"}]},{"given":"Lu","family":"Qin","sequence":"additional","affiliation":[{"name":"University of Technology, Sydney, Australia"}]}],"member":"320","published-online":{"date-parts":[[2015,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/876875.879034"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564727"},{"key":"e_1_2_1_4_1","first-page":"17","author":"Chang L.","year":"2014","journal-title":"Optimal enumeration: Efficient top-k tree matching. In UNSW-CSE-TR-"},{"key":"e_1_2_1_5_1","volume-title":"Proc. of VLDB'05","author":"Chen L.","year":"2005"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497500"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544895"},{"key":"e_1_2_1_8_1","volume-title":"Proc. of SODA'02","author":"Cohen E.","year":"2002"},{"key":"e_1_2_1_9_1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2001"},{"key":"e_1_2_1_10_1","unstructured":"B. Dawes and D. Abrahams. Boost c++ libraries. http:\/\/www.boost.org\/. B. Dawes and D. Abrahams. Boost c++ libraries. http:\/\/www.boost.org\/."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367929"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375567"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920986"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920878"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536258.2536263"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/280277.280279"},{"key":"e_1_2_1_17_1","volume-title":"Computers and Intractability","author":"Garey M. R.","year":"1990"},{"key":"e_1_2_1_18_1","volume-title":"Algorithmic Graph Theory","author":"Gibbons A.","year":"1985"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773171"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.1060"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376676"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465300"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391729.1391730"},{"key":"e_1_2_1_26_1","volume-title":"Hop doubling label indexing for point-to-point distance querying on scale-free networks. PVLDB, 7(12)","author":"Jiang M.","year":"2014"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335415"},{"key":"e_1_2_1_28_1","volume-title":"A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem. Management Science, 18(7)","author":"Lawler E. L.","year":"1972"},{"key":"e_1_2_1_29_1","volume-title":"Proc. of VLDB'07","author":"Qi Y.","year":"2007"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453899"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_1_32_1","volume-title":"http:\/\/www.w3.org\/TR\/xpath","author":"C. Xml","year":"1999"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1855072"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212355"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213896"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687727"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2735479.2735486","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:21:27Z","timestamp":1672226487000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2735479.2735486"}},"subtitle":["efficient top-k tree matching"],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":36,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.14778\/2735479.2735486"],"URL":"https:\/\/doi.org\/10.14778\/2735479.2735486","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}