|
Published Articles >> Table of Contents >> Abstract
19th International Conference on Data Engineering (ICDE'03)
p. 139
Navigation- vs. Index-Based XML Multi-Query Processing
Nicolas Bruno, Columbia University
Luis Gravano, Columbia University
Nick Koudas, AT&T Labs-Research
Divesh Srivastava, AT&T Labs-Research
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICDE.2003.1260788
Send link to a friend
| Abstract |
|
XML path queries form the basis of complex filtering of XML data. Most current XML path query processing techniques can be divided in two groups. Navigation-based algorithms compute results by analyzing an input document one tag at a time. In contrast, index-based algorithms take advantage of precomputed numbering schemes over the input XML document. In this paper we introduce a new index-based technique, Index-Filter, to answer multiple XML path queries. Index-Filter uses indexes built over the document tags to avoid processing large portions of the input document that are guaranteed not to be part of any match. We analyze Index-Filter and compare it against Y-Filter, a state-of-the-art navigation-based technique. We show that both techniques have their advantages, and we discuss the scenarios under which each technique is superior to the other one. In particular, we show that while most XML path query processing techniques work off SAX events, in some cases it pays off to preprocess the input document, augmenting it with auxiliary information that can be used to evaluate the queries faster. We present experimental results over real and synthetic XML documents that validate our claims.
|
 Additional Information
|
Citation:
Nicolas Bruno, Luis Gravano, Nick Koudas, Divesh Srivastava,
"Navigation- vs. Index-Based XML Multi-Query Processing,"
icde,
p. 139,
19th International Conference on Data Engineering (ICDE'03),
2003
|
|
