XML tree structure compression using RePair

Adiego, 2007, Using structural contexts to compress semistructured text collections, Information Processing & Management, 43, 769, 10.1016/j.ipm.2006.07.001

Akutsu, 2010, A bisection algorithm for grammar-based compression of ordered trees, Information Processing Letters, 110, 815, 10.1016/j.ipl.2010.07.004

D. Arroyuelo, R. Cánovas, G. Navarro, K. Sadakane, Succinct trees in practice, in: ALENEX, 2010, pp. 84–97.

P. Bille, I. Li Gørtz, G.M. Landau, O. Weimann, Tree compression with top trees, in: ICALP, in press.

Böttcher, 2010, CluX – clustering XML sub-trees, International Conference on Enterprise Information Systems, 1, 142

P. Buneman, M. Grohe, C. Koch, Path queries on compressed XML, in: Very Large Databases, 2003, pp. 141–152.

Busatto, 2008, Efficient memory representation of XML document trees, Information Systems, 33, 456, 10.1016/j.is.2008.01.004

A. Gascón, C. Creus, G. Godoy, One-context unification with STG-compressed terms is in NP, in: RTA, 2012, pp. 149–164.

Charikar, 2005, The smallest grammar problem, IEEE Transactions on Information Theory, 51, 2554, 10.1109/TIT.2005.850116

J. Cheney, Compressing XML with multiplexed hierarchical PPM models, in: DCC, 2001, pp. 163–172.

H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, C. Löding, D. Lugiez, S. Tison, M. Tommasi, Tree automata techniques and applications, Available at: 〈http://www.grappa.univ-lille3.fr/tata〉, 2007.

P. Deutsch, DEFLATE compressed data format specification version 1.3. 1996.

Downey, 1980, Variations on the common subexpression problem, Journal of the ACM, 27, 758, 10.1145/322217.322228

M. Frick, M. Grohe, C. Koch, Query evaluation on compressed trees (extended abstract), in: LICS, 2003, pp. 188–197.

Gascón, 2011, Unification and matching on compressed terms, ACM Transactions on Computational Logic, 12, 26, 10.1145/1970398.1970402

Knuth, 1968

N. Kobayashi, K. Matsuda, A. Shinohara, Functional programs as compressed data, in: PEPM 2012, pp. 121–130.

C. Krislin, Optimierung grammatik-basierter XML-Kompression, Diplomarbeit, Faculty for Electrical Engineering, Computer Science and Mathematics, University of Paderborn, Germany, 2008.

N.J. Larsson, A. Moffat, Offline dictionary-based compression, in: DCC, 1999, pp. 296–305.

Levy, 2008, The complexity of monadic second-order unification, SIAM Journal on Computing, 38, 1113, 10.1137/050645403

H. Liefke, D. Suciu, XMill: an efficient compressor for XML data, in: SIGMOD Conference, 2000, pp. 153–164.

Lohrey, 2006, The complexity of tree automata and XPath on grammar-compressed trees, Theoretical Computer Science, 363, 196, 10.1016/j.tcs.2006.07.024

M. Lohrey, S. Maneth, R. Mennicke, Tree structure compression with RePair, CoRR, abs/1007.5406, 2010.

M. Lohrey, S. Maneth, R. Mennicke, Tree structure compression with RePair, in: DCC, 2011, pp. 353–362.

M. Lohrey, S. Maneth, E. Noeth, Xml compression via dags, in: ICDT, 2013, pp. 69–80.

Lohrey, 2012, Parameter reduction and automata evaluation for grammar-compressed trees, Journal of Computer and System Sciences, 78, 1651, 10.1016/j.jcss.2012.03.003

S. Maneth, G. Busatto, Tree transducers and tree compressions, in: FoSSaCS, 2004, pp. 363–377.

S. Maneth, N. Mihaylov, S. Sakr, XML tree structure compression, in: DEXA Workshops, 2008, pp. 243–247.

S. Maneth, T. Sebastian, Fast and tiny structural self-indexes for XML, CoRR, abs/1012.5696, 2010.

Murata, 2005, Taxonomy of XML schema languages using formal language theory, ACM Transactions on Internet Technology, 5, 660, 10.1145/1111627.1111631

Neven, 2002, Automata theory for XML researchers, SIGMOD Record, 31, 39, 10.1145/601858.601869

W. Plandowski, Testing equivalence of morphisms on context-free languages, in: ESA, 1994, pp. 460–470.

K. Sadakane, G. Navarro, Fully-functional succinct trees, in: SODA, 2010, pp. 134–149.

A. Schmidt, F. Waas, M.L. Kersten, M.J. Carey, I. Manolescu, R. Busse, XMark: a benchmark for XML data management, in: VLDB, 2002, pp. 974–985.

M. Schmidt-Schauß, Polynomial equality testing for terms with shared substructures, Frank report 21, Fachbereich Informatik und Mathematik. J.W. Goethe-Universität Frankfurt am Main, German, 2005.

M. Schmidt-Schauß, Matching of compressed patterns with character-variables, in: RTA, 2012, pp. 272–287.

M. Schmidt-Schauß, D. Sabel, A. Anis, Congruence closure of compressed terms in polynomial time, in: FroCos, 2011, pp. 227–242.

Schwentick, 2007, Automata for XML – a survey, Journal of Computer and System Sciences, 73, 289, 10.1016/j.jcss.2006.10.003

K. Yamagata, T. Uchida, T. Shoudai, Y. Nakamura, An effective grammar-based compression algorithm for tree structured data, in: ILP, 2003, pp. 383–400.