An Efficient Index Lattice for XML Query Evaluation

We have defined an XML structural index called the Structure Index Tree (SIT), which eliminates duplicate structures arising from the equivalent subtrees in an XML document by merging them into a concise structure. In this paper, we impose a lattice structure on the SIT and call the structure a SIT-lattice in order to enhance the applicability of the index. A SIT-Lattice Element (SLE) is an index of an arbitrary subset of paths in the document. Since paths represent the structure of the XML data and each text node is associated with a unique path, we can define an SLE to filter out both irrelevant structures and text nodes. We demonstrate that SLEs are able to support effective querying over very large XML documents in memory-limited hand-held devices. © Springer-Verlag Berlin Heidelberg 2007