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: 3490
Venue: SIGMOD
Year: 2003
Pagerank: 5.4766319e-05
Overall Rank: 8,155 | 44.05%
DOI: 10.1145/872757.872777

Incoming Non-self Citations Over Time

Authors

1. Wei Wang (Hong Kong University of Science and Technology)
2. Haifeng Jiang (Hong Kong University of Science and Technology)
3. Hongjun Lu (Hong Kong University of Science and Technology)
4. Jeffrey Xu Yu (Chinese University of Hong Kong)

BibTeX Citation

@inproceedings{wang_sigmod03,
        title = {{Containment Join Size Estimation: Models and Methods}},
        author = {Wang, Wei and Jiang, Haifeng and Lu, Hongjun and Yu, Jeffrey Xu},
        series = {{SIGMOD} '03},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/872757.872777},
        url = {https://dl.acm.org/doi/10.1145/872757.872777},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,694	Holistic Twig Joins on Indexed XML Documents	2003	VLDB	8.2469414e-05
3,180	Approximate XML Query Answers	2004	SIGMOD	7.6599179e-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
35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00048481081
55	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040746149
79	XMark: A Benchmark for XML Data Management	2002	VLDB	0.00036555628
163	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027839792
178	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00026881845
341	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00020704572
418	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018812821
730	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00014539362
786	Universality of Serial Histograms	1993	VLDB	0.00014053885
817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013823702
901	Estimating the Selectivity of XML Path Expressions for Internet Scale Applications	2001	VLDB	0.00013334162
992	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS	0.00012790174
1,186	Fixed-Precision Estimation of Join Selectivity	1993	PODS	0.00011764128
1,900	StatiX: Making XML Count	2002	SIGMOD	9.5168326e-05
2,326	Statistical Synopses for Graph-Structured XML Databases	2002	SIGMOD	8.748172e-05
5,932	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	6.0369275e-05
9,676	Analysis and Application of Adaptive Sampling	2000	PODS	5.2377579e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	418	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS
2	3,941	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS
3	2,984	Multiple Join Size Estimation by Virtual Domains (extended abstract)	1993	PODS
4	14,003	Efficient XML Path Expression Processing Techniques	2002	VLDB
5	2,699	Approximate XML Joins	2002	SIGMOD
6	1,172	An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment	1993	SIGMOD
7	1,664	Two-Level Sampling for Join Size Estimation	2017	SIGMOD
8	11,907	Worst Case Optimal Joins on Relational and XML data	2018	SIGMOD
9	163	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD
10	6,185	Containment of Nested XML Queries	2004	VLDB