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.7028998e-05
Overall Rank: 4,236 | 71.61%
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,095	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012036913
1,691	ParaTimer: A Progress Indicator for MapReduce DAGs	2010	SIGMOD	9.838545e-05
3,092	Continuous Sampling for Online Aggregation Over Multiple Queries	2010	SIGMOD	7.638249e-05
3,428	Revisiting Reuse for Approximate Query Processing	2017	VLDB	7.2957009e-05
3,912	Distributed Online Aggregations	2009	VLDB	6.9103187e-05
5,841	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB	5.9569427e-05
9,681	Are Joins over LSM-trees Ready? Take RocksDB as an Example	2025	VLDB	5.1258854e-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.00076079812
57	On Random Sampling over Joins	1999	SIGMOD	0.0003999751
58	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00039922419
135	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00029805026
183	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00026316699
480	Random Sampling from B+ trees	1989	VLDB	0.00017573936
750	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00014246313
1,237	Random Sampling from Hash Files	1990	SIGMOD	0.00011381076
1,832	A Scalable Hash Ripple Join Algorithm	2002	SIGMOD	9.5365548e-05
2,853	Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm	2002	VLDB	7.9179824e-05
5,620	On Producing Join Results Early	2003	PODS	6.0466546e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,886	Optimizing Probabilistic Query Processing on Continuous Uncertain Data	2011	VLDB
2	9,885	Constructing Join Histograms from Histograms with q-error Guarantees	2016	SIGMOD
3	10,480	Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees	2026	SIGMOD
4	4,011	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS
5	9,218	PR-Join: A Non-Blocking Join Achieving Higher Early Result Rate with Statistical Guarantees	2010	SIGMOD
6	7,490	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,097	Online Estimation For Subset-Based SQL Queries	2005	VLDB
10	12,726	Efficient Rank Join with Aggregation Constraints	2011	VLDB