When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-16762
Go to the corresponding Portal

Anantharaman, Siva

Compression vs Queryability - A Case Study

08261.AnantharamanSiva.Paper.1676.pdf (0.2 MB)


Some compromise on compression is known to be necessary, if the relative positions of the information stored by semi-structured documents are to remain accessible under queries. With this in view, we compare, on an example, the ‘query-friendliness’ of XML documents, when compressed into straightline tree grammars which are either regular or context-free. The queries considered are in a limited fragment of XPath, corresponding to a type of patterns; each such query defines naturally a non-deterministic, bottom-up ‘query automaton’ that runs just as well on a tree as on its compressed dag.

BibTeX - Entry

  author =	{Siva Anantharaman},
  title =	{Compression vs Queryability - A Case Study},
  booktitle =	{Structure-Based Compression of Complex Massive Data },
  year =	{2008},
  editor =	{Stefan B{\"o}ttcher and Markus Lohrey and Sebastian Maneth and Wojcieh Rytter},
  number =	{08261},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{},
  annote =	{Keywords: Tree automata, Tree Grammars, Dags, XML documents, Queries}

Keywords: Tree automata, Tree Grammars, Dags, XML documents, Queries
Seminar: 08261 - Structure-Based Compression of Complex Massive Data
Issue Date: 2008
Date of publication: 20.11.2008

DROPS-Home | Fulltext Search | Imprint Published by LZI