Efficient Structural Joins on Indexed XML Documents

Summary: Maps XML structure to B+-trees and R-trees via tag-based node numbering, enabling efficient structural joins for parent–child and ancestor–descendant queries. Introduces a prune-friendly B+-tree join with a lightweight sibling-pointer enhancement; experiments show robust gains and superiority over R-tree approaches. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9041
Venue: VLDB
Year: 2002
Pagerank: 0.00010502089
Overall Rank: 1,523 | 89.56%
DOI: 10.1016/B978-155860869-6/50031-7

Incoming Non-self Citations Over Time

Authors

1. Shu-Yao Chien (University of California Los Angeles)
2. Zografoula Vagena (University of California Riverside)
3. Donghui Zhang (University of California Riverside)
4. Vassilis J. Tsotras (University of California Riverside)
5. Carlo Zaniolo (University of California Los Angeles)

BibTeX Citation

@article{chien_vldb02,
        title = {{Efficient Structural Joins on Indexed XML Documents}},
        author = {Chien, Shu-Yao and Vagena, Zografoula and Zhang, Donghui and Tsotras, Vassilis J. and Zaniolo, Carlo},
        journal = {PVLDB},
        series = {{VLDB} '02},
        doi = {10.1016/B978-155860869-6/50031-7},
        url = {https://doi.org/10.1016/B978-155860869-6/50031-7},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
496	Schema-Free XQuery	2004	VLDB	0.0001750537
1,155	Projecting XML Documents	2003	VLDB	0.00011933524
2,006	On the Integration of Structure Indexes and Inverted Lists	2004	SIGMOD	9.3190255e-05
2,694	Holistic Twig Joins on Indexed XML Documents	2003	VLDB	8.2469414e-05
2,720	XQuery on SQL Hosts	2004	VLDB	8.2086071e-05
3,727	Staircase Join: Teach a Relational DBMS to Watch its (Axis) Steps	2003	VLDB	7.1689738e-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
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,580	BLAS : An Efficient XPath Processing System	2004	SIGMOD	6.1625053e-05
7,202	Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs	2007	VLDB	5.6755422e-05
7,494	Hash-based Subgraph Query Processing Method for Graph-structured XML Documents	2008	VLDB	5.6043267e-05
8,422	LCS-TRIM: Dynamic Programming Meets XML Indexing and Querying	2007	VLDB	5.4278338e-05
8,870	Lazy XML Updates: Laziness as a Virtue of Update and Structural Join Efficiency	2005	SIGMOD	5.3543292e-05
9,338	Tree-Pattern Queries on a Lightweight XML Processor	2005	VLDB	5.2874872e-05
12,499	Cost Based Plan Selection for XPath	2009	SIGMOD	5.093636e-05
12,635	XPath on Steroids: Exploiting Relational Engines for XPath Performance	2007	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029548428
175	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD	0.00027226333

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,688	Incremental Maintenance of XML Structural Indexes	2004	SIGMOD
2	5,298	Efficient Processing of XML Twig Queries with OR-Predicates	2004	SIGMOD
3	12,689	Locking-Aware Structural Join Operators for XML Query Processing	2006	SIGMOD
4	3,814	Mixed Mode XML Query Processing	2003	VLDB
5	175	Holistic Twig Joins: Optimal XML Pattern Matching	2002	SIGMOD
6	341	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB
7	6,014	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB
8	12,555	Relational-Style XML Query	2008	SIGMOD
9	9,730	Fast Optimal Twig Joins	2010	VLDB
10	2,694	Holistic Twig Joins on Indexed XML Documents	2003	VLDB