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.0128493e-05
Overall Rank: 4,663 | 67.57%
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
2,781	JSON: Data model, Query languages and Schema specification	2017	PODS	8.1305074e-05
7,681	SXPath - Extending XPath towards Spatial Querying on Web Documents	2011	VLDB	4.6804276e-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,553	XPath Evaluation in Linear Time	2008	PODS	-

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,340	Efficient Rewriting of XPath Queries Using Query Set Specifications	2009	VLDB	4.1945683e-05
4,366	The Complexity of Query Containment in Expressive Fragments of XPath 2.0	2007	PODS	6.2538592e-05
3,695	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS	6.8345021e-05
1,663	Conjunctive Queries over Trees	2004	PODS	0.00010977096
12,439	Efficient Algorithms for Evaluating XPath over Streams	2007	SIGMOD	4.1945683e-05
3,084	On the minimization of Xpath queries	2003	VLDB	7.6011919e-05
13,586	Polynomial Time Fragments of XPath with Variables	2007	PODS	-
713	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00017731096
2,248	The Complexity of XPath Query Evaluation	2003	PODS	9.2038466e-05
13,553	XPath Evaluation in Linear Time	2008	PODS	-