Efficient memory representation of XML document trees

Megginson, 2004 Fernandez, 2003, Implementing XQuery 1.0: the Galax experience, 1077 Milo, 2003, Typechecking for XML transformers, J. Comput. Syst. Sci., 66, 66, 10.1016/S0022-0000(02)00030-2 Katajainen, 1990, Tree compression and optimization with applications, Int. J. Found. Comput. Sci., 1, 425, 10.1142/S0129054190000291 Ferragina, 2005, Structuring labeled trees for optimal succinctness and beyond, 184 Geary, 2004, Succinct ordinal trees with level-ancestor queries, 1 Geary, 2006, A simple optimal representation for balanced parentheses, Theor. Comput. Sci., 368, 231, 10.1016/j.tcs.2006.09.014 Buneman, 2003, Path queries on compressed XML, 141 Lohrey, 2006, The complexity of tree automata and XPath on grammar-compressed trees, Theor. Comput. Sci., 363, 196, 10.1016/j.tcs.2006.07.024 D.K. Fisher, S. Maneth, Structural selectivity estimation for XML documents, in: Proceedings of the ICDE 2007, IEEE Press, New York, 2007, pp. 626–635. Arion, 2003, XQueC: pushing queries to compressed XML data, 1065 Liefke, 2000, XMill: an efficient compressor for XML data, 153 S. Maneth, G. Busatto, Tree transducers and tree compressions, in: Proceedings of the FOSSACS 2004, Lecture Notes on Computer Science, vol. 2987, Springer, Berlin, 2004, pp. 363–377. Lamping, 1990, An algorithm for optimal lambda calculus reductions, 16 Charikar, 2005, The smallest grammar problem, IEEE Trans. Inform. Theory, 51, 2554, 10.1109/TIT.2005.850116 Plandowski, 1994, Testing equivalence of morphisms on context-free languages, vol. 855, 460 Rytter, 1999, Algorithms on compressed strings and arrays, vol. 1725, 48 Gécseg, 1997, Tree languages, vol. 3 Yao, 2004, XBench benchmark and performance testing of XML DBMSs, 621 Murata, 2001, Taxonomy of XML schema languages using formal language theory Bar-Hillel, 1961, On formal properties of simple phrase structure grammars, Z. Phonetik. Shrachwiss. Kommunikationsforsch., 14, 143 M.J. Fischer, Grammars with macro-like productions, Ph.D. Thesis, Harvard University, Massachusetts, May 1968. Papadimitriou, 1994 Yamagata, 2003, An effective grammar-based compression algorithm for tree structured data, vol. 2835, 383 Min, 2003, XPRESS: a queriable compression for XML data, 122 Tolani, 2002, XGRIND: a query-friendly XML compressor, 225 Zhang, 2004, A succinct physical storage scheme for efficient evaluation of path queries in XML, 54 Cheng, 2004, XQzip: querying compressed XML using structural indexing, vol. 2992, 219 Rytter, 2002, Application of Lempel-Ziv factorization to the approximation of grammar-based compression, Theor. Comput. Sci., 302, 211, 10.1016/S0304-3975(02)00777-6 J.R. Cheney, Personal communication, 2004. Chen, 1996, Efficient lossless compression of trees and graphs J.R. Cheney, First-order term compression: techniques and applications, Master's Thesis, Carnegie Mellon University, August 1998. Frick, 2003, Query evaluation on compressed trees (extended abstract), 188 Buneman, 2005, Vectorizing and querying large XML repositories, 261 Gapeyev, 2005, XML goes native: run-time representations for Xtatic, vol. 3443, 43