DBScholar

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
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

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 50 of 69 citing papers.

Rank Citing Paper Year Venue Pagerank
229 High-Performance Complex Event Processing over Streams 2006 SIGMOD 0.00023927582
444 Stack-based Algorithms for Pattern Matching on DAGs 2005 VLDB 0.00018350865
496 Schema-Free XQuery 2004 VLDB 0.0001750537
666 Efficient Algorithms for Processing XPath Queries 2002 VLDB 0.00015166582
1,128 Graph Pattern Matching: From Intractable to Polynomial Time 2010 VLDB 0.0001206219
1,155 Projecting XML Documents 2003 VLDB 0.00011933524
1,204 A Comprehensive XQuery to SQL Translation using Dynamic Interval Encoding 2003 SIGMOD 0.00011664562
1,460 MonetDB/XQuery: A Fast XQuery Processor Powered by a Relational Engine 2006 SIGMOD 0.00010710674
1,523 Efficient Structural Joins on Indexed XML Documents 2002 VLDB 0.00010502089
1,744 System RX: One Part Relational, One Part XML 2005 SIGMOD 9.868841e-05
2,006 On the Integration of Structure Indexes and Inverted Lists 2004 SIGMOD 9.3190255e-05
2,589 Statistical Learning Techniques for Costing XML Queries 2005 VLDB 8.371643e-05
2,694 Holistic Twig Joins on Indexed XML Documents 2003 VLDB 8.2469414e-05
3,167 From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery 2003 VLDB 7.6749991e-05
3,209 An Efficient and Versatile Query Engine for TopX Search 2005 VLDB 7.6357297e-05
3,524 Lazy, Adaptive RID-List Intersection, and Its Application to Index Anding 2007 SIGMOD 7.3448437e-05
3,728 Querying Structured Text in an XML Database 2003 SIGMOD 7.1685118e-05
3,814 Mixed Mode XML Query Processing 2003 VLDB 7.1026815e-05
3,917 Tree Logical Classes for Efficient Evaluation of XQuery 2004 SIGMOD 7.0182992e-05
3,976 Rewriting XPath Queries Using Materialized Views 2005 VLDB 6.9785468e-05
4,027 FiST: Scalable XML Document Filtering by Sequencing Twig Patterns 2005 VLDB 6.9470299e-05
4,066 Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents 2006 VLDB 6.9298871e-05
4,107 Processing Queries on Tree-Structured Data Efficiently 2006 PODS 6.8973582e-05
4,113 On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques 2005 SIGMOD 6.8941988e-05
4,221 Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs 2008 SIGMOD 6.8233111e-05
4,294 From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching 2005 VLDB 6.7780241e-05
4,566 Approximate Matching of Hierarchical Data Using pq-Grams 2005 VLDB 6.6275286e-05
4,822 Colorful XML: One Hierarchy Isn't Enough 2004 SIGMOD 6.4919484e-05
5,100 Indexing Dataspaces 2007 SIGMOD 6.3646337e-05
5,298 Efficient Processing of XML Twig Queries with OR-Predicates 2004 SIGMOD 6.2770047e-05
5,336 Distributed Query Evaluation with Performance Guarantees 2007 SIGMOD 6.2612462e-05
5,346 Running Tree Automata on Probabilistic XML 2009 PODS 6.257995e-05
5,580 BLAS : An Efficient XPath Processing System 2004 SIGMOD 6.1625053e-05
5,772 Pattern tree algebras: sets or sequences? 2005 VLDB 6.0930389e-05
5,848 Efficient Mining of XML Query Patterns for Caching 2003 VLDB 6.0675818e-05
5,952 Efficient Processing of XML Path Queries Using the Disk-based F&B Index 2005 VLDB 6.031089e-05
6,688 ROX: Run-time Optimization of XQueries 2009 SIGMOD 5.8015211e-05
6,791 MILC: Inverted List Compression in Memory 2017 VLDB 5.7723936e-05
6,917 Query Efficiency in Probabilistic XML Models 2008 SIGMOD 5.7400564e-05
7,180 Nearest Keyword Search in XML Documents 2011 SIGMOD 5.6798251e-05
7,202 Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs 2007 VLDB 5.6755422e-05
7,486 Why Off-the-Shelf RDBMSs are Better at XPath Than You Might Expect 2007 SIGMOD 5.6073128e-05
7,494 Hash-based Subgraph Query Processing Method for Graph-structured XML Documents 2008 VLDB 5.6043267e-05
7,524 Efficient Indexing and Querying over Syntactically Annotated Trees 2012 VLDB 5.6029996e-05
7,559 An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data 2006 VLDB 5.5985266e-05
7,622 Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data 2012 VLDB 5.5806644e-05
7,664 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB 5.5720259e-05
7,786 AFilter: Adaptable XML Filtering with Prefix-Caching and Suffix-Clustering 2006 VLDB 5.5449897e-05
7,864 Cost-Sensitive Reordering of Navigational Primitives 2005 SIGMOD 5.5294867e-05
7,981 DeltaNI: An Efficient Labeling Scheme for Versioned Hierarchical Data 2013 SIGMOD 5.5146136e-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
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
Previous Page 1 / 1 Next

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