A Disk-Based Join With Probabilistic Guarantees*

Summary: A disk-based join that maintains an online statistical estimator with probabilistic confidence bounds for the aggregate result. Users can monitor progress, stop early when accuracy suffices, or finish with near-memory-free time, unlike prior online joins lacking guarantees or requiring large memory. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h440abc39e6eaf029
Venue: SIGMOD
Year: 2005
Pagerank: 6.7242128e-05
Overall Rank: 4,218 | 71.66%
DOI: 10.1145/1066157.1066222

Incoming Non-self Citations Over Time

Authors

1. Christopher Jermaine (University of Florida)
2. Alin Dobra (University of Florida)
3. Subramanian Arumugam (University of Florida)
4. Shantanu Joshi (University of Florida)
5. Abhijit Pol (University of Florida)

BibTeX Citation

@inproceedings{jermaine_sigmod05,
        title = {{A Disk-Based Join With Probabilistic Guarantees*}},
        author = {Jermaine, Christopher and Dobra, Alin and Arumugam, Subramanian and Joshi, Shantanu and Pol, Abhijit},
        series = {{SIGMOD} '05},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1066157.1066222},
        url = {https://dl.acm.org/doi/10.1145/1066157.1066222},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,090	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012074369
1,688	ParaTimer: A Progress Indicator for MapReduce DAGs	2010	SIGMOD	9.860716e-05
3,085	Continuous Sampling for Online Aggregation Over Multiple Queries	2010	SIGMOD	7.6607519e-05
3,417	Revisiting Reuse for Approximate Query Processing	2017	VLDB	7.3184905e-05
3,904	Distributed Online Aggregations	2009	VLDB	6.9307047e-05
5,829	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB	5.9764044e-05
9,654	Are Joins over LSM-trees Ready? Take RocksDB as an Example	2025	VLDB	5.142891e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
9	Online Aggregation	1997	SIGMOD	0.00076265429
57	On Random Sampling over Joins	1999	SIGMOD	0.00040095727
58	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040025054
135	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00029858107
181	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00026384065
478	Random Sampling from B+ trees	1989	VLDB	0.00017625093
746	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00014282427
1,231	Random Sampling from Hash Files	1990	SIGMOD	0.00011415576
1,820	A Scalable Hash Ripple Join Algorithm	2002	SIGMOD	9.5651265e-05
2,845	Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm	2002	VLDB	7.9439702e-05
5,609	On Producing Join Results Early	2003	PODS	6.0665543e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,868	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB
2	9,848	Constructing Join Histograms from Histograms with q-error Guarantees	2016	SIGMOD
3	10,414	Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees	2026	SIGMOD
4	3,994	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS
5	9,194	PR-Join: A Non-Blocking Join Achieving Higher Early Result Rate with Statistical Guarantees	2010	SIGMOD
6	7,471	Reservoir Sampling over Joins	2024	SIGMOD
7	138	Join Synopses for Approximate Query Answering	1999	SIGMOD
8	135	Ripple Joins for Online Aggregation	1999	SIGMOD
9	13,056	Online Estimation For Subset-Based SQL Queries	2005	VLDB
10	12,683	Efficient Rank Join with Aggregation Constraints	2011	VLDB