{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T11:01:10Z","timestamp":1780743670096,"version":"3.54.1"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,11,1]],"date-time":"2009-11-01T00:00:00Z","timestamp":1257033600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000121","name":"Division of Mathematical Sciences","doi-asserted-by":"publisher","award":["DMS 0354600DMS 0354690"],"award-info":[{"award-number":["DMS 0354600DMS 0354690"]}],"id":[{"id":"10.13039\/100000121","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,11]]},"abstract":"<jats:p>\n            Consider an ordered, static tree\n            <jats:italic>T<\/jats:italic>\n            where each node has a label from alphabet \u03a3. Tree\n            <jats:italic>T<\/jats:italic>\n            may be of arbitrary degree and shape. Our goal is designing a compressed storage scheme of\n            <jats:italic>T<\/jats:italic>\n            that supports basic\n            <jats:italic>navigational<\/jats:italic>\n            operations among the immediate neighbors of a node (i.e. parent,\n            <jats:italic>i<\/jats:italic>\n            th child, or any child with some label,\u2026) as well as more sophisticated\n            <jats:italic>path<\/jats:italic>\n            -based search operations over its labeled structure.\n          <\/jats:p>\n          <jats:p>\n            We present a novel approach to this problem by designing what we call the XBW-transform of the tree in the spirit of the well-known Burrows-Wheeler transform for strings [1994]. The XBW-transform uses path-sorting to linearize the labeled tree\n            <jats:italic>T<\/jats:italic>\n            into\n            <jats:italic>two<\/jats:italic>\n            coordinated arrays, one capturing the structure and the other the labels. For the first time, by using the properties of the XBW-transform, our compressed indexes go beyond the information-theoretic lower bound, and support navigational and path-search operations over labeled trees within (near-)optimal time bounds and entropy-bounded space.\n          <\/jats:p>\n          <jats:p>Our XBW-transform is simple and likely to spur new results in the theory of tree compression and indexing, as well as interesting application contexts. As an example, we use the XBW-transform to design and implement a compressed index for XML documents whose compression ratio is significantly better than the one achievable by state-of-the-art tools, and its query time performance is order of magnitudes faster.<\/jats:p>","DOI":"10.1145\/1613676.1613680","type":"journal-article","created":{"date-parts":[[2009,11,24]],"date-time":"2009-11-24T15:21:01Z","timestamp":1259076061000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":110,"title":["Compressing and indexing labeled trees, with applications"],"prefix":"10.1145","volume":"57","author":[{"given":"Paolo","family":"Ferragina","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Pisa, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabrizio","family":"Luccio","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Pisa, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giovanni","family":"Manzini","sequence":"additional","affiliation":[{"name":"Universit\u00e0 del Piemonte Orientale, Alessandria, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S.","family":"Muthukrishnan","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway, New Jersey"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,11,27]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the IEEE Data Compression Conference (DCC). IEEE Computer Society Press","author":"Adiego J.","unstructured":"Adiego , J. , de la Fuente , P. , and Navarro , G . 2004. Merging prediction by partial matching with structural contexts model . In Proceedings of the IEEE Data Compression Conference (DCC). IEEE Computer Society Press , Los Alamitos, CA, 522. Adiego, J., de la Fuente, P., and Navarro, G. 2004. Merging prediction by partial matching with structural contexts model. In Proceedings of the IEEE Data Compression Conference (DCC). IEEE Computer Society Press, Los Alamitos, CA, 522."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 29th International Conference on Very Large Data Bases (VLDB). 1065--1068","author":"Arion A.","unstructured":"Arion , A. , Bonifati , A. , Costa , G. , D'Aguanno , S. , Manolescu , I. , and Pugliese , A . 2003. XQueC: pushing queries to compressed XML data . In Proceedings of the 29th International Conference on Very Large Data Bases (VLDB). 1065--1068 . Arion, A., Bonifati, A., Costa, G., D'Aguanno, S., Manolescu, I., and Pugliese, A. 2003. XQueC: pushing queries to compressed XML data. In Proceedings of the 29th International Conference on Very Large Data Bases (VLDB). 1065--1068."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11780441_29"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.07.015"},{"key":"e_1_2_1_5_1","unstructured":"Barbay J. He M. Munro J. and Rao S. 2008. Succinct indexes for string bynary relations and multi-labeled trees. Submitted to Journal (Preliminary version appeared in Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 07)).   Barbay J. He M. Munro J. and Rao S. 2008. Succinct indexes for string bynary relations and multi-labeled trees. Submitted to Journal (Preliminary version appeared in Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 07))."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118737.3118845"},{"key":"e_1_2_1_7_1","volume-title":"Tech. Rep. 124","author":"Burrows M.","year":"1994","unstructured":"Burrows , M. , and Wheeler , D . 1994 . A block-sorting lossless data compression algorithm. Tech. Rep. 124 , Digital Equipment Corporation. Burrows, M., and Wheeler, D. 1994. A block-sorting lossless data compression algorithm. Tech. Rep. 124, Digital Equipment Corporation."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2008.01.004"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/MIC.2005.115"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/882454.875122"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 9th International Conference on Extending Database Technology. Lecture Notes in Computer Science","volume":"2992","author":"Cheng J.","unstructured":"Cheng , J. , and Ng , W . 2004. XQzip: Querying compressed XML using structural indexing . In Proceedings of the 9th International Conference on Extending Database Technology. Lecture Notes in Computer Science , vol. 2992 . Springer-Verlag, Berlin, Germany, 219--236. Cheng, J., and Ng, W. 2004. XQzip: Querying compressed XML using structural indexing. In Proceedings of the 9th International Conference on Extending Database Technology. Lecture Notes in Computer Science, vol. 2992. Springer-Verlag, Berlin, Germany, 219--236."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_33"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 29th International Conference on Very Large Data Bases (VLDB). 1077--1080","author":"Fernandez M. F.","unstructured":"Fernandez , M. F. , Simeon , J. , Choi , B. , Marian , A. , and Sur , G . 2003. Implementing Xquery 1.0: the Galax experience . In Proceedings of the 29th International Conference on Very Large Data Bases (VLDB). 1077--1080 . Fernandez, M. F., Simeon, J., Choi, B., Marian, A., and Sur, G. 2003. Implementing Xquery 1.0: the Galax experience. In Proceedings of the 29th International Conference on Very Large Data Bases (VLDB). 1077--1080."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_67"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.12.010"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082043"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412228.1455268"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.69"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1135777.1135891"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0255(01)00098-6"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082039"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1240233.1240243"},{"key":"e_1_2_1_23_1","unstructured":"Ferragina P. and Navarro G. 2007. The Pizza&Chili corpus home page. http:\/\/pizzachili.dcc.uchile.cl\/or http:\/\/pizzachili.di.unipi.it\/.  Ferragina P. and Navarro G. 2007. The Pizza&Chili corpus home page. http:\/\/pizzachili.dcc.uchile.cl\/or http:\/\/pizzachili.di.unipi.it\/."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Ferragina P. and Rao S. 2008. Tree compression and indexing. In Encyclopedia of Algorithms Springer. 964--967.  Ferragina P. and Rao S. 2008. Tree compression and indexing. In Encyclopedia of Algorithms Springer. 964--967.","DOI":"10.1007\/978-0-387-30162-4_430"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.12.012"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198516"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB). 436--445","author":"Goldman R.","unstructured":"Goldman , R. , and Widom , J . 1997. Dataguides: Enabling query formulation and optimization in semistructured databases . In Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB). 436--445 . Goldman, R., and Widom, J. 1997. Dataguides: Enabling query formulation and optimization in semistructured databases. In Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB). 436--445."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Golynski A.","unstructured":"Golynski , A. , Munro , J. I. , and Rao , S . 2006. Rank\/select operations on large alphabets: A tool for text indexing . In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM , New York, 368--373. Golynski, A., Munro, J. I., and Rao, S. 2006. Rank\/select operations on large alphabets: A tool for text indexing. In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 368--373."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science","volume":"4596","author":"Gupta A.","unstructured":"Gupta , A. , Hon , W. , Shah , R. , and Vitter , J . 2007. A framework for dynamizing succinct data structures . In Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science , vol. 4596 . Springer-Verlag, Berlin, Germany, 521--532. Gupta, A., Hon, W., Shah, R., and Vitter, J. 2007. A framework for dynamizing succinct data structures. In Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 4596. Springer-Verlag, Berlin, Germany, 521--532."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63533"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Jansson J.","unstructured":"Jansson , J. , Sadakane , K. , and Sung , W . 2007. Ultra-succinct representation of ordered trees . In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM , New York, 575--584. Jansson, J., Sadakane, K., and Sung, W. 2007. Ultra-succinct representation of ordered trees. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 575--584."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217856.1217858"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/800152.804905"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007656"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63475"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335405"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/11682462_64"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382782"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 3rd International Conference on Database Theory. 277--295","author":"Milo T.","unstructured":"Milo , T. , and Suciu , D . 1999. Index structures for path expressions . In Proceedings of the 3rd International Conference on Database Theory. 277--295 . Milo, T., and Suciu, D. 1999. Index structures for path expressions. In Proceedings of the 3rd International Conference on Database Theory. 277--295."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872775"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/348751.348754"},{"key":"e_1_2_1_43_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceeding of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science","author":"Munro J. I.","unstructured":"Munro , J. I. 1996. Tables . In Proceeding of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science . Lecture Notes in Computer Science , vol. 1180 . Springer-Verlag , Berlin, Germany , 37--42. Munro, J. I. 1996. Tables. In Proceeding of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science, vol. 1180. Springer-Verlag, Berlin, Germany, 37--42."},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science","volume":"2719","author":"Munro J. I.","unstructured":"Munro , J. I. , Raman , R. , Raman , V. , and Rao , S . 2003. Succinct representations of permutations . In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science , vol. 2719 . Springer-Verlag, Berlin, Germany, 345--356. Munro, J. I., Raman, R., Raman, V., and Rao, S. 2003. Succinct representations of permutations. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 2719. Springer-Verlag, Berlin, Germany, 345--356."},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the 38th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press","author":"Munro J. I.","unstructured":"Munro , J. I. , and Raman , V . 1997. Succinct representation of balanced parentheses, static trees and planar graphs . In Proceedings of the 38th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press , Los Alamitos, CA, 118--126. Munro, J. I., and Raman, V. 1997. Succinct representation of balanced parentheses, static trees and planar graphs. In Proceedings of the 38th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 118--126."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799364092"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science","volume":"3142","author":"Munro J. I.","unstructured":"Munro , J. I. , and Rao , S . 2004. Succinct representations of functions . In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science , vol. 3142 . Springer-Verlag, Germany, 1006--1015. Munro, J. I., and Rao, S. 2004. Succinct representations of functions. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 3142. Springer-Verlag, Germany, 1006--1015."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1216370.1216372"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-006-0012-z"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290680"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the 20th International Conference on Data Engineering (ICDE). 288--300","author":"Raw P.","unstructured":"Raw , P. , and Moon , B . 2004. PRIX: Indexing and querying XML using Pr\u00fcfer sequences . In Proceedings of the 20th International Conference on Data Engineering (ICDE). 288--300 . Raw, P., and Moon, B. 2004. PRIX: Indexing and querying XML using Pr\u00fcfer sequences. In Proceedings of the 20th International Conference on Data Engineering (ICDE). 288--300."},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the 18th International Conference on Data Engineering (ICDE). 225--234","author":"Tolani P. M.","unstructured":"Tolani , P. M. , and Haritsa , J. R . 2002. XGRIND: A query-friendly XML compressor . In Proceedings of the 18th International Conference on Data Engineering (ICDE). 225--234 . Tolani, P. M., and Haritsa, J. R. 2002. XGRIND: A query-friendly XML compressor. In Proceedings of the 18th International Conference on Data Engineering (ICDE). 225--234."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872774"},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the 31st International Conference on Very Large Data Bases (VLDB). 145--156","author":"Wang W.","unstructured":"Wang , W. , Wang , H. , Lu , H. , Jang , H. , Lin , X. , and Li , J . 2005. Efficient processing of XML path queries using the disk-based F&B index . In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB). 145--156 . Wang, W., Wang, H., Lu, H., Jang, H., Lin, X., and Li, J. 2005. Efficient processing of XML path queries using the disk-based F&B index. In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB). 145--156."},{"key":"e_1_2_1_55_1","volume-title":"Managing Gigabytes: Compressing and Indexing Documents and Images","author":"Witten I. H.","year":"1999","unstructured":"Witten , I. H. , Moffat , A. , and Bell , T. C . 1999 . Managing Gigabytes: Compressing and Indexing Documents and Images , Second ed. Morgan Kaufmann , Los Altos, CA . Witten, I. H., Moffat, A., and Bell, T. C. 1999. Managing Gigabytes: Compressing and Indexing Documents and Images, Second ed. Morgan Kaufmann, Los Altos, CA."},{"key":"e_1_2_1_56_1","unstructured":"Ye Z. and Berger T. 1998. Information measures for discrete random fields. Science Press.  Ye Z. and Berger T. 1998. Information measures for discrete random fields. Science Press."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1613676.1613680","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1613676.1613680","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:41:08Z","timestamp":1750250468000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1613676.1613680"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,11]]},"references-count":56,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,11]]}},"alternative-id":["10.1145\/1613676.1613680"],"URL":"https:\/\/doi.org\/10.1145\/1613676.1613680","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,11]]},"assertion":[{"value":"2007-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-11-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}