Technical Reports

The ICICS/CS Reading Room

UBC CS TR-2004-04 Summary

Logarithmic Complexity for a class of XML Queries, April 01, 2004 Jeremy Barbay, 14 pages

The index of an XML document typically consists of a set of lists of node references. For each node type, a list gives the references of all nodes of this type, in the prefix traversal order. A twig pattern query is answered by the list of all occurrences of a labeled tree structure, and is computed faster using an index. While previous results propose index structures and algorithms which answer twig pattern queries with a complexity linear in the size of the document, we propose an index which allows to answer twig pattern queries with a number of comparisons logarithmic in the size of the document. As answering efficiently twig pattern matching queries necessitates a sophisticate encoding of the output, we expose our technique on two simpler problems, and we claim that the technique can be applied to answer twig pattern queries using a logarithmic number of comparisons as well.

If you have any questions or comments regarding this page please send mail to