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.00014837097
Overall Rank
679 | 95.44%
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
760 Stream Processing of XPath Queries with Predicates 2003 SIGMOD 0.00014161342
1,154 The Lixto Data Extraction Project - Back and Forth between Theory and Practice 2004 PODS 0.00011793227
1,599 Conjunctive Queries over Trees 2004 PODS 0.00010117703
1,976 XPath Satisfiability in the Presence of DTDs 2005 PODS 9.2797174e-05
2,177 The Complexity of XPath Query Evaluation 2003 PODS 8.9153711e-05
2,525 Path Queries on Compressed XML 2003 VLDB 8.343313e-05
2,680 Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach 2003 VLDB 8.1432169e-05
2,816 Secure XML Querying with Security Views 2004 SIGMOD 7.9770184e-05
2,881 On the minimization of XPath queries 2003 VLDB 7.9134117e-05
2,934 Typing and Querying XML Documents: Some Complexity Bounds 2003 PODS 7.839851e-05
3,751 Dynamic XML Documents with Distribution and Replication 2003 SIGMOD 7.0519156e-05
3,889 Mixed Mode XML Query Processing 2003 VLDB 6.9447533e-05
4,135 Two-Variable Logic on Data Trees and XML Reasoning 2006 PODS 6.7875138e-05
4,189 Processing Queries on Tree-Structured Data Efficiently 2006 PODS 6.7459542e-05
4,807 On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values 2005 PODS 6.4079967e-05
5,174 Querying in the Age of Graph Databases and Knowledge Graphs 2021 SIGMOD 6.243251e-05
5,462 Distributed Query Evaluation with Performance Guarantees 2007 SIGMOD 6.1221387e-05
5,490 Lazy Query Evaluation for Active XML 2004 SIGMOD 6.1094192e-05
5,593 Using Partial Evaluation in Distributed Query Evaluation 2006 VLDB 6.073568e-05
6,265 XML Transformation by Tree-Walking Transducers with Invisible Pebbles 2007 PODS 5.8305555e-05
6,571 XPath, Transitive Closure Logic, and Nested Tree Walking Automata 2008 PODS 5.7457654e-05
7,592 XQuery Optimization 2003 VLDB 5.4880486e-05
7,995 Covering Indexes for XML Queries: Bisimulation - Simulation = Negation 2003 VLDB 5.4111901e-05
8,022 Cost-Sensitive Reordering of Navigational Primitives 2005 SIGMOD 5.4054691e-05
8,182 SXPath - Extending XPath towards Spatial Querying on Web Documents 2011 VLDB 5.3819907e-05
8,717 Conditional XPath, the first order complete XPath dialect* 2004 PODS 5.2905577e-05
12,767 XPath Whole Query Optimization 2010 VLDB 4.9793485e-05
12,923 Efficient Algorithms for Evaluating XPath over Streams 2007 SIGMOD 4.9793485e-05
12,924 Querying XML with Update Syntax 2007 SIGMOD 4.9793485e-05
12,979 Locking-Aware Structural Join Operators for XML Query Processing 2006 SIGMOD 4.9793485e-05
13,088 Taming XPath Queries by Minimizing Wildcard Steps 2004 VLDB 4.9793485e-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
178 Holistic Twig Joins: Optimal XML Pattern Matching 2002 SIGMOD 0.00026628894
192 Algorithmics and Applications of Tree and Graph Searching 2002 PODS 0.00025659453
409 Containment and Equivalence for an XPath Fragment [Extended Abstract] 2002 PODS 0.00018868173
1,406 Typechecking for XML Transformers 2000 PODS 0.00010749818
2,223 Monadic Datalog and the Expressive Power of Languages for Web Information Extraction 2002 PODS 8.8092332e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 958 XPath Queries on Streaming Data 2003 SIGMOD
2 5,368 Buffering in Query Evaluation over XML Streams 2005 PODS
3 2,715 A Framework for Using Materialized XPath Views in XML Query Processing 2004 VLDB
4 12,824 Efficient Rewriting of XPath Queries Using Query Set Specifications 2009 VLDB
5 3,746 On the Memory Requirements of XPath Evaluation over XML Streams 2004 PODS
6 2,881 On the minimization of XPath queries 2003 VLDB
7 12,923 Efficient Algorithms for Evaluating XPath over Streams 2007 SIGMOD
8 14,064 XPath Evaluation in Linear Time 2008 PODS
9 2,177 The Complexity of XPath Query Evaluation 2003 PODS
10 5,502 XPath Evaluation in Linear Time with Polynomial Combined Complexity 2009 PODS