XML tree structure compression using RePair
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.
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.
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.
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, 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
W. Plandowski, Testing equivalence of morphisms on context-free languages, in: ESA, 1994, pp. 460–470.
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