QuickStack: A Fast Algorithm for XML Query Matching
DocUID: 2008-012 Full Text:
PDF Author: Iyad Batal, Alexandros Labrinidis
Abstract: With the increasing popularity of XML for data representation and exchange, much research has been done for providing an efficient way to evaluate twig patterns in an XML database. As a result, many holistic join algorithms have been developed, most of which are derivatives of the well-known TwigStack algorithm. However, these algorithms still apply a two phase processing scheme: first identify all root-toleaf path solutions and then join these intermediate solutions to form the twig results. In this paper, we first propose a novel algorithm, QuickStack, for matching single path queries. The proposed algorithm extensively optimizes the PathStack algorithm by effectively skipping the ancestor and descendant elements that do not participate in the results. Secondly, we generalize QuickStack to answer twig pattern queries. Unlike the previous algorithms, QuickStack joins the intermediate path solutions incrementally while evaluating the root-to-leaf paths of the twig query. Our extensive performance study, over a range of synthetic and real world datasets, shows that QuickStack provides a drastic improvement gain over TwigStack for a wide variety of both single path and twig queries. Finally, we compare our algorithm with YFilter for answering multiple XML queries.
Keywords: XML, query processing
Published In: Technical Report TR-08-155, Department of Computer Science, University of Pittsburgh
Year Published: 2008
Project: Others Subject Area: Others
Publication Type: Technical Report
Sponsor: Others