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: 1477
Venue: PODS
Year: 2009
Pagerank: 6.3394897e-05
Overall Rank: 5,314 | 63.07%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Pawel Parys

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,242	JSON: Data model, Query languages and Schema specification	2017	PODS	7.6762304e-05
7,894	SXPath - Extending XPath towards Spatial Querying on Web Documents	2011	VLDB	5.5907877e-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,566	XPath Evaluation in Linear Time	2008	PODS	-

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,348	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB	5.1725247e-05
4,432	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS	6.7624383e-05
3,606	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS	7.3287071e-05
1,532	Conjunctive Queries over Trees	2004	PODS	0.00010509919
12,448	Efficient Algorithms for Evaluating XPath over Streams	2007	SIGMOD	5.1725247e-05
2,762	On the minimization of Xpath queries	2003	VLDB	8.2183977e-05
13,599	Polynomial Time Fragments of XPath with Variables	2007	PODS	-
653	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00015399469
2,086	The Complexity of XPath Query Evaluation	2003	PODS	9.2607172e-05
13,566	XPath Evaluation in Linear Time	2008	PODS	-