XML has been used extensively in many applications as a de facto standard for information representation and exchange over internet. Huge volumes of data are organized or exported in tree-structured form and the desired information can be got by traversing the whole tree structure using a twig pattern query. A new definition,Extended Solution Extension,is proposed in this paper to check the usefulness of an element from both forward and backward directions. Then a novel Extended Solution Extension based algorithm,TwigStack+,is also proposed to reduce the query processing cost,simply because it can check whether other ele-ments can be processed together with the current one. Compared with existing methods,query evaluation cost can be largely re-duced. The experimental results on various datasets indicate that the proposed algorithm performs significantly better than the ex-isting ones.
展开▼