An efficient XPath query processor for XML streams

Yi Chen, Susan B. Davidson, Yifeng Zheng

Research output: Chapter in Book/Report/Conference proceedingConference contribution

76 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 22nd International Conference on Data Engineering, ICDE '06
Number of pages1
DOIs
StatePublished - Oct 17 2006
Externally publishedYes
Event22nd International Conference on Data Engineering, ICDE '06 - Atlanta, GA, United States
Duration: Apr 3 2006Apr 7 2006

Publication series

NameProceedings - International Conference on Data Engineering
Volume2006
ISSN (Print)1084-4627

Other

Other22nd International Conference on Data Engineering, ICDE '06
Country/TerritoryUnited States
CityAtlanta, GA
Period4/3/064/7/06

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Information Systems

Fingerprint

Dive into the research topics of 'An efficient XPath query processor for XML streams'. Together they form a unique fingerprint.

Cite this