Database Paper Browser

Back to papers

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
3360
Venue
SIGMOD
Year
2002
Pagerank
0.00031581944
Overall Rank
239 | 98.35%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 19 of 69 citing papers.

Rank Citing Paper Year Venue Pagerank
8,374 LCS-TRIM: Dynamic Programming Meets XML Indexing and Querying 2007 VLDB 4.5282277e-05
8,431 Materialized View Selection for XQuery Workloads 2012 SIGMOD 4.5084372e-05
8,551 Search Driven Analysis of Heterogeneous XML Data 2009 CIDR 4.4893996e-05
8,555 Incorporating Constraints in Probabilistic XML 2008 PODS 4.4893996e-05
8,641 Lazy XML Updates: Laziness as a Virtue of Update and Structural Join Efficiency 2005 SIGMOD 4.4743031e-05
9,182 Tree-Pattern Queries on a Lightweight XML Processor 2005 VLDB 4.3788525e-05
9,315 FIX: Feature-based Indexing Technique for XML Documents 2006 VLDB 4.352917e-05
9,535 Answering Tree Pattern Queries Using Views 2006 VLDB 4.3226836e-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,164 Comments on “Stack-based Algorithms for Pattern Matching on DAGs” 2012 VLDB 4.1905499e-05
12,196 Generating Efficient Execution Plans for Vertically Partitioned XML Databases 2011 VLDB 4.1905499e-05
12,313 Cost Based Plan Selection for XPath 2009 SIGMOD 4.1905499e-05
12,374 Grouping and Optimization of XPath Expressions in DB2 pureXML 2008 SIGMOD 4.1905499e-05
12,389 StreamTX: Extracting Tuples from Streaming XML Data 2008 VLDB 4.1905499e-05
12,398 Towards a Physical XML independent XQuery/SQL/XML Engine 2008 VLDB 4.1905499e-05
12,448 Efficient Algorithms for Evaluating XPath over Streams 2007 SIGMOD 4.1905499e-05
12,505 Locking-Aware Structural Join Operators for XML Query Processing 2006 SIGMOD 4.1905499e-05
12,614 Taming XPath Queries by Minimizing Wildcard Steps 2004 VLDB 4.1905499e-05
Previous Page 2 / 2 Next

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
151 An Evaluation of Non-Equijoin Algorithms 1991 VLDB 0.00041010211
153 Relational Databases for Querying XML Documents: Limitations and Opportunities 1999 VLDB 0.00040759404
193 On Supporting Containment Queries in Relational Database Management Systems 2001 SIGMOD 0.00035591171
504 Query Optimization for XML 1999 VLDB 0.00021513261
513 Efficiently Publishing Relational Data as XML Documents 2000 VLDB 0.00021365031
923 Partition Based Spatial-Merge Join 1996 SIGMOD 0.00015254021
1,174 Spatial Hash-Joins 1996 SIGMOD 0.00013490827
1,286 XPERANTO: A Middleware for Publishing Object-Relational Data as XML Documents 2000 VLDB 0.00012803857
2,572 Optimizing Queries on Files 1994 SIGMOD 8.5141353e-05
2,680 LORE: A Lightweight Object REpository for Semistructured Data 1996 SIGMOD 8.3203995e-05
3,462 Size Separation Spatial Join 1997 SIGMOD 7.0683581e-05
5,198 Algebras for Querying Text Regions (Extended Abstract) 1995 PODS 5.6294569e-05
Previous Page 1 / 1 Next

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
1,732 Efficient Structural Joins on Indexed XML Documents 2002 VLDB 0.00010716665
12,505 Locking-Aware Structural Join Operators for XML Query Processing 2006 SIGMOD 4.1905499e-05
4,351 From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching 2005 VLDB 6.2563762e-05
5,580 Efficient Processing of XML Twig Queries with OR-Predicates 2004 SIGMOD 5.4216254e-05
9,594 Fast Optimal Twig Joins 2010 VLDB 4.3155661e-05
4,360 Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents 2006 VLDB 6.2486086e-05
4,584 On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques 2005 SIGMOD 6.0599995e-05
3,125 Holistic Twig Joins on Indexed XML Documents 2003 VLDB 7.5228453e-05