Indexing for XML Siblings SungRan Cho   View Paper (PDF)   Return to Paper Session 5: XML Abstract Efficient querying XML documents is an increasingly important issue considering the fact that XML becomes the de facto standard for data representation and exchange over the Web, and XML data in diverse data sources and applications is growing rapidly in size. Given the importance of XPath based query access, Grust proposed R-tree index, we refer to as whole-tree indexes (WI). Such index, however, has a very high cost for the following-sibling and preceding-sibling axes. In this paper we develop a family of index structures, which we refer to as splittree indexes (SI), to address this problem, in which (i) XML data is horizontally split by a simple, yet efficient criteria, and (ii) the split value is associated with tree labeling. While the SI is straightforward to construct, it incurs the overlap problem between bounding boxes. We resolve this problem by designing the transformed split-tree indexes (TSI).We also study the most promising existing method of constructing R-tree, the Hilbert tree, so that we take advantage of its benefit for XML siblings. Lastly, we experimentally demonstrate the benefits of the TSI for siblings over the WI using benchmark data sets. ©2006 Association for Computing Machinery