Stream processing of XPath queries with predicates
Top Cited Papers
- 9 June 2003
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 419-430
- https://doi.org/10.1145/872757.872809
Abstract
We consider the problem of evaluating large numbers of XPath filters, each with many predicates, on a stream of XML documents. The solution we propose is to lazily construct a single deterministic pushdown automata, called the XPush Machine from the given XPath fllters. We describe a number of optimization techniques to make the lazy XPush machine more efficient, both in terms of space and time. The combination of these optimizations results in high, sustained throughput. For example, if the total number of atomic predicates in the filters is up to 200000, then the throughput is at least 0.5 MB/sec: it increases to 4.5 MB/sec when each fllter contains a single predicate.Keywords
This publication has 10 references indexed in Scilit:
- An evaluation of regular path expressions with qualifiers against XML streamsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Mesh-based content routing using XMLPublished by Association for Computing Machinery (ACM) ,2001
- Monitoring XML data on the WebPublished by Association for Computing Machinery (ACM) ,2001
- NiagaraCQPublished by Association for Computing Machinery (ACM) ,2000
- Efficient Preprocessing of Simple Binary Pattern ForestsJournal of Algorithms, 1996
- Ordered and Unordered Tree InclusionSIAM Journal on Computing, 1995
- More efficient bottom-up multi-pattern matching in treesTheoretical Computer Science, 1992
- Pattern Matching in TreesJournal of the ACM, 1982
- AlternationJournal of the ACM, 1981
- Efficient string matchingCommunications of the ACM, 1975