XML tree structure compression using RePair

Information Systems - Tập 38 Số 8 - Trang 1150-1167 - 2013
Markus Lohrey1, Sebastian Maneth2, Roy Mennicke3
1Universität Leipzig, Institut für Informatik, Germany#TAB#
2University of Oxford Department of Computer Science, UK
3Technische Universität Ilmenau, Institut für Theoretische Informatik, Germany

Tóm tắt

Từ khóa


Tài liệu tham khảo

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.