Tree signatures for XML querying and navigation

In order to accelerate the performance of various matching and navigational operations on collections of XML documents, new indexing structures, called tree signatures, are proposed. We show that XML tree structures can be efficiently represented as ordered sequences of preorder and postorder ranks. Two proposed versions of tree signatures differ in the amount of information they contain, and extensive performance evaluation demonstrates the tradeoff between the space and performance of executing different XPath axes. We also show how to apply tree signatures in query processing and demonstrate that a speedup of up to one order of magnitude can be achieved with respect to the containment join strategy. Other alternatives of using the tree signatures in intelligent XML searching are outlined in the conclusions.