Database Paper Browser

Back to papers

Efficient Algorithms for Processing XPath Queries

Summary: Empirical analysis: popular XPath processors exhibit exponential worst-case query time. Introduces main-memory algorithms with polynomial-time combined evaluation and two XPath fragments enabling linear-time query processing. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
8836
Venue
VLDB
Year
2002
Pagerank
0.00017731096
Overall Rank
713 | 95.05%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 31 of 31 citing papers.

Rank Citing Paper Year Venue Pagerank
831 Stream Processing of XPath Queries with Predicates 2003 SIGMOD 0.00016171218
1,095 The Lixto Data Extraction Project - Back and Forth between Theory and Practice 2004 PODS 0.00014126427
1,663 Conjunctive Queries over Trees 2004 PODS 0.00010977096
1,848 Typing and Querying XML Documents: Some Complexity Bounds 2003 PODS 0.00010330772
1,929 XPath Satisfiability in the Presence of DTDs 2005 PODS 0.00010058897
1,947 Secure XML Querying with Security Views 2004 SIGMOD 0.00010000435
2,248 The Complexity of XPath Query Evaluation 2003 PODS 9.2038466e-05
2,507 Path Queries on Compressed XML 2003 VLDB 8.6311009e-05
2,855 Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach 2003 VLDB 8.0059865e-05
3,084 On the minimization of Xpath queries 2003 VLDB 7.6011919e-05
3,117 Processing Queries on Tree-Structured Data Efficiently 2006 PODS 7.5407318e-05
3,679 Dynamic XML Documents with Distribution and Replication 2003 SIGMOD 6.8516241e-05
4,073 Two-Variable Logic on Data Trees and XML Reasoning 2006 PODS 6.4719397e-05
4,207 Mixed Mode XML Query Processing 2003 VLDB 6.359465e-05
4,611 On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values 2005 PODS 6.0488752e-05
5,139 Lazy Query Evaluation for Active XML 2004 SIGMOD 5.6686638e-05
5,188 Using Partial Evaluation in Distributed Query Evaluation 2006 VLDB 5.6385696e-05
5,317 Distributed Query Evaluation with Performance Guarantees 2007 SIGMOD 5.5719038e-05
5,716 XML Transformation by Tree-Walking Transducers with Invisible Pebbles 2007 PODS 5.3561157e-05
5,792 Querying in the Age of Graph Databases and Knowledge Graphs 2021 SIGMOD 5.325937e-05
6,150 XPath, Transitive Closure Logic, and Nested Tree Walking Automata 2008 PODS 5.1846373e-05
6,872 XQuery Optimization 2003 VLDB 4.8991822e-05
7,681 SXPath - Extending XPath towards Spatial Querying on Web Documents 2011 VLDB 4.6804276e-05
7,763 Covering Indexes for XML Queries: Bisimulation - Simulation = Negation 2003 VLDB 4.6575679e-05
7,848 Cost-Sensitive Reordering of Navigational Primitives 2005 SIGMOD 4.6362551e-05
8,314 Conditional XPath, the first order complete XPath dialect* 2004 PODS 4.5435639e-05
12,281 XPath Whole Query Optimization 2010 VLDB 4.1945683e-05
12,439 Efficient Algorithms for Evaluating XPath over Streams 2007 SIGMOD 4.1945683e-05
12,440 Querying XML with Update Syntax 2007 SIGMOD 4.1945683e-05
12,496 Locking-Aware Structural Join Operators for XML Query Processing 2006 SIGMOD 4.1945683e-05
12,605 Taming XPath Queries by Minimizing Wildcard Steps 2004 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank Cited Paper Year Venue Pagerank
171 Algorithmics and Applications of Tree and Graph Searching 2002 PODS 0.00038830709
240 Holistic Twig Joins: Optimal XML Pattern Matching 2002 SIGMOD 0.00031603463
499 Containment and Equivalence for an XPath Fragment [Extended Abstract] 2002 PODS 0.000216753
970 Typechecking for XML Transformers 2000 PODS 0.00014939578
1,370 Monadic Datalog and the Expressive Power of Languages for Web Information Extraction 2002 PODS 0.00012338027
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
987 XPath Queries on Streaming Data 2003 SIGMOD 0.00014819204
5,248 Buffering in Query Evaluation over XML Streams 2005 PODS 5.6056584e-05
2,977 A Framework for Using Materialized XPath Views in XML Query Processing 2004 VLDB 7.7876083e-05
12,340 Efficient Rewriting of XPath Queries Using Query Set Specifications 2009 VLDB 4.1945683e-05
3,695 On the Memory Requirements of XPath Evaluation over XML Streams 2004 PODS 6.8345021e-05
3,084 On the minimization of Xpath queries 2003 VLDB 7.6011919e-05
12,439 Efficient Algorithms for Evaluating XPath over Streams 2007 SIGMOD 4.1945683e-05
13,553 XPath Evaluation in Linear Time 2008 PODS -
2,248 The Complexity of XPath Query Evaluation 2003 PODS 9.2038466e-05
4,663 XPath Evaluation in Linear Time with Polynomial Combined Complexity 2009 PODS 6.0128493e-05