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.00026534482
Overall Rank
180 | 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.00023332645
456 Stack-based Algorithms for Pattern Matching on DAGs 2005 VLDB 0.00017946233
509 Schema-Free XQuery 2004 VLDB 0.00017102298
683 Efficient Algorithms for Processing XPath Queries 2002 VLDB 0.00014781223
1,148 Graph Pattern Matching: From Intractable to Polynomial Time 2010 VLDB 0.00011777466
1,176 Projecting XML Documents 2003 VLDB 0.00011624347
1,243 A Comprehensive XQuery to SQL Translation using Dynamic Interval Encoding 2003 SIGMOD 0.00011363056
1,497 MonetDB/XQuery: A Fast XQuery Processor Powered by a Relational Engine 2006 SIGMOD 0.00010447125
1,555 Efficient Structural Joins on Indexed XML Documents 2002 VLDB 0.0001023212
1,793 System RX: One Part Relational, One Part XML 2005 SIGMOD 9.6149082e-05
2,058 On the Integration of Structure Indexes and Inverted Lists 2004 SIGMOD 9.0944201e-05
2,614 Statistical Learning Techniques for Costing XML Queries 2005 VLDB 8.2023561e-05
2,756 Holistic Twig Joins on Indexed XML Documents 2003 VLDB 8.0322898e-05
3,252 From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery 2003 VLDB 7.475123e-05
3,288 An Efficient and Versatile Query Engine for TopX Search 2005 VLDB 7.4398818e-05
3,558 Lazy, Adaptive RID-List Intersection, and Its Application to Index Anding 2007 SIGMOD 7.1850547e-05
3,819 Querying Structured Text in an XML Database 2003 SIGMOD 6.9825548e-05
3,900 Mixed Mode XML Query Processing 2003 VLDB 6.9197487e-05
4,019 Tree Logical Classes for Efficient Evaluation of XQuery 2004 SIGMOD 6.8351685e-05
4,090 Rewriting XPath Queries Using Materialized Views 2005 VLDB 6.7964465e-05
4,145 FiST: Scalable XML Document Filtering by Sequencing Twig Patterns 2005 VLDB 6.7662074e-05
4,176 Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents 2006 VLDB 6.7488554e-05
4,208 Processing Queries on Tree-Structured Data Efficiently 2006 PODS 6.7214366e-05
4,219 On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques 2005 SIGMOD 6.7141046e-05
4,307 Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs 2008 SIGMOD 6.6581902e-05
4,410 From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching 2005 VLDB 6.6011343e-05
4,679 Approximate Matching of Hierarchical Data Using pq-Grams 2005 VLDB 6.4567077e-05
4,965 Colorful XML: One Hierarchy Isn't Enough 2004 SIGMOD 6.3225096e-05
5,247 Indexing Dataspaces 2007 SIGMOD 6.1985096e-05
5,443 Efficient Processing of XML Twig Queries with OR-Predicates 2004 SIGMOD 6.1130037e-05
5,480 Distributed Query Evaluation with Performance Guarantees 2007 SIGMOD 6.0991082e-05
5,495 Running Tree Automata on Probabilistic XML 2009 PODS 6.0944915e-05
5,720 BLAS : An Efficient XPath Processing System 2004 SIGMOD 6.0015097e-05
5,909 Pattern tree algebras: sets or sequences? 2005 VLDB 5.9342596e-05
5,985 Efficient Mining of XML Query Patterns for Caching 2003 VLDB 5.9092174e-05
6,087 Efficient Processing of XML Path Queries Using the Disk-based F&B Index 2005 VLDB 5.8741996e-05
6,816 ROX: Run-time Optimization of XQueries 2009 SIGMOD 5.6593309e-05
6,920 MILC: Inverted List Compression in Memory 2017 VLDB 5.631163e-05
7,080 Query Efficiency in Probabilistic XML Models 2008 SIGMOD 5.5901209e-05
7,344 Nearest Keyword Search in XML Documents 2011 SIGMOD 5.5321368e-05
7,362 Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs 2007 VLDB 5.5281595e-05
7,645 Why Off-the-Shelf RDBMSs are Better at XPath Than You Might Expect 2007 SIGMOD 5.4613959e-05
7,655 Hash-based Subgraph Query Processing Method for Graph-structured XML Documents 2008 VLDB 5.4578901e-05
7,689 Efficient Indexing and Querying over Syntactically Annotated Trees 2012 VLDB 5.4565877e-05
7,717 An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data 2006 VLDB 5.4545945e-05
7,769 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB 5.4391973e-05
7,793 Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data 2012 VLDB 5.4352151e-05
7,937 AFilter: Adaptable XML Filtering with Prefix-Caching and Suffix-Clustering 2006 VLDB 5.4060062e-05
8,045 Cost-Sensitive Reordering of Navigational Primitives 2005 SIGMOD 5.3850485e-05
8,170 DeltaNI: An Efficient Labeling Scheme for Versioned Hierarchical Data 2013 SIGMOD 5.3705113e-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.00029191386
167 On Supporting Containment Queries in Relational Database Management Systems 2001 SIGMOD 0.00027156235
220 An Evaluation of Non-Equijoin Algorithms 1991 VLDB 0.00024275691
483 Query Optimization for XML 1999 VLDB 0.00017537362
546 Efficiently Publishing Relational Data as XML Documents 2000 VLDB 0.00016567886
760 Partition Based Spatial-Merge Join 1996 SIGMOD 0.0001419395
999 Spatial Hash-Joins 1996 SIGMOD 0.00012590189
1,596 XPERANTO: A Middleware for Publishing Object-Relational Data as XML Documents 2000 VLDB 0.00010099978
2,646 Optimizing Queries on Files 1994 SIGMOD 8.157239e-05
2,662 LORE: A Lightweight Object REpository for Semistructured Data 1996 SIGMOD 8.1406777e-05
3,131 Size Separation Spatial Join 1997 SIGMOD 7.6016052e-05
5,777 Algebras for Querying Text Regions (Extended Abstract) 1995 PODS 5.9810913e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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