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
8837
Venue
VLDB
Year
2002
Pagerank
0.00017714027
Overall Rank
712 | 95.06%
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
827 Stream Processing of XPath Queries with Predicates 2003 SIGMOD 0.00016155855
1,094 The Lixto Data Extraction Project - Back and Forth between Theory and Practice 2004 PODS 0.00014105105
1,662 Conjunctive Queries over Trees 2004 PODS 0.00010966423
1,854 Typing and Querying XML Documents: Some Complexity Bounds 2003 PODS 0.00010320817
1,933 XPath Satisfiability in the Presence of DTDs 2005 PODS 0.00010049404
1,951 Secure XML Querying with Security Views 2004 SIGMOD 9.9907874e-05
2,250 The Complexity of XPath Query Evaluation 2003 PODS 9.1949563e-05
2,509 Path Queries on Compressed XML 2003 VLDB 8.6250598e-05
2,862 Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach 2003 VLDB 7.9982917e-05
3,089 On the minimization of Xpath queries 2003 VLDB 7.5938563e-05
3,115 Processing Queries on Tree-Structured Data Efficiently 2006 PODS 7.5414053e-05
3,681 Dynamic XML Documents with Distribution and Replication 2003 SIGMOD 6.8449871e-05
4,076 Two-Variable Logic on Data Trees and XML Reasoning 2006 PODS 6.4657154e-05
4,205 Mixed Mode XML Query Processing 2003 VLDB 6.354571e-05
4,612 On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values 2005 PODS 6.0428289e-05
5,140 Lazy Query Evaluation for Active XML 2004 SIGMOD 5.6632963e-05
5,190 Using Partial Evaluation in Distributed Query Evaluation 2006 VLDB 5.633429e-05
5,324 Distributed Query Evaluation with Performance Guarantees 2007 SIGMOD 5.5668659e-05
5,726 XML Transformation by Tree-Walking Transducers with Invisible Pebbles 2007 PODS 5.3509726e-05
5,802 Querying in the Age of Graph Databases and Knowledge Graphs 2021 SIGMOD 5.3209544e-05
6,153 XPath, Transitive Closure Logic, and Nested Tree Walking Automata 2008 PODS 5.1796878e-05
6,876 XQuery Optimization 2003 VLDB 4.8947451e-05
7,682 SXPath - Extending XPath towards Spatial Querying on Web Documents 2011 VLDB 4.6759376e-05
7,763 Covering Indexes for XML Queries: Bisimulation - Simulation = Negation 2003 VLDB 4.6531059e-05
7,852 Cost-Sensitive Reordering of Navigational Primitives 2005 SIGMOD 4.631832e-05
8,308 Conditional XPath, the first order complete XPath dialect* 2004 PODS 4.5392079e-05
12,289 XPath Whole Query Optimization 2010 VLDB 4.1905499e-05
12,448 Efficient Algorithms for Evaluating XPath over Streams 2007 SIGMOD 4.1905499e-05
12,449 Querying XML with Update Syntax 2007 SIGMOD 4.1905499e-05
12,505 Locking-Aware Structural Join Operators for XML Query Processing 2006 SIGMOD 4.1905499e-05
12,614 Taming XPath Queries by Minimizing Wildcard Steps 2004 VLDB 4.1905499e-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
172 Algorithmics and Applications of Tree and Graph Searching 2002 PODS 0.00038837872
239 Holistic Twig Joins: Optimal XML Pattern Matching 2002 SIGMOD 0.00031581944
499 Containment and Equivalence for an XPath Fragment [Extended Abstract] 2002 PODS 0.00021654356
970 Typechecking for XML Transformers 2000 PODS 0.00014924533
1,374 Monadic Datalog and the Expressive Power of Languages for Web Information Extraction 2002 PODS 0.00012325543
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
988 XPath Queries on Streaming Data 2003 SIGMOD 0.00014805516
5,253 Buffering in Query Evaluation over XML Streams 2005 PODS 5.6002448e-05
2,980 A Framework for Using Materialized XPath Views in XML Query Processing 2004 VLDB 7.7800968e-05
12,348 Efficient Rewriting of XPath Queries Using Query Set Specifications 2009 VLDB 4.1905499e-05
3,697 On the Memory Requirements of XPath Evaluation over XML Streams 2004 PODS 6.8281158e-05
3,089 On the minimization of Xpath queries 2003 VLDB 7.5938563e-05
12,448 Efficient Algorithms for Evaluating XPath over Streams 2007 SIGMOD 4.1905499e-05
13,566 XPath Evaluation in Linear Time 2008 PODS -
2,250 The Complexity of XPath Query Evaluation 2003 PODS 9.1949563e-05
4,660 XPath Evaluation in Linear Time with Polynomial Combined Complexity 2009 PODS 6.0070615e-05