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.7271293e-05
Overall Rank: 4,217 | 71.65%
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.00012077577
1,688	ParaTimer: A Progress Indicator for MapReduce DAGs	2010	SIGMOD	9.8645784e-05
3,087	Continuous Sampling for Online Aggregation Over Multiple Queries	2010	SIGMOD	7.6624333e-05
3,419	Revisiting Reuse for Approximate Query Processing	2017	VLDB	7.3190065e-05
3,905	Distributed Online Aggregations	2009	VLDB	6.9335334e-05
5,831	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB	5.9782109e-05
9,646	Are Joins over LSM-trees Ready? Take RocksDB as an Example	2025	VLDB	5.1453267e-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.00076195956
57	On Random Sampling over Joins	1999	SIGMOD	0.00040108301
58	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040035279
135	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00029866033
181	Processing Aggregate Relational Queries with Hard Time Constraints	1989	SIGMOD	0.00026389403
477	Random Sampling from B+ trees	1989	VLDB	0.00017632787
745	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00014288286
1,229	Random Sampling from Hash Files	1990	SIGMOD	0.00011420642
1,820	A Scalable Hash Ripple Join Algorithm	2002	SIGMOD	9.5690887e-05
2,845	Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm	2002	VLDB	7.9474809e-05
5,608	On Producing Join Results Early	2003	PODS	6.0692914e-05

Semantically Similar Papers

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