Online prime labeling and generation of synopsis for XML query estimation

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

XML query optimizers use selectivity estimators to choose the best possible query execution plan. However, one the main components of most estimators is the generation of a synopsis of the XML database. In this paper, we present a novel approach for online construction of an XML synopsis based on prime labeling and counting. The resulting synopsis will be used to estimate different path and twig queries with parent-child or ancestor-descendant relationships. Besides the efficiency of the proposed approach in terms of estimation accuracy and low storage requirements, it can process streams of XML documents as they are received. We experimentally compared the proposed algorithm with one of the state-of-the-art algorithms, namely the Sampling, and it showed drastic improvement in the estimation results. For example, when allocating the same memory budget for both algorithms, the overall average error rate of our algorithm was 0.54% whereas it was 55.3% for the Sampling algorithm.

Original languageEnglish
Title of host publication2015 6th International Conference on Information and Communication Systems, ICICS 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages19-24
Number of pages6
ISBN (Electronic)9781479973491
DOIs
StatePublished - 6 May 2015

Publication series

Name2015 6th International Conference on Information and Communication Systems, ICICS 2015

Bibliographical note

Publisher Copyright:
© 2015 IEEE.

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing

Fingerprint

Dive into the research topics of 'Online prime labeling and generation of synopsis for XML query estimation'. Together they form a unique fingerprint.

Cite this