Efficient processing of XML path queries using the disk-based F&B index

Abstract

With the proliferation of XML data and applications on the Internet, efficient XML query processing techniques are in great demand. Answering queries using XML indexes is a natural approach. A number of XML indexes have been proposed in the literature; among them, F&B Index is one powerful index as it is the smallest index that answers all twig queries. However, an F&B Index suffers from the following two problems: (1) it was originally proposed as a memory-based index while its size is usually large in practice and (2) answering queries using an F&B Index is not fully optimized. These problems limit the benefits and even applications of F&B Indexes in practice. In this paper, we propose a highly optimized disk organization method for an F&B Index; the result is a disk-based F&B Index with good clustering properties. In addition, novel query processing algorithms exploiting the physical organization of the disk-based F&B Indexes are proposed. Experimental results verify that our disk-based F&B Index can scale up for large data size with good query performance compared with state-ofthe-art XML query processing algorithms.