Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach

Summary: Tree-automata-based engine for expressive XML node-selecting queries on secondary storage; two linear passes, memory independent of data. O(m+n) time; m depends on the query; bounded-memory queries are exactly captured; each node is visited twice (optimal); experiments validate. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h5aff8f61d59383c2
Venue: VLDB
Year: 2003
Pagerank: 8.1432169e-05
Overall Rank: 2,680 | 81.99%
DOI: 10.1016/B978-012722442-8/50030-6

Incoming Non-self Citations Over Time

Authors

1. Christoph Koch (University of Edinburgh)

BibTeX Citation

@article{koch_vldb03,
        title = {{Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach}},
        author = {Koch, Christoph},
        journal = {PVLDB},
        series = {{VLDB} '03},
        doi = {10.1016/B978-012722442-8/50030-6},
        url = {https://doi.org/10.1016/B978-012722442-8/50030-6},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,154	The Lixto Data Extraction Project - Back and Forth between Theory and Practice	2004	PODS	0.00011793227
4,189	Processing Queries on Tree-Structured Data Efficiently	2006	PODS	6.7459542e-05
5,462	Distributed Query Evaluation with Performance Guarantees	2007	SIGMOD	6.1221387e-05
5,593	Using Partial Evaluation in Distributed Query Evaluation	2006	VLDB	6.073568e-05
8,022	Cost-Sensitive Reordering of Navigational Primitives	2005	SIGMOD	5.4054691e-05
8,656	Machine Models and Lower Bounds for Query Processing	2007	PODS	5.2938008e-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,813	Binary XML Storage and Query Processing in Oracle 11g	2009	VLDB	4.9793485e-05
12,924	Querying XML with Update Syntax	2007	SIGMOD	4.9793485e-05
12,995	SMOQE: A System for Providing Secure Access to XML	2006	VLDB	4.9793485e-05
13,013	Lower Bounds for Sorting with Few Random Accesses to External Memory	2005	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
247	Efficient Filtering of XML Documents for Selective Dissemination of Information	2000	VLDB	0.00023199427
356	Regular Path Queries with Constraints	1997	PODS	0.00020103855
679	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00014837097
2,223	Monadic Datalog and the Expressive Power of Languages for Web Information Extraction	2002	PODS	8.8092332e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	351	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB
2	3,184	Structure and Value Synopses for XML Data Graphs	2002	VLDB
3	4,189	Processing Queries on Tree-Structured Data Efficiently	2006	PODS
4	5,474	Running Tree Automata on Probabilistic XML	2009	PODS
5	2,525	Path Queries on Compressed XML	2003	VLDB
6	2,368	Statistical Synopses for Graph-Structured XML Databases	2002	SIGMOD
7	1,599	Conjunctive Queries over Trees	2004	PODS
8	3,746	On the Memory Requirements of XPath Evaluation over XML Streams	2004	PODS
9	12,767	XPath Whole Query Optimization	2010	VLDB
10	919	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB