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

Summary: Twig2Stack introduces hierarchical stack encoding and bottom-up holistic evaluation for XML twig patterns, reducing useless path matches. It directly supports generalized-tree-pattern queries while avoiding post path joins, sorting, duplicate elimination, and grouping. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h6c9c87b055698097
Venue: VLDB
Year: 2006
Pagerank: 6.774434e-05
Overall Rank: 4,156 | 72.06%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Songting Chen (NEC Corporation)
2. Hua-Gang Li (University of California Santa Barbara)
3. Junichi Tatemura (NEC Corporation)
4. Wang-Pin Hsiung (NEC Corporation)
5. Divyakant Agrawal (NEC Corporation)
6. K. Selçuk Candan (NEC Corporation)

BibTeX Citation

@article{chen_vldb06,
        title = {{Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents}},
        author = {Chen, Songting and Li, Hua-Gang and Tatemura, Junichi and Hsiung, Wang-Pin and Agrawal, Divyakant and Candan, K. Selçuk},
        journal = {PVLDB},
        series = {{VLDB} '06},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,323	Nearest Keyword Search in XML Documents	2011	SIGMOD	5.5524474e-05
7,768	Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data	2012	VLDB	5.4558207e-05
7,927	Scalable Structural Index Construction for JSON Analytics	2021	VLDB	5.425609e-05
9,547	Scalable XML Query Processing using Parallel Pushdown Transducers	2013	VLDB	5.1602021e-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,864	StreamTX: Extracting Tuples from Streaming XML Data	2008	VLDB	4.9793485e-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
166	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027254612
178	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00026628894
409	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00018868173
453	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00017972038
1,174	Projecting XML Documents	2003	VLDB	0.00011668225
2,381	Query Processing for High-Volume XML Message Brokering	2003	VLDB	8.5462254e-05
2,637	Optimizing Queries on Files	1994	SIGMOD	8.1877616e-05
3,233	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB	7.5033766e-05
4,200	On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques	2005	SIGMOD	6.7395481e-05
4,383	From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching	2005	VLDB	6.6261511e-05
5,421	Efficient Processing of XML Twig Queries with OR-Predicates	2004	SIGMOD	6.1361863e-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	9,514	Tree-Pattern Queries on a Lightweight XML Processor	2005	VLDB
4	9,901	Fast Optimal Twig Joins	2010	VLDB
5	2,746	Holistic Twig Joins on Indexed XML Documents	2003	VLDB
6	4,383	From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching	2005	VLDB
7	3,233	From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery	2003	VLDB
8	5,421	Efficient Processing of XML Twig Queries with OR-Predicates	2004	SIGMOD
9	4,200	On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques	2005	SIGMOD
10	178	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD