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.00026534482
Overall Rank: 180 | 98.80%
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,568	LCS-TRIM: Dynamic Programming Meets XML Indexing and Querying	2007	VLDB	5.2994373e-05
8,586	Materialized View Selection for XQuery Workloads	2012	SIGMOD	5.2939333e-05
8,948	Search Driven Analysis of Heterogeneous XML Data	2009	CIDR	5.2361195e-05
8,951	Incorporating Constraints in Probabilistic XML	2008	PODS	5.2361195e-05
9,058	Lazy XML Updates: Laziness as a Virtue of Update and Structural Join Efficiency	2005	SIGMOD	5.214424e-05
9,552	Tree-Pattern Queries on a Lightweight XML Processor	2005	VLDB	5.1497999e-05
9,715	FIX: Feature-based Indexing Technique for XML Documents	2006	VLDB	5.1236529e-05
9,904	Answering Tree Pattern Queries Using Views	2006	VLDB	5.0983308e-05
9,943	Fast Optimal Twig Joins	2010	VLDB	5.0922518e-05
12,400	Index-Assisted Hierarchical Computations in Main-Memory RDBMS	2016	VLDB	4.9605343e-05
12,692	Comments on "Stack-based Algorithms for Pattern Matching on DAGs"	2012	VLDB	4.9605343e-05
12,723	Generating Efficient Execution Plans for Vertically Partitioned XML Databases	2011	VLDB	4.9605343e-05
12,838	Cost Based Plan Selection for XPath	2009	SIGMOD	4.9605343e-05
12,898	Grouping and Optimization of XPath Expressions in DB2 pureXML	2008	SIGMOD	4.9605343e-05
12,913	StreamTX: Extracting Tuples from Streaming XML Data	2008	VLDB	4.9605343e-05
12,921	Towards a Physical XML independent XQuery/SQL/XML Engine	2008	VLDB	4.9605343e-05
12,971	Efficient Algorithms for Evaluating XPath over Streams	2007	SIGMOD	4.9605343e-05
13,027	Locking-Aware Structural Join Operators for XML Query Processing	2006	SIGMOD	4.9605343e-05
13,135	Taming XPath Queries by Minimizing Wildcard Steps	2004	VLDB	4.9605343e-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.00029191386
167	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027156235
220	An Evaluation of Non-Equijoin Algorithms	1991	VLDB	0.00024275691
483	Query Optimization for XML	1999	VLDB	0.00017537362
546	Efficiently Publishing Relational Data as XML Documents	2000	VLDB	0.00016567886
760	Partition Based Spatial-Merge Join	1996	SIGMOD	0.0001419395
999	Spatial Hash-Joins	1996	SIGMOD	0.00012590189
1,596	XPERANTO: A Middleware for Publishing Object-Relational Data as XML Documents	2000	VLDB	0.00010099978
2,646	Optimizing Queries on Files	1994	SIGMOD	8.157239e-05
2,662	LORE: A Lightweight Object REpository for Semistructured Data	1996	SIGMOD	8.1406777e-05
3,131	Size Separation Spatial Join	1997	SIGMOD	7.6016052e-05
5,777	Algebras for Querying Text Regions (Extended Abstract)	1995	PODS	5.9810913e-05

Semantically Similar Papers

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