Fast Optimal Twig Joins

Summary: Introduces new data structures and filtering strategies for twig joins, achieving worst-case optimality with practical speedups. Experimental results show ~3× speedups on standard benchmarks, up to an order of magnitude for unselective leaves, and never more than 20% slower elsewhere. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10326
Venue: VLDB
Year: 2010
Pagerank: 5.2288699e-05
Overall Rank: 9,730 | 33.25%
DOI: 10.14778/1920841.1920953

Incoming Non-self Citations Over Time

Authors

1. Nils Grimsmo (Norwegian Institute of Technology)
2. Truls A. Bjørklund (Norwegian Institute of Technology)
3. Magnus Lie Hetland (Norwegian Institute of Technology)

BibTeX Citation

@article{grimsmo_vldb10,
        title = {{Fast Optimal Twig Joins}},
        author = {Grimsmo, Nils and Bjørklund, Truls A. and Hetland, Magnus Lie},
        journal = {PVLDB},
        series = {{VLDB} '10},
        volume = {3},
        number = {1},
        pages = {894--905},
        doi = {10.14778/1920841.1920953},
        url = {https://doi.org/10.14778/1920841.1920953},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,180	Nearest Keyword Search in XML Documents	2011	SIGMOD	5.6798251e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
163	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027839792
175	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00027226333
718	Covering Indexes for Branching Path Queries	2002	SIGMOD	0.00014642961
2,694	Holistic Twig Joins on Indexed XML Documents	2003	VLDB	8.2469414e-05
4,066	Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents	2006	VLDB	6.9298871e-05
4,113	On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques	2005	SIGMOD	6.8941988e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,814	Mixed Mode XML Query Processing	2003	VLDB
2	4,066	Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents	2006	VLDB
3	6,014	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB
4	4,113	On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques	2005	SIGMOD
5	12,689	Locking-Aware Structural Join Operators for XML Query Processing	2006	SIGMOD
6	1,523	Efficient Structural Joins on Indexed XML Documents	2002	VLDB
7	4,294	From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching	2005	VLDB
8	175	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD
9	5,298	Efficient Processing of XML Twig Queries with OR-Predicates	2004	SIGMOD
10	2,694	Holistic Twig Joins on Indexed XML Documents	2003	VLDB