Abstract | ||
---|---|---|
Holistic twig join algorithms represent the state of the art for evaluating path expressions in XML queries. Using inverted indexes on XML elements, holistic twig joins move a set of index cursors in a coordinated way to quickly find structural matches. Because each cursor move can trigger I/O, the performance of a holistic twig join is largely determined by how many cursor moves it makes, yet, surprisingly, existing join algorithms have not been optimized along these lines. In this paper, we describe TwigOptimal, a new holistic twig join algorithm with optimal cursor movement. We sketch the proof of TwigOptimal's optimality, and describe how TwigOptimal can use information in the return clause of XQuery to boost its performance. Finally, experimental results are presented, showing TwigOptimal's superiority over existing holistic twig join algorithms. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1145/1099554.1099741 | CIKM |
Keywords | Field | DocType |
cursor move,xml element,optimal cursor movement,xml query,holistic twig,path expression,new holistic,index cursor,inverted index,path expressions,xml,evaluation,indexing,indexation | Twig,Data mining,Joins,XML,Information retrieval,Computer science,Path expression,Search engine indexing,Cursor (user interface),XQuery,Sketch | Conference |
ISBN | Citations | PageRank |
1-59593-140-6 | 26 | 0.84 |
References | Authors | |
14 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Marcus Fontoura | 1 | 1116 | 61.74 |
Vanja Josifovski | 2 | 2265 | 148.84 |
Eugene J. Shekita | 3 | 3630 | 574.21 |
Beverly Yang | 4 | 1790 | 121.37 |