|
Abstract
Data on the Internet is increasingly presented in XML format. This enables novel applications
that pose queries over all the XML data on the Internet. Queries over XML data use path
expressions to navigate through the structure of the data, and optimizing these queries
requires estimating the selectivity of these path expressions. In this paper, the authors
propose two techniques for estimating the selectivity of simple XML path expressions over
complex large-scale XML data as would be handled by Internet-scale applications: path trees
and Markov tables. Both techniques work by summarizing the structure of the XML data in a
small amount of memory and using this summary for selectivity estimation. The authors
experimentally demonstrate the accuracy of the proposed techniques, and explore the different
situations that would favor one technique over the other. They also demonstrate that the
proposed techniques are more accurate than the best previously known alternative.
Read the Presentation
Slides...
Referred Papers
|