Paper ID 229 Estimating the Selectivity of XML Path Expressions for Internet Scale Applications

Data on the Internet is increasingly presented in XML format. This allows for novel applications that query all this data using some XML query language. All XML query languages use path expressions to navigate through the tree structure of the data. Estimating the selectivity of these path expressions is therefore essential for optimizing queries in these languages. In this paper, we propose two techniques for capturing the structure of complex large-scale XML data as would be handled by Internet-scale applications in a small amount of memory for estimating the selectivity of XML path expressions: summarized path trees and summarized Markov tables. We experimentally demonstrate the accuracy of our proposed techniques, and explore the different situations that would favor one technique over the other. We also demonstrate that our proposed techniques are more accurate than the best previously known technique