XPath Evaluation in Linear Time
Summary: Studying an XPath fragment restricted to attribute-equality tests, the paper shows that for any fixed unary query the set of answer nodes can be computed in time linear in the document size. Establishes optimal data-complexity (linear-time) evaluation and clarifies the tractability boundary for XPath with attribute equalities. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Mikołaj Bojańczyk
- 2. Paweł Parys
Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,663 | XPath Evaluation in Linear Time with Polynomial Combined Complexity | 2009 | PODS | 6.0128493e-05 |
| 13,484 | Efficient Evaluation for a Temporal Logic on Changing XML Documents | 2011 | PODS | - |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 0 of 0 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
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 |
| 3,084 | On the minimization of Xpath queries | 2003 | VLDB | 7.6011919e-05 |
| 3,695 | On the Memory Requirements of XPath Evaluation over XML Streams | 2004 | PODS | 6.8345021e-05 |
| 5,248 | Buffering in Query Evaluation over XML Streams | 2005 | PODS | 5.6056584e-05 |
| 4,625 | On Testing Satisfiability of Tree Pattern Queries | 2004 | VLDB | 6.0406081e-05 |
| 13,586 | Polynomial Time Fragments of XPath with Variables | 2007 | PODS | - |
| 2,248 | The Complexity of XPath Query Evaluation | 2003 | PODS | 9.2038466e-05 |
| 12,439 | Efficient Algorithms for Evaluating XPath over Streams | 2007 | SIGMOD | 4.1945683e-05 |
| 713 | Efficient Algorithms for Processing XPath Queries | 2002 | VLDB | 0.00017731096 |
| 4,663 | XPath Evaluation in Linear Time with Polynomial Combined Complexity | 2009 | PODS | 6.0128493e-05 |