{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:43:50Z","timestamp":1750308230439,"version":"3.41.0"},"reference-count":12,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2004,6,1]],"date-time":"2004-06-01T00:00:00Z","timestamp":1086048000000},"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":["SIGMOD Rec."],"published-print":{"date-parts":[[2004,6]]},"abstract":"<jats:p>\n            Trees and graphs are widely used to model biological databases. Providing efficient algorithms to support tree-based or graph-based querying is therefore an important issue. In this paper, we propose an optimal algorithm which can answer the following question: \"Where do the root-to-leaf paths of a rooted labeled tree\n            <jats:italic>Q<\/jats:italic>\n            occur in another rooted labeled tree\n            <jats:italic>T<\/jats:italic>\n            ?\" in time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            +\n            <jats:italic>Occ<\/jats:italic>\n            ), where\n            <jats:italic>m<\/jats:italic>\n            is the size of\n            <jats:italic>Q<\/jats:italic>\n            and\n            <jats:italic>Occ<\/jats:italic>\n            is the output size. We also show the problem of querying a general graph is NP-complete and not approximable within\n            <jats:italic>\n              n\n              <jats:sup>k<\/jats:sup>\n            <\/jats:italic>\n            for any\n            <jats:italic>k<\/jats:italic>\n            &lt; 1, where\n            <jats:italic>n<\/jats:italic>\n            is the number of nodes in the queried graph, unless P = NP.\n          <\/jats:p>","DOI":"10.1145\/1024694.1024698","type":"journal-article","created":{"date-parts":[[2005,11,9]],"date-time":"2005-11-09T22:23:27Z","timestamp":1131575007000},"page":"21-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["An optimal algorithm for querying tree structures and its applications in bioinformatics"],"prefix":"10.1145","volume":"33","author":[{"given":"Hsiao-Fei","family":"Liu","sequence":"first","affiliation":[{"name":"National Taiwan University, Taipei, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ya-Hui","family":"Chang","sequence":"additional","affiliation":[{"name":"National Taiwan Ocean University, Keelung, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kun-Mao","family":"Chao","sequence":"additional","affiliation":[{"name":"National Taiwan University, Taipei, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2004,6]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"134","volume":"14","author":"Aoki K. F.","year":"2003","unstructured":"K. F. Aoki , A. Yamaguchi , Y. Okuno , T. Akutsu , N. Ueda , M. Kanehisa , and H. Mamitsuka , Efficient Tree-Matching Methods for Accurate Carbohydrate Database Queries. Genome Informatics , 14 : 134 -- 143 , 2003 . K. F. Aoki, A. Yamaguchi, Y. Okuno, T. Akutsu, N. Ueda, M. Kanehisa, and H. Mamitsuka, Efficient Tree-Matching Methods for Accurate Carbohydrate Database Queries. Genome Informatics, 14: 134--143, 2003.","journal-title":"Efficient Tree-Matching Methods for Accurate Carbohydrate Database Queries. Genome Informatics"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/640990.640993"},{"key":"e_1_2_1_3_1","volume-title":"Generalized Tree Patterns: On Efficient Evaluation of XQuery. In Proceedings of the 29th Very Large Data Base Conference","author":"Paparizos Z. Chen H. V.","year":"2003","unstructured":"Z. Chen H. V. Jagadish L. V. S. Lakshmanan S. Paparizos , From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery. In Proceedings of the 29th Very Large Data Base Conference , 2003 . Z. Chen H. V. Jagadish L. V. S. Lakshmanan S. Paparizos, From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery. In Proceedings of the 29th Very Large Data Base Conference, 2003."},{"key":"e_1_2_1_4_1","volume-title":"M. Shadmon, A Fast Index for Semistructured Data. In Proceedings of the 27th Very Large Data Base Conference","author":"Cooper B. F.","year":"2001","unstructured":"B. F. Cooper , N. Sample , M. J. Franklin , G. R. Hjaltason , M. Shadmon, A Fast Index for Semistructured Data. In Proceedings of the 27th Very Large Data Base Conference , 2001 . B. F. Cooper, N. Sample, M. J. Franklin, G. R. Hjaltason, M. Shadmon, A Fast Index for Semistructured Data. In Proceedings of the 27th Very Large Data Base Conference, 2001."},{"key":"e_1_2_1_5_1","volume-title":"Introduction to Algorithms, 2\/e","author":"Cormen T. H.","year":"2001","unstructured":"T. H. Cormen , C. E. Leiserson , R. L. Rivest , and C. Stein , Introduction to Algorithms, 2\/e . The MIT Press , 2001 . T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2\/e. The MIT Press, 2001."},{"key":"e_1_2_1_6_1","volume-title":"XPath Query Evaluation: Improving Time and Space Efficiency. In Proceedings of the 19th IEEE International Conference on Data Engineering","author":"Gottlob G.","year":"2003","unstructured":"G. Gottlob , C. Koch , R. Pichler , XPath Query Evaluation: Improving Time and Space Efficiency. In Proceedings of the 19th IEEE International Conference on Data Engineering , 2003 . G. Gottlob, C. Koch, R. Pichler, XPath Query Evaluation: Improving Time and Space Efficiency. In Proceedings of the 19th IEEE International Conference on Data Engineering, 2003."},{"key":"e_1_2_1_7_1","volume-title":"Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology","author":"Gusfield D.","year":"1999","unstructured":"D. Gusfield , Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology . Cambridge University Press , 1999 . D. Gusfield, Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1999."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/19.2.228"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkh063"},{"key":"e_1_2_1_10_1","volume-title":"Efficient Algorithms for Document Retrieval Problems. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, 657--666","author":"Muthukrishnan S.","year":"2002","unstructured":"S. Muthukrishnan , Efficient Algorithms for Document Retrieval Problems. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, 657--666 , 2002 . S. Muthukrishnan, Efficient Algorithms for Document Retrieval Problems. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, 657--666, 2002."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543620"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872774"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1024694.1024698","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1024694.1024698","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:31:35Z","timestamp":1750264295000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1024694.1024698"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,6]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2004,6]]}},"alternative-id":["10.1145\/1024694.1024698"],"URL":"https:\/\/doi.org\/10.1145\/1024694.1024698","relation":{},"ISSN":["0163-5808"],"issn-type":[{"type":"print","value":"0163-5808"}],"subject":[],"published":{"date-parts":[[2004,6]]},"assertion":[{"value":"2004-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}