A stream-based selectivity estimation technique for forward XPath

The Extensible Markup Language (XML) rapidly establishes itself as the de facto standard for presenting, storing, and exchanging data on the Internet. However, querying large volume of XML data represents a bottleneck for several computationally intensive applications. A fast and accurate selectivity estimation mechanism is of practical importance because selectivity estimation plays a fundamental role in XML query performance. Recently proposed techniques are all based on some forms of structure synopses that could be time-consuming to build and not effective for summarizing complex structure relationships. To overcome this limitation, we propose an innovative selectivity estimation algorithm, which consists of (1) the path tree synopsis data structure, a succinct description of the original document with low computational overhead and high accuracy for processing tasks like selectivity estimation, (2) a streaming selectivity estimation algorithm which is efficient for path tree traversal. Extensive experiments on both real and synthetic data sets show that our technique achieves better accuracy and less construction time than existing approaches.