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
3359
Venue
SIGMOD
Year
2002
Pagerank
0.00031603463
Overall Rank
240 | 98.34%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 69 citing papers.

Rank Citing Paper Year Venue Pagerank
259 High-Performance Complex Event Processing over Streams 2006 SIGMOD 0.00030174924
425 Stack-based Algorithms for Pattern Matching on DAGs 2005 VLDB 0.00023598882
548 Schema-Free XQuery 2004 VLDB 0.00020391259
713 Efficient Algorithms for Processing XPath Queries 2002 VLDB 0.00017731096
1,149 A Comprehensive XQuery to SQL Translation using Dynamic Interval Encoding 2003 SIGMOD 0.0001365931
1,264 Projecting XML Documents 2003 VLDB 0.00012976407
1,414 Graph Pattern Matching: From Intractable to Polynomial Time 2010 VLDB 0.00012118275
1,733 Efficient Structural Joins on Indexed XML Documents 2002 VLDB 0.00010724888
1,795 MonetDB/XQuery: A Fast XQuery Processor Powered by a Relational Engine 2006 SIGMOD 0.00010526672
2,069 System RX: One Part Relational, One Part XML 2005 SIGMOD 9.6329563e-05
2,161 On the Integration of Structure Indexes and Inverted Lists 2004 SIGMOD 9.4002771e-05
2,665 Statistical Learning Techniques for Costing XML Queries 2005 VLDB 8.3498101e-05
3,044 An Efficient and Versatile Query Engine for TopX Search 2005 VLDB 7.6640252e-05
3,086 Tree Logical Classes for Efficient Evaluation of XQuery 2004 SIGMOD 7.596041e-05
3,117 Processing Queries on Tree-Structured Data Efficiently 2006 PODS 7.5407318e-05
3,120 Holistic Twig Joins on Indexed XML Documents 2003 VLDB 7.5295938e-05
3,610 From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery 2003 VLDB 6.9196208e-05
3,667 Querying Structured Text in an XML Database 2003 SIGMOD 6.8602249e-05
3,716 Colorful XML: One Hierarchy Isn't Enough 2004 SIGMOD 6.8214504e-05
3,717 Lazy, Adaptive RID-List Intersection, and Its Application to Index Anding 2007 SIGMOD 6.8210203e-05
4,041 FiST: Scalable XML Document Filtering by Sequencing Twig Patterns 2005 VLDB 6.5028576e-05
4,143 Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs 2008 SIGMOD 6.4129418e-05
4,207 Mixed Mode XML Query Processing 2003 VLDB 6.359465e-05
4,354 From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching 2005 VLDB 6.262393e-05
4,364 Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents 2006 VLDB 6.2546168e-05
4,406 Approximate Matching of Hierarchical Data Using pq-Grams 2005 VLDB 6.2141638e-05
4,568 Rewriting XPath Queries Using Materialized Views 2005 VLDB 6.0784118e-05
4,587 On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques 2005 SIGMOD 6.0658154e-05
5,206 Pattern tree algebras: sets or sequences? 2005 VLDB 5.6301206e-05
5,296 Running Tree Automata on Probabilistic XML 2009 PODS 5.5802694e-05
5,317 Distributed Query Evaluation with Performance Guarantees 2007 SIGMOD 5.5719038e-05
5,385 Indexing Dataspaces 2007 SIGMOD 5.5381684e-05
5,574 Efficient Processing of XML Twig Queries with OR-Predicates 2004 SIGMOD 5.4268403e-05
5,820 Efficient Processing of XML Path Queries Using the Disk-based F&B Index 2005 VLDB 5.3135144e-05
5,889 BLAS : An Efficient XPath Processing System 2004 SIGMOD 5.2873528e-05
6,224 Efficient Mining of XML Query Patterns for Caching 2003 VLDB 5.1495715e-05
6,681 Query Efficiency in Probabilistic XML Models 2008 SIGMOD 4.9643102e-05
6,732 An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data 2006 VLDB 4.9477058e-05
6,874 ROX: Run-time Optimization of XQueries 2009 SIGMOD 4.8978984e-05
6,919 Efficient Indexing and Querying over Syntactically Annotated Trees 2012 VLDB 4.8925595e-05
7,240 Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs 2007 VLDB 4.792172e-05
7,315 Nearest Keyword Search in XML Documents 2011 SIGMOD 4.7645064e-05
7,367 Hash-based Subgraph Query Processing Method for Graph-structured XML Documents 2008 VLDB 4.7514687e-05
7,416 MILC: Inverted List Compression in Memory 2017 VLDB 4.7355258e-05
7,584 Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data 2012 VLDB 4.7041255e-05
7,639 Why Off-the-Shelf RDBMSs are Better at XPath Than You Might Expect 2007 SIGMOD 4.6904624e-05
7,738 AFilter: Adaptable XML Filtering with Prefix-Caching and Suffix-Clustering 2006 VLDB 4.6636747e-05
7,762 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB 4.6583829e-05
7,815 DeltaNI: An Efficient Labeling Scheme for Versioned Hierarchical Data 2013 SIGMOD 4.6438721e-05
7,848 Cost-Sensitive Reordering of Navigational Primitives 2005 SIGMOD 4.6362551e-05
Previous Page 1 / 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
152 An Evaluation of Non-Equijoin Algorithms 1991 VLDB 0.00040963225
153 Relational Databases for Querying XML Documents: Limitations and Opportunities 1999 VLDB 0.00040784455
193 On Supporting Containment Queries in Relational Database Management Systems 2001 SIGMOD 0.00035610321
501 Query Optimization for XML 1999 VLDB 0.00021530411
511 Efficiently Publishing Relational Data as XML Documents 2000 VLDB 0.00021384332
925 Partition Based Spatial-Merge Join 1996 SIGMOD 0.00015264328
1,174 Spatial Hash-Joins 1996 SIGMOD 0.00013486418
1,288 XPERANTO: A Middleware for Publishing Object-Relational Data as XML Documents 2000 VLDB 0.00012815736
2,569 Optimizing Queries on Files 1994 SIGMOD 8.5218077e-05
2,676 LORE: A Lightweight Object REpository for Semistructured Data 1996 SIGMOD 8.3274001e-05
3,457 Size Separation Spatial Join 1997 SIGMOD 7.0755358e-05
5,198 Algebras for Querying Text Regions (Extended Abstract) 1995 PODS 5.6346171e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
12,156 Comments on “Stack-based Algorithms for Pattern Matching on DAGs” 2012 VLDB 4.1945683e-05
12,381 StreamTX: Extracting Tuples from Streaming XML Data 2008 VLDB 4.1945683e-05
1,733 Efficient Structural Joins on Indexed XML Documents 2002 VLDB 0.00010724888
12,496 Locking-Aware Structural Join Operators for XML Query Processing 2006 SIGMOD 4.1945683e-05
4,354 From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching 2005 VLDB 6.262393e-05
5,574 Efficient Processing of XML Twig Queries with OR-Predicates 2004 SIGMOD 5.4268403e-05
9,594 Fast Optimal Twig Joins 2010 VLDB 4.3197044e-05
4,364 Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents 2006 VLDB 6.2546168e-05
4,587 On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques 2005 SIGMOD 6.0658154e-05
3,120 Holistic Twig Joins on Indexed XML Documents 2003 VLDB 7.5295938e-05