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
h98fbc0c654556cc9
Venue
SIGMOD
Year
2002
Pagerank
0.00026617591
Overall Rank
179 | 98.80%
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
241 High-Performance Complex Event Processing over Streams 2006 SIGMOD 0.00023408695
453 Stack-based Algorithms for Pattern Matching on DAGs 2005 VLDB 0.00017963727
505 Schema-Free XQuery 2004 VLDB 0.00017153776
680 Efficient Algorithms for Processing XPath Queries 2002 VLDB 0.0001483008
1,150 Graph Pattern Matching: From Intractable to Polynomial Time 2010 VLDB 0.00011804185
1,174 Projecting XML Documents 2003 VLDB 0.00011662712
1,235 A Comprehensive XQuery to SQL Translation using Dynamic Interval Encoding 2003 SIGMOD 0.00011400492
1,497 MonetDB/XQuery: A Fast XQuery Processor Powered by a Relational Engine 2006 SIGMOD 0.00010477876
1,555 Efficient Structural Joins on Indexed XML Documents 2002 VLDB 0.00010265572
1,784 System RX: One Part Relational, One Part XML 2005 SIGMOD 9.6466168e-05
2,048 On the Integration of Structure Indexes and Inverted Lists 2004 SIGMOD 9.1227281e-05
2,625 Statistical Learning Techniques for Costing XML Queries 2005 VLDB 8.206615e-05
2,746 Holistic Twig Joins on Indexed XML Documents 2003 VLDB 8.0587951e-05
3,235 From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery 2003 VLDB 7.4998307e-05
3,277 An Efficient and Versatile Query Engine for TopX Search 2005 VLDB 7.4642865e-05
3,552 Lazy, Adaptive RID-List Intersection, and Its Application to Index Anding 2007 SIGMOD 7.2070901e-05
3,813 Querying Structured Text in an XML Database 2003 SIGMOD 7.0055814e-05
3,889 Mixed Mode XML Query Processing 2003 VLDB 6.9415444e-05
4,001 Tree Logical Classes for Efficient Evaluation of XQuery 2004 SIGMOD 6.8578225e-05
4,068 Rewriting XPath Queries Using Materialized Views 2005 VLDB 6.8189688e-05
4,128 FiST: Scalable XML Document Filtering by Sequencing Twig Patterns 2005 VLDB 6.788597e-05
4,156 Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents 2006 VLDB 6.7712336e-05
4,189 Processing Queries on Tree-Structured Data Efficiently 2006 PODS 6.7427859e-05
4,201 On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques 2005 SIGMOD 6.7363634e-05
4,291 Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs 2008 SIGMOD 6.6795809e-05
4,386 From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching 2005 VLDB 6.6230198e-05
4,665 Approximate Matching of Hierarchical Data Using pq-Grams 2005 VLDB 6.4779518e-05
4,939 Colorful XML: One Hierarchy Isn't Enough 2004 SIGMOD 6.343473e-05
5,225 Indexing Dataspaces 2007 SIGMOD 6.2190653e-05
5,425 Efficient Processing of XML Twig Queries with OR-Predicates 2004 SIGMOD 6.1332823e-05
5,466 Distributed Query Evaluation with Performance Guarantees 2007 SIGMOD 6.1192481e-05
5,478 Running Tree Automata on Probabilistic XML 2009 PODS 6.1147103e-05
5,710 BLAS : An Efficient XPath Processing System 2004 SIGMOD 6.0214073e-05
5,893 Pattern tree algebras: sets or sequences? 2005 VLDB 5.9538443e-05
5,971 Efficient Mining of XML Query Patterns for Caching 2003 VLDB 5.928821e-05
6,073 Efficient Processing of XML Path Queries Using the Disk-based F&B Index 2005 VLDB 5.8935926e-05
6,802 ROX: Run-time Optimization of XQueries 2009 SIGMOD 5.6773357e-05
6,908 MILC: Inverted List Compression in Memory 2017 VLDB 5.6471881e-05
7,060 Query Efficiency in Probabilistic XML Models 2008 SIGMOD 5.6086666e-05
7,326 Nearest Keyword Search in XML Documents 2011 SIGMOD 5.5500332e-05
7,342 Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs 2007 VLDB 5.5464639e-05
7,630 Why Off-the-Shelf RDBMSs are Better at XPath Than You Might Expect 2007 SIGMOD 5.4795145e-05
7,641 Hash-based Subgraph Query Processing Method for Graph-structured XML Documents 2008 VLDB 5.475997e-05
7,676 Efficient Indexing and Querying over Syntactically Annotated Trees 2012 VLDB 5.4746904e-05
7,705 An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data 2006 VLDB 5.472514e-05
7,756 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB 5.4570169e-05
7,777 Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data 2012 VLDB 5.4532403e-05
7,924 AFilter: Adaptable XML Filtering with Prefix-Caching and Suffix-Clustering 2006 VLDB 5.4238547e-05
8,027 Cost-Sensitive Reordering of Navigational Primitives 2005 SIGMOD 5.4029105e-05
8,153 DeltaNI: An Efficient Labeling Scheme for Versioned Hierarchical Data 2013 SIGMOD 5.3883285e-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
141 Relational Databases for Querying XML Documents: Limitations and Opportunities 1999 VLDB 0.0002928095
166 On Supporting Containment Queries in Relational Database Management Systems 2001 SIGMOD 0.00027241844
220 An Evaluation of Non-Equijoin Algorithms 1991 VLDB 0.00024333068
482 Query Optimization for XML 1999 VLDB 0.00017590408
544 Efficiently Publishing Relational Data as XML Documents 2000 VLDB 0.00016622134
752 Partition Based Spatial-Merge Join 1996 SIGMOD 0.00014239937
994 Spatial Hash-Joins 1996 SIGMOD 0.00012630797
1,592 XPERANTO: A Middleware for Publishing Object-Relational Data as XML Documents 2000 VLDB 0.00010133221
2,637 Optimizing Queries on Files 1994 SIGMOD 8.1840201e-05
2,655 LORE: A Lightweight Object REpository for Semistructured Data 1996 SIGMOD 8.166934e-05
3,122 Size Separation Spatial Join 1997 SIGMOD 7.6263979e-05
5,764 Algebras for Querying Text Regions (Extended Abstract) 1995 PODS 6.0007448e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 12,649 Comments on "Stack-based Algorithms for Pattern Matching on DAGs" 2012 VLDB
2 12,870 StreamTX: Extracting Tuples from Streaming XML Data 2008 VLDB
3 1,555 Efficient Structural Joins on Indexed XML Documents 2002 VLDB
4 12,985 Locking-Aware Structural Join Operators for XML Query Processing 2006 SIGMOD
5 4,386 From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching 2005 VLDB
6 5,425 Efficient Processing of XML Twig Queries with OR-Predicates 2004 SIGMOD
7 9,908 Fast Optimal Twig Joins 2010 VLDB
8 4,156 Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents 2006 VLDB
9 4,201 On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques 2005 SIGMOD
10 2,746 Holistic Twig Joins on Indexed XML Documents 2003 VLDB