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: 3569
Venue: SIGMOD
Year: 2004
Pagerank: 6.2770047e-05
Overall Rank: 5,298 | 63.66%
DOI: 10.1145/1007568.1007578

Incoming Non-self Citations Over Time

Authors

1. Haifeng Jiang (Hong Kong University of Science and Technology)
2. Hongjun Lu (Hong Kong University of Science and Technology)
3. Wei Wang (Hong Kong University of Science and Technology)

BibTeX Citation

@inproceedings{jiang_sigmod04,
        title = {{Efficient Processing of XML Twig Queries with OR-Predicates}},
        author = {Jiang, Haifeng and Lu, Hongjun and Wang, Wei},
        series = {{SIGMOD} '04},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1007568.1007578},
        url = {https://dl.acm.org/doi/10.1145/1007568.1007578},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,066	Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents	2006	VLDB	6.9298871e-05
4,113	On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques	2005	SIGMOD	6.8941988e-05
4,294	From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching	2005	VLDB	6.7780241e-05
7,622	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB	5.5806644e-05
12,689	Locking-Aware Structural Join Operators for XML Query Processing	2006	SIGMOD	5.093636e-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
48	DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases	1997	VLDB	0.00044033592
163	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027839792
175	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00027226333
341	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00020704572
430	A Fast Index for Semistructured Data	2001	VLDB	0.00018600166
470	Query Optimization for XML	1999	VLDB	0.00017965707
718	Covering Indexes for Branching Path Queries	2002	SIGMOD	0.00014642961
1,068	Minimization of Tree Pattern Queries	2001	SIGMOD	0.00012326498
1,523	Efficient Structural Joins on Indexed XML Documents	2002	VLDB	0.00010502089
1,849	ViST: A Dynamic Index Method for Querying XML Data by Tree Structures	2003	SIGMOD	9.6191884e-05
2,603	LORE: A Lightweight Object REpository for Semistructured Data	1996	SIGMOD	8.3535371e-05
2,694	Holistic Twig Joins on Indexed XML Documents	2003	VLDB	8.2469414e-05
3,814	Mixed Mode XML Query Processing	2003	VLDB	7.1026815e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,814	Mixed Mode XML Query Processing	2003	VLDB
2	9,338	Tree-Pattern Queries on a Lightweight XML Processor	2005	VLDB
3	3,075	Matching Twigs in Probabilistic XML	2007	VLDB
4	4,294	From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching	2005	VLDB
5	12,689	Locking-Aware Structural Join Operators for XML Query Processing	2006	SIGMOD
6	4,066	Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents	2006	VLDB
7	175	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD
8	4,113	On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques	2005	SIGMOD
9	9,730	Fast Optimal Twig Joins	2010	VLDB
10	2,694	Holistic Twig Joins on Indexed XML Documents	2003	VLDB