Holistic Twig Joins: Optimal XML Pattern Matching

Summary: Proposes holistic twig join TwigStack for XML twig pattern matching, encoding root-to-leaf partial matches with a chain of linked stacks and stitching them into full matches. For ancestor-descendant patterns, TwigStack is I/O and CPU optimal among sequential algorithms that read the entire input—linear in input plus final result and independent of intermediates; B-tree augmentations enable sub-linear time; experiments validate efficiency. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h98fbc0c654556cc9
Venue: SIGMOD
Year: 2002
Pagerank: 0.00026628894
Overall Rank: 178 | 98.81%
DOI: 10.1145/564691.564727

Incoming Non-self Citations Over Time

Authors

1. Nicolas Bruno (Columbia University)
2. Nick Koudas (AT&T)
3. Divesh Srivastava (AT&T)

BibTeX Citation

@inproceedings{bruno_sigmod02,
        title = {{Holistic Twig Joins: Optimal XML Pattern Matching}},
        author = {Bruno, Nicolas and Koudas, Nick and Srivastava, Divesh},
        series = {{SIGMOD} '02},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/564691.564727},
        url = {https://dl.acm.org/doi/10.1145/564691.564727},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 19 of 69 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,548	LCS-TRIM: Dynamic Programming Meets XML Indexing and Querying	2007	VLDB	5.3171525e-05
8,561	Materialized View Selection for XQuery Workloads	2012	SIGMOD	5.314012e-05
8,920	Search Driven Analysis of Heterogeneous XML Data	2009	CIDR	5.2559789e-05
8,923	Incorporating Constraints in Probabilistic XML	2008	PODS	5.2559789e-05
9,029	Lazy XML Updates: Laziness as a Virtue of Update and Structural Join Efficiency	2005	SIGMOD	5.2342004e-05
9,514	Tree-Pattern Queries on a Lightweight XML Processor	2005	VLDB	5.1692468e-05
9,679	FIX: Feature-based Indexing Technique for XML Documents	2006	VLDB	5.1430855e-05
9,862	Answering Tree Pattern Queries Using Views	2006	VLDB	5.1176676e-05
9,901	Fast Optimal Twig Joins	2010	VLDB	5.1115496e-05
12,351	Index-Assisted Hierarchical Computations in Main-Memory RDBMS	2016	VLDB	4.9793485e-05
12,643	Comments on "Stack-based Algorithms for Pattern Matching on DAGs"	2012	VLDB	4.9793485e-05
12,674	Generating Efficient Execution Plans for Vertically Partitioned XML Databases	2011	VLDB	4.9793485e-05
12,789	Cost Based Plan Selection for XPath	2009	SIGMOD	4.9793485e-05
12,849	Grouping and Optimization of XPath Expressions in DB2 pureXML	2008	SIGMOD	4.9793485e-05
12,864	StreamTX: Extracting Tuples from Streaming XML Data	2008	VLDB	4.9793485e-05
12,873	Towards a Physical XML independent XQuery/SQL/XML Engine	2008	VLDB	4.9793485e-05
12,923	Efficient Algorithms for Evaluating XPath over Streams	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

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
141	Relational Databases for Querying XML Documents: Limitations and Opportunities	1999	VLDB	0.00029294114
166	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027254612
220	An Evaluation of Non-Equijoin Algorithms	1991	VLDB	0.00024344086
482	Query Optimization for XML	1999	VLDB	0.00017598607
544	Efficiently Publishing Relational Data as XML Documents	2000	VLDB	0.00016629924
752	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014246504
994	Spatial Hash-Joins	1996	SIGMOD	0.00012636707
1,592	XPERANTO: A Middleware for Publishing Object-Relational Data as XML Documents	2000	VLDB	0.00010137967
2,637	Optimizing Queries on Files	1994	SIGMOD	8.1877616e-05
2,654	LORE: A Lightweight Object REpository for Semistructured Data	1996	SIGMOD	8.1707415e-05
3,120	Size Separation Spatial Join	1997	SIGMOD	7.6300049e-05
5,763	Algebras for Querying Text Regions (Extended Abstract)	1995	PODS	6.0035367e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,643	Comments on "Stack-based Algorithms for Pattern Matching on DAGs"	2012	VLDB
2	12,864	StreamTX: Extracting Tuples from Streaming XML Data	2008	VLDB
3	1,554	Efficient Structural Joins on Indexed XML Documents	2002	VLDB
4	12,979	Locking-Aware Structural Join Operators for XML Query Processing	2006	SIGMOD
5	4,383	From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching	2005	VLDB
6	5,421	Efficient Processing of XML Twig Queries with OR-Predicates	2004	SIGMOD
7	9,901	Fast Optimal Twig Joins	2010	VLDB
8	4,156	Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents	2006	VLDB
9	4,200	On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques	2005	SIGMOD
10	2,746	Holistic Twig Joins on Indexed XML Documents	2003	VLDB