DROPS

Document

Compression vs Queryability - A Case Study

Authors: Siva Anantharaman

Published in: Dagstuhl Seminar Proceedings, Volume 8261, Structure-Based Compression of Complex Massive Data (2008)

Abstract

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.

Cite as

Siva Anantharaman. Compression vs Queryability - A Case Study. In Structure-Based Compression of Complex Massive Data. Dagstuhl Seminar Proceedings, Volume 8261, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{anantharaman:DagSemProc.08261.8,
  author =	{Anantharaman, Siva},
  title =	{{Compression vs Queryability - A Case Study}},
  booktitle =	{Structure-Based Compression of Complex Massive Data},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8261},
  editor =	{Stefan B\"{o}ttcher and Markus Lohrey and Sebastian Maneth and Wojcieh Rytter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08261.8},
  URN =		{urn:nbn:de:0030-drops-16762},
  doi =		{10.4230/DagSemProc.08261.8},
  annote =	{Keywords: Tree automata, Tree Grammars, Dags, XML documents, Queries}
}

Search Results

Documents authored by Anantharaman, Siva

Compression vs Queryability - A Case Study

Abstract

Cite as

Thanks for your feedback!

Could not send message