XPathLearner: an on-line self-tuning Markov histogram for XML path selectivity estimation Export

@inproceedings{citeulike:4069628, abstract = {The extensible mark-up language (XML) is gaining widespread use as a format for data exchange and storage on the World Wide Web. Queries over XML data require accurate selectivity estimation of path expressions to optimize query execution plans. Selectivity estimation of XML path expression is usually done based on summary statistics about the structure of the underlying XML repository. All previous methods require an off-line scan of the XML repository to collect the statistics. In this paper, we propose XPathLearner, a method for estimating selectivity of the most commonly used types of path expressions without looking at the XML data. XPathLearner gathers and refines the statistics using query feedback in an on-line manner and is especially suited to queries in Internet scale applications since the underlying XML repository is either inaccessible or too large to be scanned in its entirety. Besides the on-line property, our method also has two other novel features: (a) XPathLearner is workload-aware in collecting the statistics and thus can be more accurate than the more costly off-line method under tight memory constraints, and (b) XPathLearner automatically adjusts the statistics using query feedback when the underlying XML data change. We show empirically the estimation accuracy of our method using several real data sets.}, author = {Lim, Lipyeow and Wang, Min and Padmanabhan, Sriram and Vitter, Jeffrey S. and Parr, Ronald}, booktitle = {VLDB '02: Proceedings of the 28th international conference on Very Large Data Bases}, citeulike-article-id = {4069628}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1287369.1287408}, keywords = {2002, machinelearning, selectivity, self-tuning, vldb, xpath}, location = {Hong Kong, China}, pages = {442--453}, posted-at = {2009-02-19 06:35:42}, priority = {2}, publisher = {VLDB Endowment}, title = {XPathLearner: an on-line self-tuning Markov histogram for XML path selectivity estimation}, url = {http://portal.acm.org/citation.cfm?id=1287369.1287408}, year = {2002} }

TY - CONF ID - citeulike:4069628 L3 - citeulike-article-id:4069628 N2 - The extensible mark-up language (XML) is gaining widespread use as a format for data exchange and storage on the World Wide Web. Queries over XML data require accurate selectivity estimation of path expressions to optimize query execution plans. Selectivity estimation of XML path expression is usually done based on summary statistics about the structure of the underlying XML repository. All previous methods require an off-line scan of the XML repository to collect the statistics. In this paper, we propose XPathLearner, a method for estimating selectivity of the most commonly used types of path expressions without looking at the XML data. XPathLearner gathers and refines the statistics using query feedback in an on-line manner and is especially suited to queries in Internet scale applications since the underlying XML repository is either inaccessible or too large to be scanned in its entirety. Besides the on-line property, our method also has two other novel features: (a) XPathLearner is workload-aware in collecting the statistics and thus can be more accurate than the more costly off-line method under tight memory constraints, and (b) XPathLearner automatically adjusts the statistics using query feedback when the underlying XML data change. We show empirically the estimation accuracy of our method using several real data sets. CY - Hong Kong, China EP - 453 TI - XPathLearner: an on-line self-tuning Markov histogram for XML path selectivity estimation PB - VLDB Endowment T2 - VLDB '02: Proceedings of the 28th international conference on Very Large Data Bases SP - 442 KW - 2002 KW - machinelearning KW - selectivity KW - self-tuning KW - vldb KW - xpath AU - Lim, Lipyeow AU - Wang, Min AU - Padmanabhan, Sriram AU - Vitter, Jeffrey AU - Parr, Ronald PY - 2002/// UR - http://portal.acm.org/citation.cfm?id=1287369.1287408 ER -