A sampling approach for XML query selectivity estimation

As the Extensible Markup Language (XML) rapidly estab-lishes itself as the de facto standard for presenting, stor-ing, and exchanging data on the Internet, large volume of XML data and their supporting facilities start to surface. A fast and accurate selectivity estimation mechanism is of practical importance because selectivity estimation plays a fundamental role in XML query optimization. Recently pro-posed techniques are all based on some forms of structure synopses that could be time-consuming to build and not ef-fective for summarizing complex structure relationships. In this research, we propose an innovative sampling method that can capture the tree structures and intricate relation-ships among nodes in a simple and eective way. The de-rived sample tree is stored as a synopsis for selectivity esti-mation. Extensive experimental results show that, in com-parison with the state-of-the-art structure synopses, specif-ically the TreeSketch and Xseed synopses, our sample tree synopsis applies to a broader range of query types, requires several orders of magnitude less construction time, and gen-erates estimates with considerably better precision for com-plex datasets. 1