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: 3421
Venue: SIGMOD
Year: 2002
Pagerank: 0.00027226333
Overall Rank: 175 | 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,416	Materialized View Selection for XQuery Workloads	2012	SIGMOD	5.429311e-05
8,422	LCS-TRIM: Dynamic Programming Meets XML Indexing and Querying	2007	VLDB	5.4278338e-05
8,757	Search Driven Analysis of Heterogeneous XML Data	2009	CIDR	5.3766157e-05
8,761	Incorporating Constraints in Probabilistic XML	2008	PODS	5.3766157e-05
8,870	Lazy XML Updates: Laziness as a Virtue of Update and Structural Join Efficiency	2005	SIGMOD	5.3543292e-05
9,338	Tree-Pattern Queries on a Lightweight XML Processor	2005	VLDB	5.2874872e-05
9,496	FIX: Feature-based Indexing Technique for XML Documents	2006	VLDB	5.2611263e-05
9,687	Answering Tree Pattern Queries Using Views	2006	VLDB	5.2351299e-05
9,730	Fast Optimal Twig Joins	2010	VLDB	5.2288699e-05
12,057	Index-Assisted Hierarchical Computations in Main-Memory RDBMS	2016	VLDB	5.093636e-05
12,352	Comments on "Stack-based Algorithms for Pattern Matching on DAGs"	2012	VLDB	5.093636e-05
12,383	Generating Efficient Execution Plans for Vertically Partitioned XML Databases	2011	VLDB	5.093636e-05
12,499	Cost Based Plan Selection for XPath	2009	SIGMOD	5.093636e-05
12,559	Grouping and Optimization of XPath Expressions in DB2 pureXML	2008	SIGMOD	5.093636e-05
12,574	StreamTX: Extracting Tuples from Streaming XML Data	2008	VLDB	5.093636e-05
12,583	Towards a Physical XML independent XQuery/SQL/XML Engine	2008	VLDB	5.093636e-05
12,633	Efficient Algorithms for Evaluating XPath over Streams	2007	SIGMOD	5.093636e-05
12,689	Locking-Aware Structural Join Operators for XML Query Processing	2006	SIGMOD	5.093636e-05
12,798	Taming XPath Queries by Minimizing Wildcard Steps	2004	VLDB	5.093636e-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
137	Relational Databases for Querying XML Documents: Limitations and Opportunities	1999	VLDB	0.00029877792
163	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027839792
210	An Evaluation of Non-Equijoin Algorithms	1991	VLDB	0.00024797689
470	Query Optimization for XML	1999	VLDB	0.00017965707
535	Efficiently Publishing Relational Data as XML Documents	2000	VLDB	0.00017003136
728	Partition Based Spatial-Merge Join	1996	SIGMOD	0.00014542772
994	Spatial Hash-Joins	1996	SIGMOD	0.00012764684
1,556	XPERANTO: A Middleware for Publishing Object-Relational Data as XML Documents	2000	VLDB	0.00010369056
2,588	Optimizing Queries on Files	1994	SIGMOD	8.3742403e-05
2,603	LORE: A Lightweight Object REpository for Semistructured Data	1996	SIGMOD	8.3535371e-05
3,066	Size Separation Spatial Join	1997	SIGMOD	7.7941163e-05
5,635	Algebras for Querying Text Regions (Extended Abstract)	1995	PODS	6.1408026e-05

Semantically Similar Papers

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