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: 3428
Venue: SIGMOD
Year: 2003
Pagerank: 4.6411831e-05
Overall Rank: 7,827 | 45.55%
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,120	Holistic Twig Joins on Indexed XML Documents	2003	VLDB	7.5295938e-05
3,419	Approximate XML Query Answers	2004	SIGMOD	7.1173416e-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
39	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00074745564
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
98	XMark: A Benchmark for XML Data Management	2002	VLDB	0.00050023808
134	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00042452811
193	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00035610321
391	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00024564567
549	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00020376603
553	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00020272061
762	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00017036868
808	Universality of Serial Histograms	1993	VLDB	0.00016432772
1,046	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB	0.00014462307
1,064	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00014356481
1,255	Fixed-Precision Estimation of Join Selectivity	1993	PODS	0.00013024064
2,010	StatiX: Making XML Count	2002	SIGMOD	9.7970026e-05
2,316	Statistical Synopses for Graph-Structured XML Databases	2002	SIGMOD	9.0419716e-05
6,161	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	5.1753664e-05
9,523	Analysis and Application of Adaptive Sampling	2000	PODS	4.331052e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
549	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00020376603
5,104	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	5.6946113e-05
3,053	Multiple Join Size Estimation by Virtual Domains (extended abstract)	1993	PODS	7.64969e-05
13,802	Efficient XML Path Expression Processing Techniques	2002	VLDB	-
2,784	Approximate XML Joins	2002	SIGMOD	8.128931e-05
1,020	An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment	1993	SIGMOD	0.00014624893
2,254	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.1897043e-05
11,703	Worst Case Optimal Joins on Relational and XML data	2018	SIGMOD	4.1945683e-05
193	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00035610321
6,294	Containment of Nested XML Queries	2004	VLDB	5.1255418e-05