Efficient Processing of XML Twig Queries with OR-Predicates

Summary: Holistic processing of XML twig queries with OR-predicates (no decomposition). Proposes a merge-based algorithm for sorted XML data and an index-based algorithm for indexed XML data; demonstrates that holistic processing outperforms decomposition, with indexing particularly effective for large inputs and small outputs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3507
Venue: SIGMOD
Year: 2004
Pagerank: 5.4268403e-05
Overall Rank: 5,574 | 61.23%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,354	From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching	2005	VLDB	6.262393e-05
4,364	Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents	2006	VLDB	6.2546168e-05
4,587	On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques	2005	SIGMOD	6.0658154e-05
7,584	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB	4.7041255e-05
12,496	Locking-Aware Structural Join Operators for XML Query Processing	2006	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
61	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00064329285
193	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00035610321
240	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00031603463
391	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00024564567
415	A Fast Index for Semistructured Data	2001	VLDB	0.00023814619
501	Query Optimization for XML	1999	VLDB	0.00021530411
817	Covering Indexes for Branching Path Queries	2002	SIGMOD	0.00016352717
1,235	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00013120483
1,733	Efficient Structural Joins on Indexed XML Documents	2002	VLDB	0.00010724888
2,168	ViST: A Dynamic Index Method for Querying XML Data by Tree Structures	2003	SIGMOD	9.3848723e-05
2,676	LORE: A Lightweight Object REpository for Semistructured Data	1996	SIGMOD	8.3274001e-05
3,120	Holistic Twig Joins on Indexed XML Documents	2003	VLDB	7.5295938e-05
4,207	Mixed Mode XML Query Processing	2003	VLDB	6.359465e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,207	Mixed Mode XML Query Processing	2003	VLDB	6.359465e-05
9,178	Tree-Pattern Queries on a Lightweight XML Processor	2005	VLDB	4.3828426e-05
2,978	Matching Twigs in Probabilistic XML	2007	VLDB	7.7845728e-05
4,354	From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching	2005	VLDB	6.262393e-05
4,364	Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents	2006	VLDB	6.2546168e-05
12,496	Locking-Aware Structural Join Operators for XML Query Processing	2006	SIGMOD	4.1945683e-05
240	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00031603463
4,587	On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques	2005	SIGMOD	6.0658154e-05
9,594	Fast Optimal Twig Joins	2010	VLDB	4.3197044e-05
3,120	Holistic Twig Joins on Indexed XML Documents	2003	VLDB	7.5295938e-05