Logarithmic Complexity for a class of XML Queries

ID
TR-2004-04
Authors
Jeremy Barbay
Publishing date
April 01, 2004
Length
14 pages
Abstract
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.