DBScholar

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
h74c3bc40dadfdcca
Venue
VLDB
Year
2002
Pagerank
0.00014781223
Overall Rank
683 | 95.43%
DOI
10.1016/B978-155860869-6/50017-2

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{gottlob_vldb02,
        title = {{Efficient Algorithms for Processing XPath Queries}},
        author = {Gottlob, Georg and Koch, Christoph and Pichler, Reinhard},
        journal = {PVLDB},
        series = {{VLDB} '02},
        doi = {10.1016/B978-155860869-6/50017-2},
        url = {https://doi.org/10.1016/B978-155860869-6/50017-2},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 31 of 31 citing papers.

Rank Citing Paper Year Venue Pagerank
765 Stream Processing of XPath Queries with Predicates 2003 SIGMOD 0.00014108028
1,155 The Lixto Data Extraction Project - Back and Forth between Theory and Practice 2004 PODS 0.00011759744
1,606 Conjunctive Queries over Trees 2004 PODS 0.00010079487
1,983 XPath Satisfiability in the Presence of DTDs 2005 PODS 9.2451473e-05
2,195 The Complexity of XPath Query Evaluation 2003 PODS 8.8817263e-05
2,533 Path Queries on Compressed XML 2003 VLDB 8.3132165e-05
2,691 Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach 2003 VLDB 8.1124785e-05
2,830 Secure XML Querying with Security Views 2004 SIGMOD 7.9468777e-05
2,897 On the minimization of XPath queries 2003 VLDB 7.8835751e-05
2,948 Typing and Querying XML Documents: Some Complexity Bounds 2003 PODS 7.8102637e-05
3,758 Dynamic XML Documents with Distribution and Replication 2003 SIGMOD 7.0253212e-05
3,900 Mixed Mode XML Query Processing 2003 VLDB 6.9197487e-05
4,152 Two-Variable Logic on Data Trees and XML Reasoning 2006 PODS 6.7618676e-05
4,208 Processing Queries on Tree-Structured Data Efficiently 2006 PODS 6.7214366e-05
4,831 On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values 2005 PODS 6.3838625e-05
5,196 Querying in the Age of Graph Databases and Knowledge Graphs 2021 SIGMOD 6.2198467e-05
5,480 Distributed Query Evaluation with Performance Guarantees 2007 SIGMOD 6.0991082e-05
5,513 Lazy Query Evaluation for Active XML 2004 SIGMOD 6.0866688e-05
5,604 Using Partial Evaluation in Distributed Query Evaluation 2006 VLDB 6.0512827e-05
6,280 XML Transformation by Tree-Walking Transducers with Invisible Pebbles 2007 PODS 5.808525e-05
6,583 XPath, Transitive Closure Logic, and Nested Tree Walking Automata 2008 PODS 5.7240554e-05
7,612 XQuery Optimization 2003 VLDB 5.4677429e-05
8,017 Covering Indexes for XML Queries: Bisimulation - Simulation = Negation 2003 VLDB 5.390745e-05
8,045 Cost-Sensitive Reordering of Navigational Primitives 2005 SIGMOD 5.3850485e-05
8,206 SXPath - Extending XPath towards Spatial Querying on Web Documents 2011 VLDB 5.3616552e-05
8,745 Conditional XPath, the first order complete XPath dialect* 2004 PODS 5.2705676e-05
12,816 XPath Whole Query Optimization 2010 VLDB 4.9605343e-05
12,971 Efficient Algorithms for Evaluating XPath over Streams 2007 SIGMOD 4.9605343e-05
12,972 Querying XML with Update Syntax 2007 SIGMOD 4.9605343e-05
13,027 Locking-Aware Structural Join Operators for XML Query Processing 2006 SIGMOD 4.9605343e-05
13,135 Taming XPath Queries by Minimizing Wildcard Steps 2004 VLDB 4.9605343e-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
180 Holistic Twig Joins: Optimal XML Pattern Matching 2002 SIGMOD 0.00026534482
195 Algorithmics and Applications of Tree and Graph Searching 2002 PODS 0.00025589066
409 Containment and Equivalence for an XPath Fragment [Extended Abstract] 2002 PODS 0.00018797031
1,414 Typechecking for XML Transformers 2000 PODS 0.0001070948
2,238 Monadic Datalog and the Expressive Power of Languages for Web Information Extraction 2002 PODS 8.7761804e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 962 XPath Queries on Streaming Data 2003 SIGMOD
2 5,391 Buffering in Query Evaluation over XML Streams 2005 PODS
3 2,726 A Framework for Using Materialized XPath Views in XML Query Processing 2004 VLDB
4 12,873 Efficient Rewriting of XPath Queries Using Query Set Specifications 2009 VLDB
5 3,755 On the Memory Requirements of XPath Evaluation over XML Streams 2004 PODS
6 2,897 On the minimization of XPath queries 2003 VLDB
7 12,971 Efficient Algorithms for Evaluating XPath over Streams 2007 SIGMOD
8 14,109 XPath Evaluation in Linear Time 2008 PODS
9 2,195 The Complexity of XPath Query Evaluation 2003 PODS
10 5,527 XPath Evaluation in Linear Time with Polynomial Combined Complexity 2009 PODS