"Efficient Filtering of XML Documents with XPath Expressions"
Abstract
We propose a novel index structure, termed XTrie, that supports
the efficient filtering of XML documents based on XPath expressions.
Our XTrie index structure offers several novel features that make
it especially attractive for large-scale publish/subscribe systems.
First, XTrie is designed to support effective filtering based on
complex XPath expressions (as opposed to simple, single-path specifications).
Second, our XTrie structure and algorithms are designed to support both ordered
and unordered matching of XML data.
Third, by indexing on sequences of element names organized in a trie structure and using
a sophisticated matching algorithm, XTrie is able to both reduce the number of
unnecessary index probes as well as avoid redundant matchings, thereby providing
extremely efficient filtering.
Our experimental results over a wide range of XML document and XPath expression
workloads demonstrate that our XTrie index structure outperforms earlier approaches
by wide margins.
[
camera-ready paper
(pdf)
(ps.gz)
|
journal version
(pdf)
(in The VLDB Journal)
|
Chee-Yong's talk slides
(ppt.gz)
]
Copyright © 2002, IEEE.
Personal use of this material is permitted. However, permission to
reprint/republish this material for advertising or promotional purposes or for
creating new collective works for resale or redistribution to servers or lists,
or to reuse any copyrighted component of this work in other works must be
obtained from the IEEE.