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.00026628894
Overall Rank
178 | 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
241 High-Performance Complex Event Processing over Streams 2006 SIGMOD 0.00023419748
453 Stack-based Algorithms for Pattern Matching on DAGs 2005 VLDB 0.00017972038
505 Schema-Free XQuery 2004 VLDB 0.00017161757
679 Efficient Algorithms for Processing XPath Queries 2002 VLDB 0.00014837097
1,148 Graph Pattern Matching: From Intractable to Polynomial Time 2010 VLDB 0.00011809728
1,174 Projecting XML Documents 2003 VLDB 0.00011668225
1,234 A Comprehensive XQuery to SQL Translation using Dynamic Interval Encoding 2003 SIGMOD 0.00011405864
1,496 MonetDB/XQuery: A Fast XQuery Processor Powered by a Relational Engine 2006 SIGMOD 0.00010482718
1,554 Efficient Structural Joins on Indexed XML Documents 2002 VLDB 0.00010270419
1,784 System RX: One Part Relational, One Part XML 2005 SIGMOD 9.6511778e-05
2,046 On the Integration of Structure Indexes and Inverted Lists 2004 SIGMOD 9.1269888e-05
2,625 Statistical Learning Techniques for Costing XML Queries 2005 VLDB 8.2089383e-05
2,746 Holistic Twig Joins on Indexed XML Documents 2003 VLDB 8.0626049e-05
3,233 From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery 2003 VLDB 7.5033766e-05
3,276 An Efficient and Versatile Query Engine for TopX Search 2005 VLDB 7.4678085e-05
3,584 Lazy, Adaptive RID-List Intersection, and Its Application to Index Anding 2007 SIGMOD 7.1896153e-05
3,810 Querying Structured Text in an XML Database 2003 SIGMOD 7.0088933e-05
3,889 Mixed Mode XML Query Processing 2003 VLDB 6.9447533e-05
4,000 Tree Logical Classes for Efficient Evaluation of XQuery 2004 SIGMOD 6.8610702e-05
4,066 Rewriting XPath Queries Using Materialized Views 2005 VLDB 6.8221983e-05
4,126 FiST: Scalable XML Document Filtering by Sequencing Twig Patterns 2005 VLDB 6.7918112e-05
4,156 Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents 2006 VLDB 6.774434e-05
4,189 Processing Queries on Tree-Structured Data Efficiently 2006 PODS 6.7459542e-05
4,200 On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques 2005 SIGMOD 6.7395481e-05
4,291 Efficient Algorithms for Exact Ranked Twig-Pattern Matching over Graphs 2008 SIGMOD 6.6827339e-05
4,383 From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching 2005 VLDB 6.6261511e-05
4,663 Approximate Matching of Hierarchical Data Using pq-Grams 2005 VLDB 6.4810192e-05
4,936 Colorful XML: One Hierarchy Isn't Enough 2004 SIGMOD 6.3464763e-05
5,220 Indexing Dataspaces 2007 SIGMOD 6.2220078e-05
5,421 Efficient Processing of XML Twig Queries with OR-Predicates 2004 SIGMOD 6.1361863e-05
5,462 Distributed Query Evaluation with Performance Guarantees 2007 SIGMOD 6.1221387e-05
5,474 Running Tree Automata on Probabilistic XML 2009 PODS 6.1176063e-05
5,709 BLAS : An Efficient XPath Processing System 2004 SIGMOD 6.0242536e-05
5,893 Pattern tree algebras: sets or sequences? 2005 VLDB 5.9566606e-05
5,971 Efficient Mining of XML Query Patterns for Caching 2003 VLDB 5.9316289e-05
6,070 Efficient Processing of XML Path Queries Using the Disk-based F&B Index 2005 VLDB 5.896379e-05
6,800 ROX: Run-time Optimization of XQueries 2009 SIGMOD 5.6792071e-05
6,906 MILC: Inverted List Compression in Memory 2017 VLDB 5.6498626e-05
7,057 Query Efficiency in Probabilistic XML Models 2008 SIGMOD 5.6113229e-05
7,323 Nearest Keyword Search in XML Documents 2011 SIGMOD 5.5524474e-05
7,339 Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs 2007 VLDB 5.5490881e-05
7,624 Why Off-the-Shelf RDBMSs are Better at XPath Than You Might Expect 2007 SIGMOD 5.4821096e-05
7,635 Hash-based Subgraph Query Processing Method for Graph-structured XML Documents 2008 VLDB 5.4785904e-05
7,670 Efficient Indexing and Querying over Syntactically Annotated Trees 2012 VLDB 5.4772833e-05
7,699 An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data 2006 VLDB 5.4751052e-05
7,752 Optimal Enumeration: Efficient Top-k Tree Matching 2015 VLDB 5.4595236e-05
7,768 Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data 2012 VLDB 5.4558207e-05
7,920 AFilter: Adaptable XML Filtering with Prefix-Caching and Suffix-Clustering 2006 VLDB 5.4264214e-05
8,022 Cost-Sensitive Reordering of Navigational Primitives 2005 SIGMOD 5.4054691e-05
8,147 DeltaNI: An Efficient Labeling Scheme for Versioned Hierarchical Data 2013 SIGMOD 5.3908805e-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.00029294114
166 On Supporting Containment Queries in Relational Database Management Systems 2001 SIGMOD 0.00027254612
220 An Evaluation of Non-Equijoin Algorithms 1991 VLDB 0.00024344086
482 Query Optimization for XML 1999 VLDB 0.00017598607
544 Efficiently Publishing Relational Data as XML Documents 2000 VLDB 0.00016629924
752 Partition Based Spatial-Merge Join 1996 SIGMOD 0.00014246504
994 Spatial Hash-Joins 1996 SIGMOD 0.00012636707
1,592 XPERANTO: A Middleware for Publishing Object-Relational Data as XML Documents 2000 VLDB 0.00010137967
2,637 Optimizing Queries on Files 1994 SIGMOD 8.1877616e-05
2,654 LORE: A Lightweight Object REpository for Semistructured Data 1996 SIGMOD 8.1707415e-05
3,120 Size Separation Spatial Join 1997 SIGMOD 7.6300049e-05
5,763 Algebras for Querying Text Regions (Extended Abstract) 1995 PODS 6.0035367e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 12,643 Comments on "Stack-based Algorithms for Pattern Matching on DAGs" 2012 VLDB
2 12,864 StreamTX: Extracting Tuples from Streaming XML Data 2008 VLDB
3 1,554 Efficient Structural Joins on Indexed XML Documents 2002 VLDB
4 12,979 Locking-Aware Structural Join Operators for XML Query Processing 2006 SIGMOD
5 4,383 From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching 2005 VLDB
6 5,421 Efficient Processing of XML Twig Queries with OR-Predicates 2004 SIGMOD
7 9,901 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,200 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