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 firstname.lastname@example.org.