XPath Evaluation in Linear Time with Polynomial Combined Complexity

Summary: Fragment of XPath 1.0 allowing attribute/text value comparisons. Gives an evaluation algorithm with linear data complexity and polynomial combined complexity (linear in document size, polynomial in query size), improving prior exponential-in-query bounds. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1476
Venue: PODS
Year: 2009
Pagerank: 6.2427638e-05
Overall Rank: 5,371 | 63.16%
DOI: 10.1145/1559795.1559805

Incoming Non-self Citations Over Time

Authors

1. Pawel Parys (University of Warsaw)

BibTeX Citation

@inproceedings{parys_pods09,
        address = {New York, NY, USA},
        series = {{PODS} '09},
        title = {{XPath Evaluation in Linear Time with Polynomial Combined Complexity}},
        url = {https://dl.acm.org/doi/10.1145/1559795.1559805},
        doi = {10.1145/1559795.1559805},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Parys, Pawel},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,287	JSON: Data model, Query languages and Schema specification	2017	PODS	7.5587639e-05
8,022	SXPath - Extending XPath towards Spatial Querying on Web Documents	2011	VLDB	5.5055198e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
13,753	XPath Evaluation in Linear Time	2008	PODS	-

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,534	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB
2	4,504	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS
3	3,659	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS
4	1,564	Conjunctive Queries over Trees	2004	PODS
5	12,633	Efficient Algorithms for Evaluating XPath over Streams	2007	SIGMOD
6	2,817	On the minimization of XPath queries	2003	VLDB
7	13,786	Polynomial Time Fragments of XPath with Variables	2007	PODS
8	666	Efficient Algorithms for Processing XPath Queries	2002	VLDB
9	2,132	The Complexity of XPath Query Evaluation	2003	PODS
10	13,753	XPath Evaluation in Linear Time	2008	PODS