{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:22:25Z","timestamp":1759638145981,"version":"3.41.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2011,7,1]],"date-time":"2011-07-01T00:00:00Z","timestamp":1309478400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004966","name":"Fifth Framework Programme","doi-asserted-by":"publisher","award":["IST-2001-35443"],"award-info":[{"award-number":["IST-2001-35443"]}],"id":[{"id":"10.13039\/501100004966","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2011,7]]},"abstract":"<jats:p>\n            Given two rooted, ordered, and labeled trees\n            <jats:italic>P<\/jats:italic>\n            and\n            <jats:italic>T<\/jats:italic>\n            the tree inclusion problem is to determine if\n            <jats:italic>P<\/jats:italic>\n            can be obtained from\n            <jats:italic>T<\/jats:italic>\n            by deleting nodes in\n            <jats:italic>T<\/jats:italic>\n            . This problem has recently been recognized as an important query primitive in XML databases. Kilpel\u00e4inen and Mannila [1995] presented the first polynomial-time algorithm using quadratic time and space. Since then several improved results have been obtained for special cases when\n            <jats:italic>P<\/jats:italic>\n            and\n            <jats:italic>T<\/jats:italic>\n            have a small number of leaves or small depth. However, in the worst case these algorithms still use quadratic time and space. Let\n            <jats:italic>n<\/jats:italic>\n            <jats:sub>\n              <jats:italic>S<\/jats:italic>\n            <\/jats:sub>\n            ,\n            <jats:italic>l<\/jats:italic>\n            <jats:sub>\n              <jats:italic>S<\/jats:italic>\n            <\/jats:sub>\n            , and\n            <jats:italic>d<\/jats:italic>\n            <jats:sub>\n              <jats:italic>S<\/jats:italic>\n            <\/jats:sub>\n            denote the number of nodes, the number of leaves, and the depth of a tree\n            <jats:italic>S<\/jats:italic>\n            \u2208\n            <jats:italic>P<\/jats:italic>\n            ,\n            <jats:italic>T<\/jats:italic>\n            . In this article we show that the tree inclusion problem can be solved in space\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sub>\n              <jats:italic>T<\/jats:italic>\n            <\/jats:sub>\n            ) and time: O\u239b\u239dmin\u23a7\u23a8\u23a9lPnTlPlT log log nT + nTnPnTlog nT+ nT log nT\u23ab\u23ac\u23ad\u239e\u23a0.\n          <\/jats:p>\n          <jats:p>This improves or matches the best known time complexities while using only linear space instead of quadratic. This is particularly important in practical applications, such as XML databases, where the space is likely to be a bottleneck.<\/jats:p>","DOI":"10.1145\/1978782.1978793","type":"journal-article","created":{"date-parts":[[2011,7,21]],"date-time":"2011-07-21T13:27:09Z","timestamp":1311254829000},"page":"1-47","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["The tree inclusion problem"],"prefix":"10.1145","volume":"7","author":[{"given":"Philip","family":"Bille","sequence":"first","affiliation":[{"name":"Technical University of Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Inge Li","family":"Gortz","sequence":"additional","affiliation":[{"name":"Technical University of Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,7,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00013317"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1155-5"},{"volume-title":"Proceedings of the 24th International Colloquium on Automata, Languages and Programming. Springer, 270--280","author":"Alstrup S.","key":"e_1_2_1_3_1"},{"volume-title":"Proceedings of the 7th Scandinavian Workshop on Algorithm Theory. Springer, 46--56","author":"Alstrup S.","key":"e_1_2_1_4_1"},{"volume-title":"Proceedings of the 39th Symposium on Foundations of Computer Science. IEEE Computer Society","author":"Alstrup S.","key":"e_1_2_1_5_1"},{"volume-title":"Proceedings of the 13th Symposium on Discrete Algorithms. SIAM","author":"Alstrup S.","key":"e_1_2_1_6_1"},{"volume-title":"Proceedings of the 4th Latin American Symposium on Theoretical Informatics","author":"Bender M. A.","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.12.030"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_6"},{"key":"e_1_2_1_10_1","unstructured":"Boag S. Chamberlin D. Fernandez M. Florescu D. Robie J. Sim\u00e9on J. and Stefanescu M. 2001. XML query language (XQuery). http:\/\/www.w3.org\/TR\/xquery.  Boag S. Chamberlin D. Fernandez M. Florescu D. Robie J. Sim\u00e9on J. and Stefanescu M. 2001. XML query language (XQuery). http:\/\/www.w3.org\/TR\/xquery."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0899"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90030-7"},{"key":"e_1_2_1_13_1","unstructured":"Clark J. and DeRose S. 1999. XML path language (XPath) http:\/\/www.w3.org\/TR\/xpath.  Clark J. and DeRose S. 1999. XML path language (XPath) http:\/\/www.w3.org\/TR\/xpath."},{"volume-title":"Proceedings of the 10th Symposium on Discrete Algorithms. SIAM, 245--254","author":"Cole R.","key":"e_1_2_1_14_1"},{"volume":"4596","volume-title":"34th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science Series","author":"Demaine E. D.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/645928.672544"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89533"},{"volume-title":"Proceedings of the 4th European Symposium on Algorithms. Springer, 107--120","author":"Ferragina P.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792226825"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1171"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/322290.322295"},{"key":"e_1_2_1_23_1","unstructured":"Kilpel\u00e4inen P. 1992. Tree matching problems with applications to structured text databases. Ph.D. thesis Department of Computer Science University of Helsinki.  Kilpel\u00e4inen P. 1992. Tree matching problems with applications to structured text databases. Ph.D. thesis Department of Computer Science University of Helsinki."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/160688.160722"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791218202"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/647908.740125"},{"key":"e_1_2_1_27_1","unstructured":"Knuth D. E. 1969. The Art of Computer Programming Vol. 1. Addison-Wesley.  Knuth D. E. 1969. The Art of Computer Programming Vol. 1. Addison-Wesley."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63475"},{"key":"e_1_2_1_29_1","unstructured":"Mannila H. and R\u00e4ih\u00e4 K. J. 1990. On query languages for the p-string data model. Inf. Modell. Knowl. Bases 469--482.   Mannila H. and R\u00e4ih\u00e4 K. J. 1990. On query languages for the p-string data model. Inf. Modell. Knowl. Bases 469--482."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90687-B"},{"volume-title":"Proceedings of the 7th Symposium on Discrete Algorithms. Springer, 42--51","author":"Muthukrishnan S.","key":"e_1_2_1_31_1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/647816.738463"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.10060"},{"volume-title":"Proceedings of the Workshop On XML and Information Retrieval. ACM","author":"Schlieder T.","key":"e_1_2_1_34_1"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1044"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/322139.322143"},{"volume-title":"Proceedings of the 2nd International Conference on Data Mining. IEEE Computer Society","author":"Termier A.","key":"e_1_2_1_37_1"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780636"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-004-0134-4"},{"volume-title":"Proceedings of the 29th Conference on Very Large Data Bases. VLDB Endowment, 69--80","author":"Yang L. H.","key":"e_1_2_1_40_1"},{"volume-title":"Proceedings of the 1st International XML Database Symposium. Springer, 149--163","author":"Zezula P.","key":"e_1_2_1_41_1"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218082"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1978782.1978793","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1978782.1978793","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:59:37Z","timestamp":1750244377000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1978782.1978793"}},"subtitle":["In linear space and faster"],"short-title":[],"issued":{"date-parts":[[2011,7]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["10.1145\/1978782.1978793"],"URL":"https:\/\/doi.org\/10.1145\/1978782.1978793","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2011,7]]},"assertion":[{"value":"2007-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-07-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}