Containment Join Size Estimation: Models and Methods

Summary: Proposes two models for containment-join size estimation in XML query optimization: interval and position models, with estimation methods. Extensive experiments show gains over prior algorithms and reveal parameter tradeoffs for efficient XML query plans. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3429
Venue: SIGMOD
Year: 2003
Pagerank: 4.6367487e-05
Overall Rank: 7,833 | 45.57%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,125	Holistic Twig Joins on Indexed XML Documents	2003	VLDB	7.5228453e-05
3,421	Approximate XML Query Answers	2004	SIGMOD	7.1107127e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
37	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00075597514
63	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063595699
99	XMark: A Benchmark for XML Data Management	2002	VLDB	0.00050043993
133	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00043220055
193	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00035591171
392	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00024546229
550	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00020346247
553	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00020272747
751	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00017155121
801	Universality of Serial Histograms	1993	VLDB	0.00016440976
1,045	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB	0.00014451072
1,065	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00014344675
1,254	Fixed-Precision Estimation of Join Selectivity	1993	PODS	0.00013018797
2,016	StatiX: Making XML Count	2002	SIGMOD	9.7892568e-05
2,322	Statistical Synopses for Graph-Structured XML Databases	2002	SIGMOD	9.0348397e-05
6,170	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	5.1708554e-05
9,524	Analysis and Application of Adaptive Sampling	2000	PODS	4.3268997e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
550	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00020346247
5,085	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	5.7040225e-05
3,056	Multiple Join Size Estimation by Virtual Domains (extended abstract)	1993	PODS	7.6459653e-05
13,816	Efficient XML Path Expression Processing Techniques	2002	VLDB	-
2,786	Approximate XML Joins	2002	SIGMOD	8.1223413e-05
1,019	An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment	1993	SIGMOD	0.00014623543
2,254	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.1871115e-05
11,708	Worst Case Optimal Joins on Relational and XML data	2018	SIGMOD	4.1905499e-05
193	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00035591171
6,293	Containment of Nested XML Queries	2004	VLDB	5.1206121e-05