TY - GEN
T1 - An efficient XPath query processor for XML streams
AU - Chen, Yi
AU - Davidson, Susan B.
AU - Zheng, Yifeng
PY - 2006
Y1 - 2006
N2 - Streaming XPath evaluation algorithms must record a potentially exponential number of pattern matches when both predicates and descendant axes are present in queries, and the XML data is recursive. In this paper, we use a compact data structure to encode these pattern matches rather than storing them explicitly. We then propose a polynomial time streaming algorithm to evaluate XPath queries by probing the data structure in a lazy fashion. Extensive experiments show that our approach not only has a good theoretical complexity bound but is also efficient in practice.
AB - Streaming XPath evaluation algorithms must record a potentially exponential number of pattern matches when both predicates and descendant axes are present in queries, and the XML data is recursive. In this paper, we use a compact data structure to encode these pattern matches rather than storing them explicitly. We then propose a polynomial time streaming algorithm to evaluate XPath queries by probing the data structure in a lazy fashion. Extensive experiments show that our approach not only has a good theoretical complexity bound but is also efficient in practice.
UR - http://www.scopus.com/inward/record.url?scp=33749612519&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33749612519&partnerID=8YFLogxK
U2 - 10.1109/ICDE.2006.18
DO - 10.1109/ICDE.2006.18
M3 - Conference contribution
AN - SCOPUS:33749612519
SN - 0769525709
SN - 9780769525709
T3 - Proceedings - International Conference on Data Engineering
SP - 79
BT - Proceedings of the 22nd International Conference on Data Engineering, ICDE '06
T2 - 22nd International Conference on Data Engineering, ICDE '06
Y2 - 3 April 2006 through 7 April 2006
ER -