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: 3728
Venue: SIGMOD
Year: 2005
Pagerank: 6.8779166e-05
Overall Rank: 4,138 | 71.62%
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,064	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012336248
1,665	ParaTimer: A Progress Indicator for MapReduce DAGs	2010	SIGMOD	0.00010069173
3,042	Continuous Sampling for Online Aggregation Over Multiple Queries	2010	SIGMOD	7.8231049e-05
3,370	Revisiting Reuse for Approximate Query Processing	2017	VLDB	7.4700891e-05
3,844	Distributed Online Aggregations	2009	VLDB	7.0782059e-05
5,743	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB	6.1025457e-05
9,465	Are Joins over LSM-trees Ready? Take RocksDB as an Example	2025	VLDB	5.2634238e-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.00077458002
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
55	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040746149
131	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00030424509
178	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00026881845
467	Random Sampling from B+ trees	1989	VLDB	0.00018002218
730	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00014539362
1,206	Random Sampling from Hash Files	1990	SIGMOD	0.00011663837
1,785	A Scalable Hash Ripple Join Algorithm	2002	SIGMOD	9.7702627e-05
2,787	Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm	2002	VLDB	8.1205738e-05
5,467	On Producing Join Results Early	2003	PODS	6.2074577e-05

Semantically Similar Papers

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