Efficient Algorithms for Evaluating XPath over Streams

Summary: Proposes two streaming XPath algorithms, LQ (lazy) and EQ (eager), for Univariate XPath over streams. They achieve the O(|D||Q|) streaming time bound in one pass—the first to do so; EQ offers optimal buffering-space, and experiments show practical gains over prior stream-querying methods. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h879a95f491bb7f65
Venue: SIGMOD
Year: 2007
Pagerank: 4.9769913e-05
Overall Rank: 12,929 | 13.11%
DOI: 10.1145/1247480.1247512

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Gang Gou (North Carolina State University)
2. Rada Chirkova (North Carolina State University)

BibTeX Citation

@inproceedings{gou_sigmod07,
        title = {{Efficient Algorithms for Evaluating XPath over Streams}},
        author = {Gou, Gang and Chirkova, Rada},
        series = {{SIGMOD} '07},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1247480.1247512},
        url = {https://dl.acm.org/doi/10.1145/1247480.1247512},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
179	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00026617591
680	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.0001483008
760	Stream Processing of XPath Queries with Predicates	2003	SIGMOD	0.00014154656
1,111	A Transducer-Based XML Query Processor	2002	VLDB	0.00011978534
1,539	The BEA/XQRL Streaming XQuery Processor	2003	VLDB	0.00010311535
2,179	The Complexity of XPath Query Evaluation	2003	PODS	8.9111534e-05
2,935	Typing and Querying XML Documents: Some Complexity Bounds	2003	PODS	7.8361406e-05
3,586	Schema-based Scheduling of Event Processors and Buffer Minimization for Queries on Structured Data Streams	2004	VLDB	7.1859239e-05
3,747	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS	7.052433e-05
5,373	Buffering in Query Evaluation over XML Streams	2005	PODS	6.156821e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,505	XPath Evaluation in Linear Time with Polynomial Combined Complexity	2009	PODS
2	12,830	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
3	2,179	The Complexity of XPath Query Evaluation	2003	PODS
4	14,069	XPath Evaluation in Linear Time	2008	PODS
5	760	Stream Processing of XPath Queries with Predicates	2003	SIGMOD
6	680	Efficient Algorithms for Processing XPath Queries	2002	VLDB
7	4,680	Efficient Evaluation of XQuery over Streaming Data	2005	VLDB
8	3,747	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS
9	958	XPath Queries on Streaming Data	2003	SIGMOD
10	5,373	Buffering in Query Evaluation over XML Streams	2005	PODS