Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents

Summary: Introduces hierarchical stack encoding to compact twig results and a bottom-up Twig2Stack for GTP queries on XML. Directly enumerates from encodings with no post-processing and outperforms state-of-the-art on twig and GTP workloads. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9444
Venue: VLDB
Year: 2006
Pagerank: 6.2486086e-05
Overall Rank: 4,360 | 69.70%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,313	Nearest Keyword Search in XML Documents	2011	SIGMOD	4.7599924e-05
7,588	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB	4.6996269e-05
7,836	Scalable Structural Index Construction for JSON Analytics	2021	VLDB	4.6345023e-05
9,211	Scalable XML Query Processing using Parallel Pushdown Transducers	2013	VLDB	4.3684716e-05
9,594	Fast Optimal Twig Joins	2010	VLDB	4.3155661e-05
11,864	Index-Assisted Hierarchical Computations in Main-Memory RDBMS	2016	VLDB	4.1905499e-05
12,389	StreamTX: Extracting Tuples from Streaming XML Data	2008	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
193	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00035591171
239	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00031581944
425	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00023592024
499	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00021654356
1,261	Projecting XML Documents	2003	VLDB	0.00012985367
2,514	Query Processing for High-Volume XML Message Brokering	2003	VLDB	8.6121924e-05
2,572	Optimizing Queries on Files	1994	SIGMOD	8.5141353e-05
3,613	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB	6.9139845e-05
4,351	From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching	2005	VLDB	6.2563762e-05
4,584	On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques	2005	SIGMOD	6.0599995e-05
5,580	Efficient Processing of XML Twig Queries with OR-Predicates	2004	SIGMOD	5.4216254e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,164	Comments on “Stack-based Algorithms for Pattern Matching on DAGs”	2012	VLDB	4.1905499e-05
12,389	StreamTX: Extracting Tuples from Streaming XML Data	2008	VLDB	4.1905499e-05
9,182	Tree-Pattern Queries on a Lightweight XML Processor	2005	VLDB	4.3788525e-05
9,594	Fast Optimal Twig Joins	2010	VLDB	4.3155661e-05
3,125	Holistic Twig Joins on Indexed XML Documents	2003	VLDB	7.5228453e-05
4,351	From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching	2005	VLDB	6.2563762e-05
3,613	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB	6.9139845e-05
5,580	Efficient Processing of XML Twig Queries with OR-Predicates	2004	SIGMOD	5.4216254e-05
4,584	On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques	2005	SIGMOD	6.0599995e-05
239	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00031581944