{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:18:04Z","timestamp":1750306684816,"version":"3.41.0"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2014,6,1]],"date-time":"2014-06-01T00:00:00Z","timestamp":1401580800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"MINECO","award":["(co-funded with CDTI and GAIN) CDTI EXP 00064563"],"award-info":[{"award-number":["(co-funded with CDTI and GAIN) CDTI EXP 00064563"]}]},{"name":"Fondecyt","award":["1-080019 and 1-110066, Chile (G.N.)"],"award-info":[{"award-number":["1-080019 and 1-110066, Chile (G.N.)"]}]},{"name":"MICINN","award":["(PGE and FEDER) TIN2009-14560-C03-02- and TIN2010-21246-C02-01"],"award-info":[{"award-number":["(PGE and FEDER) TIN2009-14560-C03-02- and TIN2010-21246-C02-01"]}]},{"name":"ITC-20133062 (for the Spanish group)"},{"name":"Xunta de Galicia","award":["(co-funded with FEDER) GRC2013\/053 and CN 2012\/211"],"award-info":[{"award-number":["(co-funded with FEDER) GRC2013\/053 and CN 2012\/211"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst."],"published-print":{"date-parts":[[2014,6]]},"abstract":"<jats:p>\n            The\n            <jats:italic>eXtensible Markup Language<\/jats:italic>\n            (XML) is acknowledged as the\n            <jats:italic>de facto<\/jats:italic>\n            standard for semistructured data representation and data exchange on the Web and many other scenarios. A well-known shortcoming of XML is its verbosity, which increases manipulation, transmission, and processing costs. Various structure-blind and structure-conscious compression techniques can be applied to XML, and some are even access-friendly, meaning that the documents can be efficiently accessed in compressed form. Direct access is necessary to implement the query languages XPath and XQuery, which are the standard ones to exploit the expressiveness of XML. While a good deal of theoretical and practical proposals exist to solve XPath\/XQuery operations on XML, only a few ones are well integrated with a compression format that supports the required access operations on the XML data. In this work we go one step further and design a compression format for XML collections that\n            <jats:italic>boosts<\/jats:italic>\n            the performance of XPath queries on the data. This is done by designing compressed representations of the XML data that support some complex operations apart from just accessing the data, and those are exploited to solve key components of the XPath queries. Our system, called XXS, is aimed at XML collections containing natural language text, which are compressed to within 35%--50% of their original size while supporting a large subset of XPath operations in time competitive with, and many times outperforming, the best state-of-the-art systems that work on uncompressed representations.\n          <\/jats:p>","DOI":"10.1145\/2629554","type":"journal-article","created":{"date-parts":[[2014,7,22]],"date-time":"2014-07-22T15:08:20Z","timestamp":1406041700000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["XXS"],"prefix":"10.1145","volume":"32","author":[{"given":"Nieves R.","family":"Brisaboa","sequence":"first","affiliation":[{"name":"University of A Coru\u00f1a, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ana","family":"Cerdeira-Pena","sequence":"additional","affiliation":[{"name":"University of A Coru\u00f1a, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[{"name":"University of Chile, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,7,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.v58:4"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipm.2006.07.001"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1239971.1239974"},{"volume-title":"Proceedings of the 26th IEEE International Conference on Data Engineering. 417--428","author":"Arroyuelo D.","key":"e_1_2_1_4_1","unstructured":"D. Arroyuelo , F. Claude , S. Maneth , V. M\u00e4kinen , G. Navarro , K. Nguyen , J. Sir\u00e9n , and N. V\u00e4lim\u00e4ki . 2010. Fast in-memory XPath search using compressed indexes . In Proceedings of the 26th IEEE International Conference on Data Engineering. 417--428 . D. Arroyuelo, F. Claude, S. Maneth, V. M\u00e4kinen, G. Navarro, K. Nguyen, J. Sir\u00e9n, and N. V\u00e4lim\u00e4ki. 2010. Fast in-memory XPath search using compressed indexes. In Proceedings of the 26th IEEE International Conference on Data Engineering. 417--428."},{"key":"e_1_2_1_5_1","unstructured":"R. A. Baeza-Yates and B. Ribeiro-Neto. 1999. Modern Information Retrieval. Addison-Wesley Longman.   R. A. Baeza-Yates and B. Ribeiro-Neto. 1999. Modern Information Retrieval. Addison-Wesley Longman."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142527"},{"key":"e_1_2_1_7_1","unstructured":"R. Bourret. 2009. Going native: Use cases for native XML databases. http:\/\/www.rpbourret.com\/xml\/UseCases.htm.  R. Bourret. 2009. Going native: Use cases for native XML databases. http:\/\/www.rpbourret.com\/xml\/UseCases.htm."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1812799.1812835"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34109-0_16"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10791-012-9184-1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10791-006-9001-9"},{"key":"e_1_2_1_12_1","unstructured":"M. Burrows and D. Wheeler. 1994. A block-sorting lossless data compression algorithm. Tech. Rep. 124 Digital Equipment Corporation.  M. Burrows and D. Wheeler. 1994. A block-sorting lossless data compression algorithm. Tech. Rep. 124 Digital Equipment Corporation."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/882454.875122"},{"volume-title":"Proceedings of the 9th International Conference on Extending Database Technology. 219--236","author":"Cheng J.","key":"e_1_2_1_15_1","unstructured":"J. Cheng and W. Ng . 2004. XQzip: Querying compressed XML using structural indexing . In Proceedings of the 9th International Conference on Extending Database Technology. 219--236 . J. Cheng and W. Ng. 2004. XQzip: Querying compressed XML using structural indexing. In Proceedings of the 9th International Conference on Extending Database Technology. 219--236."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1984.1096090"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575832_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/348751.348754"},{"volume-title":"Proceedings of the 29th International Conference on Very Large Data Bases. 1077--1080","author":"Fern\u00e1ndez M. F.","key":"e_1_2_1_19_1","unstructured":"M. F. Fern\u00e1ndez , J. Sim\u00e9on , B. Choi , A. Marian , and G. Sur . 2003. Implementing XQuery 1.0: The Galax experience . In Proceedings of the 29th International Conference on Very Large Data Bases. 1077--1080 . M. F. Fern\u00e1ndez, J. Sim\u00e9on, B. Choi, A. Marian, and G. Sur. 2003. Implementing XQuery 1.0: The Galax experience. In Proceedings of the 29th International Conference on Very Large Data Bases. 1077--1080."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1135777.1135891"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1613676.1613680"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(00)00051-7"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071614"},{"volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. 841--850","author":"Grossi R.","key":"e_1_2_1_24_1","unstructured":"R. Grossi , A. Gupta , and J. S. Vitter . 2003. High-order entropy-compressed text indexes . In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. 841--850 . R. Grossi, A. Gupta, and J. S. Vitter. 2003. High-order entropy-compressed text indexes. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. 841--850."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/JRPROC.1952.273898"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63533"},{"key":"e_1_2_1_27_1","first-page":"65","article-title":"Ten reasons why Saxon XQuery is fast","volume":"31","author":"Kay M.","year":"2008","unstructured":"M. Kay . 2008 . Ten reasons why Saxon XQuery is fast . IEEE Data Eng. Bull. 31 , 4, 65 -- 74 . M. Kay. 2008. Ten reasons why Saxon XQuery is fast. IEEE Data Eng. Bull. 31, 4, 65--74.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"M. Lalmas. 2009. XML Retrieval. Morgan & Claypool Publishers.  M. Lalmas. 2009. XML Retrieval. Morgan & Claypool Publishers.","DOI":"10.1007\/978-3-031-02263-0"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4304\/jcp.2.10.9-17"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2005.20"},{"key":"e_1_2_1_31_1","volume-title":"TREECHOP: A tree-based queriable compressor for XML. Tech. Rep.","author":"Leighton G.","year":"2005","unstructured":"G. Leighton , T. M\u00fcldner , and J. Diamond . 2005 . TREECHOP: A tree-based queriable compressor for XML. Tech. Rep. , Acadia University . G. Leighton, T. M\u00fcldner, and J. Diamond. 2005. TREECHOP: A tree-based queriable compressor for XML. Tech. Rep., Acadia University."},{"volume-title":"Proceedings of the 2nd International Workshop on Web Dynamics.","author":"Levene M.","key":"e_1_2_1_32_1","unstructured":"M. Levene and P. Wood . 2002. XML structure compression . In Proceedings of the 2nd International Workshop on Web Dynamics. M. Levene and P. Wood. 2002. XML structure compression. In Proceedings of the 2nd International Workshop on Web Dynamics."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335405"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066677.1066827"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10791-005-0747-2"},{"key":"e_1_2_1_37_1","unstructured":"S. Maneth and T. Sebastian. 2010. Fast and tiny structural self-indexes for XML. CoRR abs\/1012.5696.  S. Maneth and T. Sebastian. 2010. Fast and tiny structural self-indexes for XML. CoRR abs\/1012.5696."},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"W. Meier. 2002. eXist: An Open Source Native XML Database. In Revised Papers from the NODe 2002 Web and Database-Related Workshops on Web Web-Services and Database Systems. 169--183.   W. Meier. 2002. eXist: An Open Source Native XML Database. In Revised Papers from the NODe 2002 Web and Database-Related Workshops on Web Web-Services and Database Systems. 169--183.","DOI":"10.1007\/3-540-36560-5_13"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872775"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799364092"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/263479.263482"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1216370.1216372"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-006-0012-z"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.1063"},{"key":"e_1_2_1_45_1","unstructured":"T. Oszu. 2003. XBench - a family of benchmarks for XML DBMSs. https:\/\/cs.uwaterloo.ca\/&sim;tozsu\/ddbms\/projects\/xbench\/Specification.html.  T. Oszu. 2003. XBench - a family of benchmarks for XML DBMSs. https:\/\/cs.uwaterloo.ca\/&sim;tozsu\/ddbms\/projects\/xbench\/Specification.html."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071617"},{"volume-title":"Proceedings of the 21th Annual ACM\/SIAM Symposium on Discrete Algorithms. 134--149","author":"Sadakane K.","key":"e_1_2_1_47_1","unstructured":"K. Sadakane and G. Navarro . 2010. Fully-functional succinct trees . In Proceedings of the 21th Annual ACM\/SIAM Symposium on Discrete Algorithms. 134--149 . K. Sadakane and G. Navarro. 2010. Fully-functional succinct trees. In Proceedings of the 21th Annual ACM\/SIAM Symposium on Discrete Algorithms. 134--149."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.01.004"},{"volume-title":"Proceedings of the 23rd International Conference on Data Engineering. 236--245","author":"Schmidt M.","key":"e_1_2_1_49_1","unstructured":"M. Schmidt , S. Scherzinger , and C. Koch . 2007. Combined static and dynamic analysis for effective buffer minimization in streaming XQuery evaluation . In Proceedings of the 23rd International Conference on Data Engineering. 236--245 . M. Schmidt, S. Scherzinger, and C. Koch. 2007. Combined static and dynamic analysis for effective buffer minimization in streaming XQuery evaluation. In Proceedings of the 23rd International Conference on Data Engineering. 236--245."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.v38:10"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/11605157_24"},{"volume-title":"Proceedings of the 18th International Conference on Data Engineering. 225--234","author":"Tolani P. M.","key":"e_1_2_1_52_1","unstructured":"P. M. Tolani and J. R. Haritsa . 2002. XGrind: A query-friendly XML compressor . In Proceedings of the 18th International Conference on Data Engineering. 225--234 . P. M. Tolani and J. R. Haritsa. 2002. XGrind: A query-friendly XML compressor. In Proceedings of the 18th International Conference on Data Engineering. 225--234."},{"key":"e_1_2_1_54_1","unstructured":"W3C. 1998. Recommendation of Extensible Markup Language (XML) 1.0. http:\/\/www.w3.org\/TR\/REC-xml.  W3C. 1998. Recommendation of Extensible Markup Language (XML) 1.0. http:\/\/www.w3.org\/TR\/REC-xml."},{"key":"e_1_2_1_55_1","unstructured":"W3C. 1999. Recommendation of XML Path Language (XPath) 1.0. http:\/\/www.w3.org\/TR\/xpath.  W3C. 1999. Recommendation of XML Path Language (XPath) 1.0. http:\/\/www.w3.org\/TR\/xpath."},{"key":"e_1_2_1_56_1","unstructured":"W3C. 2010a. Recommendation of XML Path Language (XPath) 2.0. http:\/\/www.w3.org\/TR\/xpath20.  W3C. 2010a. Recommendation of XML Path Language (XPath) 2.0. http:\/\/www.w3.org\/TR\/xpath20."},{"key":"e_1_2_1_57_1","unstructured":"W3C. 2010b. Recommendation of XML Query Language (XQuery) 1.0. http:\/\/www.w3.org\/TR\/xquery.  W3C. 2010b. Recommendation of XML Query Language (XQuery) 1.0. http:\/\/www.w3.org\/TR\/xquery."},{"key":"e_1_2_1_58_1","unstructured":"W3C. 2011. Recommendation of XQuery and XPath Full Text 1.0. http:\/\/www.w3.org\/TR\/xpath-full-text-10.  W3C. 2011. Recommendation of XQuery and XPath Full Text 1.0. http:\/\/www.w3.org\/TR\/xpath-full-text-10."},{"volume-title":"Proceedings of the International Conference on Information Technology: Coding and Computing. 354--358","author":"Wang H.","key":"e_1_2_1_59_1","unstructured":"H. Wang , J. Li , J. Luo , and Z. He . 2004. XCPaqs: Compression of XML documents with XPath query support . In Proceedings of the International Conference on Information Technology: Coding and Computing. 354--358 . H. Wang, J. Li, J. Luo, and Z. He. 2004. XCPaqs: Compression of XML documents with XPath query support. In Proceedings of the International Conference on Information Technology: Coding and Computing. 354--358."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.1984.1659158"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242717"},{"key":"e_1_2_1_62_1","unstructured":"XML Mind Products. 2008. Qizx XML database engine. http:\/\/www.axyana.com\/qizx.  XML Mind Products. 2008. Qizx XML database engine. http:\/\/www.axyana.com\/qizx."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1977.1055714"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055934"}],"container-title":["ACM Transactions on Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629554","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629554","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:01:18Z","timestamp":1750230078000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629554"}},"subtitle":["Efficient XPath Evaluation on Compressed XML Documents"],"short-title":[],"issued":{"date-parts":[[2014,6]]},"references-count":61,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,6]]}},"alternative-id":["10.1145\/2629554"],"URL":"https:\/\/doi.org\/10.1145\/2629554","relation":{},"ISSN":["1046-8188","1558-2868"],"issn-type":[{"type":"print","value":"1046-8188"},{"type":"electronic","value":"1558-2868"}],"subject":[],"published":{"date-parts":[[2014,6]]},"assertion":[{"value":"2013-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-07-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}