{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:39:49Z","timestamp":1750307989155,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2006,3,1]],"date-time":"2006-03-01T00:00:00Z","timestamp":1141171200000},"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":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2006,3]]},"abstract":"<jats:p>\n            We propose a new way of indexing XML documents and processing twig patterns in an XML database. Every XML document in the database can be transformed into a sequence of labels by pr\u00fcfer's method that constructs a one-to-one correspondence between trees and sequences. During query processing, a twig pattern is also transformed into its Pr\u00fcfer sequence. By performing subsequence matching on the set of sequences in the database and performing a series of refinement phases that we have developed, we can find all the occurrences of a twig pattern in the database. Our approach allows\n            <jats:italic>holistic processing<\/jats:italic>\n            of a twig pattern without breaking the twig into root-to-leaf paths and processing these paths individually. Furthermore, we show in the article that all correct answers are found without any false dismissals or false alarms. Experimental results demonstrate the performance benefits of our proposed techniques.\n          <\/jats:p>","DOI":"10.1145\/1132863.1132871","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"299-345","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Sequencing XML data and query twigs for fast pattern matching"],"prefix":"10.1145","volume":"31","author":[{"given":"Praveen","family":"Rao","sequence":"first","affiliation":[{"name":"University of Arizona, AZ"}]},{"given":"Bongki","family":"Moon","sequence":"additional","affiliation":[{"name":"University of Arizona, AZ"}]}],"member":"320","published-online":{"date-parts":[[2006,3]]},"reference":[{"volume-title":"Proceedings of the 18th IEEE International Conference on Data Engineering. IEEE Computer Society","author":"Al-Khalifa S.","key":"e_1_2_1_1_1","unstructured":"Al-Khalifa , S. , Jagadish , H. V. , Koudas , N. , Patel , J. M. , Srivastava , D. , and Wu , Y . 2002. Structural joins: A primitive for efficient XML query pattern matching . In Proceedings of the 18th IEEE International Conference on Data Engineering. IEEE Computer Society , San Jose, CA, 141--152.]] Al-Khalifa, S., Jagadish, H. V., Koudas, N., Patel, J. M., Srivastava, D., and Wu, Y. 2002. Structural joins: A primitive for efficient XML query pattern matching. In Proceedings of the 18th IEEE International Conference on Data Engineering. IEEE Computer Society, San Jose, CA, 141--152.]]"},{"key":"e_1_2_1_2_1","volume-title":"Tech. Rep. WD-xpath20-20020816","author":"Berglund A.","year":"2002","unstructured":"Berglund , A. , Boag , S. , Chamberlin , D. , Fernandez , M. F. , Kay , M. , Robie , J. , and Simon , J . 2002 . XML path language (XPath) 2.0 W3C working draft 16. Tech. Rep. WD-xpath20-20020816 , World Wide Web Consortium. (Aug .).]] Berglund, A., Boag, S., Chamberlin, D., Fernandez, M. F., Kay, M., Robie, J., and Simon, J. 2002. XML path language (XPath) 2.0 W3C working draft 16. Tech. Rep. WD-xpath20-20020816, World Wide Web Consortium. (Aug.).]]"},{"key":"e_1_2_1_3_1","volume-title":"Tech. Rep. WD-xquery-20020816","author":"Boag S.","year":"2002","unstructured":"Boag , S. , Chamberlin , D. , Fernandez , M. F. , Florescu , D. , Robie , J. , and Simon , J . 2002 . XQuery 1.0: An XML Query Language W3C working draft 16. Tech. Rep. WD-xquery-20020816 , World Wide Web Consortium. (Aug .).]] Boag, S., Chamberlin, D., Fernandez, M. F., Florescu, D., Robie, J., and Simon, J. 2002. XQuery 1.0: An XML Query Language W3C working draft 16. Tech. Rep. WD-xquery-20020816, World Wide Web Consortium. (Aug.).]]"},{"key":"e_1_2_1_4_1","volume-title":"Tech. Rep. REC-xml-20001006","author":"Bray T.","year":"2000","unstructured":"Bray , T. , Paoli , J. , Sperberg-McQueen , C. M. , and Maler , E . 2000 . Extensible markup language (XML) 1.0 2 nd Ed. W3C recommendation. Tech. Rep. REC-xml-20001006 , World Wide Web Consortium. (Oct .).]] Bray, T., Paoli, J., Sperberg-McQueen, C. M., and Maler, E. 2000. Extensible markup language (XML) 1.0 2nd Ed. W3C recommendation. Tech. Rep. REC-xml-20001006, World Wide Web Consortium. (Oct.).]]","edition":"2"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564727"},{"volume-title":"Proceedings of EMELD Workshop","author":"Catherine Bow B. H.","key":"e_1_2_1_6_1","unstructured":"Catherine Bow , B. H. and Bird , S . 2003. Towards a general model of Interlinear text . In Proceedings of EMELD Workshop . Lansing, MI.]] Catherine Bow, B. H. and Bird, S. 2003. Towards a general model of Interlinear text. In Proceedings of EMELD Workshop. Lansing, MI.]]"},{"volume-title":"Proceedings of the 28th VLDB Conference. Morgan-Kaufmann","author":"Chien S.-Y.","key":"e_1_2_1_7_1","unstructured":"Chien , S.-Y. , Vagena , Z. , Zhang , D. , Tsotras , V. J. , and Zaniolo , C . 2002. Efficient structural joins on indexed XML documents . In Proceedings of the 28th VLDB Conference. Morgan-Kaufmann , Hong Kong, China. 263--274.]] Chien, S.-Y., Vagena, Z., Zhang, D., Tsotras, V. J., and Zaniolo, C. 2002. Efficient structural joins on indexed XML documents. In Proceedings of the 28th VLDB Conference. Morgan-Kaufmann, Hong Kong, China. 263--274.]]"},{"volume-title":"Proceedings of the 27th VLDB Conference. Morgan-Kaufmann","author":"Cooper B. F.","key":"e_1_2_1_8_1","unstructured":"Cooper , B. F. , Sample , N. , Franklin , M. J. , Hjaltason , G. R. , and Shadmon , M . 2001. A fast index for semistructured data . In Proceedings of the 27th VLDB Conference. Morgan-Kaufmann , Rome, Italy. 341--350.]] Cooper, B. F., Sample, N., Franklin, M. J., Hjaltason, G. R., and Shadmon, M. 2001. A fast index for semistructured data. In Proceedings of the 27th VLDB Conference. Morgan-Kaufmann, Rome, Italy. 341--350.]]"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802184"},{"volume-title":"Proceedings of the 23rd VLDB Conference. Morgan-Kaufmann","author":"Goldman R.","key":"e_1_2_1_10_1","unstructured":"Goldman , R. and Widom , J . 1997. DataGuides: Enabling query formulation and optimization in semistructured databases . In Proceedings of the 23rd VLDB Conference. Morgan-Kaufmann , Athens, Greece. 436--445.]] Goldman, R. and Widom, J. 1997. DataGuides: Enabling query formulation and optimization in semistructured databases. In Proceedings of the 23rd VLDB Conference. Morgan-Kaufmann, Athens, Greece. 436--445.]]"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564705"},{"volume-title":"Proceedings of the 29th VLDB Conference. Morgan-Kaufmann","author":"Grust T.","key":"e_1_2_1_12_1","unstructured":"Grust , T. , van Keulen , M. , and Teubner , J . 2003. Staircase join: Teach a relational DBMS to watch its (axis) steps . In Proceedings of the 29th VLDB Conference. Morgan-Kaufmann , Berlin, Germany. 524--535.]] Grust, T., van Keulen, M., and Teubner, J. 2003. Staircase join: Teach a relational DBMS to watch its (axis) steps. In Proceedings of the 29th VLDB Conference. Morgan-Kaufmann, Berlin, Germany. 524--535.]]"},{"volume-title":"Proceedings of the 21rd VLDB Conference. Morgan-Kaufmann","author":"Hellerstein J. M.","key":"e_1_2_1_13_1","unstructured":"Hellerstein , J. M. , Naughton , J. F. , and Pfeffer , A . 1995. Generalized search trees for database systems . In Proceedings of the 21rd VLDB Conference. Morgan-Kaufmann , Zurich, Switzerland. 562--573.]] Hellerstein, J. M., Naughton, J. F., and Pfeffer, A. 1995. Generalized search trees for database systems. In Proceedings of the 21rd VLDB Conference. Morgan-Kaufmann, Zurich, Switzerland. 562--573.]]"},{"volume-title":"Proceedings of the 19th IEEE International Conference on Data Engineering. IEEE Computer Society","author":"Jiang H.","key":"e_1_2_1_14_1","unstructured":"Jiang , H. , Lu , H. , Wang , W. , and Ooi , B. C . 2003. XR-Tree: Indexing XML data for efficient structural joins . In Proceedings of the 19th IEEE International Conference on Data Engineering. IEEE Computer Society , Bangalore, India. 253--264.]] Jiang, H., Lu, H., Wang, W., and Ooi, B. C. 2003. XR-Tree: Indexing XML data for efficient structural joins. In Proceedings of the 19th IEEE International Conference on Data Engineering. IEEE Computer Society, Bangalore, India. 253--264.]]"},{"volume-title":"Proceedings of the 29th VLDB Conference. Morgan-Kaufmann","author":"Jiang H.","key":"e_1_2_1_15_1","unstructured":"Jiang , H. , Wang , W. , Lu , H. , and Yu , J. X . 2003. Holistic twig joins on indexed XML documents . In Proceedings of the 29th VLDB Conference. Morgan-Kaufmann , Berlin, Germany. 273--284.]] Jiang, H., Wang, W., Lu, H., and Yu, J. X. 2003. Holistic twig joins on indexed XML documents. In Proceedings of the 29th VLDB Conference. Morgan-Kaufmann, Berlin, Germany. 273--284.]]"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564707"},{"volume-title":"Proceedings of the 18th IEEE International Conference on Data Engineering. IEEE Computer Society","author":"Kaushik R.","key":"e_1_2_1_17_1","unstructured":"Kaushik , R. , Shenoy , P. , Bohannon , P. , and Gudes , E . 2002. Exploiting local similarity for efficient indexing of paths in graph structured data . In Proceedings of the 18th IEEE International Conference on Data Engineering. IEEE Computer Society , San Jose, CA. 129--140.]] Kaushik, R., Shenoy, P., Bohannon, P., and Gudes, E. 2002. Exploiting local similarity for efficient indexing of paths in graph structured data. In Proceedings of the 18th IEEE International Conference on Data Engineering. IEEE Computer Society, San Jose, CA. 129--140.]]"},{"volume-title":"Proceedings of the 27th VLDB Conference. Morgan-Kaufmann","author":"Li Q.","key":"e_1_2_1_18_1","unstructured":"Li , Q. and Moon , B . 2001. Indexing and querying XML data for regular path expressions . In Proceedings of the 27th VLDB Conference. Morgan-Kaufmann , Rome, Italy. 361--370.]] Li, Q. and Moon, B. 2001. Indexing and querying XML data for regular path expressions. In Proceedings of the 27th VLDB Conference. Morgan-Kaufmann, Rome, Italy. 361--370.]]"},{"volume-title":"Proceedings of the 25th VLDB Conference. Morgan-Kaufmann","author":"McHugh J.","key":"e_1_2_1_19_1","unstructured":"McHugh , J. and Widom , J . 1999. Query optimization for XML . In Proceedings of the 25th VLDB Conference. Morgan-Kaufmann , Edinburgh, Scotland. 315--326.]] McHugh, J. and Widom, J. 1999. Query optimization for XML. In Proceedings of the 25th VLDB Conference. Morgan-Kaufmann, Edinburgh, Scotland. 315--326.]]"},{"volume-title":"Proceedings of the 7th International Conference on Database Theory. Springer-Verlag","author":"Milo T.","key":"e_1_2_1_20_1","unstructured":"Milo , T. and Suciu , D . 1999. Index structures for path expressions . In Proceedings of the 7th International Conference on Database Theory. Springer-Verlag , Jerusalem, Israel. 277--295.]] Milo, T. and Suciu, D. 1999. Index structures for path expressions. In Proceedings of the 7th International Conference on Database Theory. Springer-Verlag, Jerusalem, Israel. 277--295.]]"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 4th International Conference on Language Resources and Evaluation","author":"M\u00fcller K.","year":"2004","unstructured":"M\u00fcller , K. 2004 . Semi-automatic construction of a question treebank . In Proceedings of the 4th International Conference on Language Resources and Evaluation . Lisbon, Portugal.]] M\u00fcller, K. 2004. Semi-automatic construction of a question treebank. In Proceedings of the 4th International Conference on Language Resources and Evaluation. Lisbon, Portugal.]]"},{"volume-title":"Proceedings of the 13th IEEE International Conference on Data Engineering. IEEE Computer Society","author":"Nestorov S.","key":"e_1_2_1_22_1","unstructured":"Nestorov , S. , Wiener , J. U. , and Chawathe , S . 1997. Representative objects: Concise representations of semistructured, hierarchical data . In Proceedings of the 13th IEEE International Conference on Data Engineering. IEEE Computer Society , Birmingham, U.K. 79--90.]] Nestorov, S., Wiener, J. U., and Chawathe, S. 1997. Representative objects: Concise representations of semistructured, hierarchical data. In Proceedings of the 13th IEEE International Conference on Data Engineering. IEEE Computer Society, Birmingham, U.K. 79--90.]]"},{"key":"e_1_2_1_23_1","first-page":"142","article-title":"Neuer Beweis eines Satzes \u00fcber Permutationen","volume":"27","author":"Pr\u00fcfer H.","year":"1918","unstructured":"Pr\u00fcfer , H. 1918 . Neuer Beweis eines Satzes \u00fcber Permutationen . Archiv f\u00fcr Mathematik und Physik 27 , 142 -- 144 .]] Pr\u00fcfer, H. 1918. Neuer Beweis eines Satzes \u00fcber Permutationen. Archiv f\u00fcr Mathematik und Physik 27, 142--144.]]","journal-title":"Archiv f\u00fcr Mathematik und Physik"},{"volume-title":"Proceedings of the 20th IEEE International Conference on Data Engineering. IEEE Computer Society","author":"Rao P.","key":"e_1_2_1_24_1","unstructured":"Rao , P. and Moon , B . 2004. PRIX: Indexing and querying XML using pr\u00fcfer sequences . In Proceedings of the 20th IEEE International Conference on Data Engineering. IEEE Computer Society , Boston, MA. 288--299.]] Rao, P. and Moon, B. 2004. PRIX: Indexing and querying XML using pr\u00fcfer sequences. In Proceedings of the 20th IEEE International Conference on Data Engineering. IEEE Computer Society, Boston, MA. 288--299.]]"},{"key":"e_1_2_1_25_1","unstructured":"UW XML Repository. 2002. http:\/\/www.cs.washington.edu\/research\/xmldatasets.]]  UW XML Repository. 2002. http:\/\/www.cs.washington.edu\/research\/xmldatasets.]]"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872774"},{"key":"e_1_2_1_27_1","unstructured":"William D. Lewis. 2005. Personal communications. http:\/\/zimmer.csufresno.edu\/ wlewis\/.]]  William D. Lewis. 2005. Personal communications. http:\/\/zimmer.csufresno.edu\/ wlewis\/.]]"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/383034.383038"},{"volume-title":"Proceedings of the 32nd International Conference on Current Trends in Theory and Practice of Computer Science. Springer, Merin, Czech Republic. 122--139","author":"Zezula P.","key":"e_1_2_1_29_1","unstructured":"Zezula , P. , Mandreoli , F. , and Martoglia , R . 2004. Tree signatures and unordered XML pattern matching . In Proceedings of the 32nd International Conference on Current Trends in Theory and Practice of Computer Science. Springer, Merin, Czech Republic. 122--139 .]] Zezula, P., Mandreoli, F., and Martoglia, R. 2004. Tree signatures and unordered XML pattern matching. In Proceedings of the 32nd International Conference on Current Trends in Theory and Practice of Computer Science. Springer, Merin, Czech Republic. 122--139.]]"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375722"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132863.1132871","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1132863.1132871","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:06:13Z","timestamp":1750259173000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132863.1132871"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,3]]}},"alternative-id":["10.1145\/1132863.1132871"],"URL":"https:\/\/doi.org\/10.1145\/1132863.1132871","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2006,3]]},"assertion":[{"value":"2006-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}