Reservoir Sampling over Joins

Summary: Streaming uniform samples of join outputs, maintained without materializing the join. Novel generalized reservoir sampling with predicates plus a dynamic index, yielding near-linear maintenance despite polynomial join blowup; strong graph/relational empirical gains. (summarized by gpt-5.4-mini on May 24 2026)

Paper ID: 6946
Venue: SIGMOD
Year: 2024
Pagerank: 5.64193e-05
Overall Rank: 7,335 | 49.68%
DOI: 10.1145/3654921

Incoming Non-self Citations Over Time

Authors

1. Binyang Dai (Hong Kong University of Science and Technology)
2. Xiao Hu (University of Waterloo)
3. Ke Yi (Hong Kong University of Science and Technology)

BibTeX Citation

@inproceedings{dai_sigmod24,
        title = {{Reservoir Sampling over Joins}},
        author = {Dai, Binyang and Hu, Xiao and Yi, Ke},
        series = {{SIGMOD} '24},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3654921},
        url = {https://dl.acm.org/doi/10.1145/3654921},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,512	Poisson Sampling over Acyclic Joins	2026	SIGMOD	5.2571354e-05
9,719	Subset Sampling over Joins	2026	PODS	5.2319816e-05
10,244	FIRAS: A Framework for Interval Range Search and Sampling	2026	SIGMOD	5.093636e-05
10,289	Sketch-based Secure Query Processing for Streaming Data	2026	SIGMOD	5.093636e-05
10,542	Secure Multi-Party Sampling over Joins	2026	VLDB	5.093636e-05
11,084	Exploring Exploratory Querying	2025	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
136	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00030123303
636	Answering Conjunctive Queries under Updates	2017	PODS	0.0001551856
802	Random Sampling over Joins Revisited	2018	SIGMOD	0.00013907725
816	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013827772
1,103	Counting and Sampling Triangles from a Graph Stream	2013	VLDB	0.000121583
2,777	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration	2020	PODS	8.1352657e-05
3,018	The LDBC Social Network Benchmark: Business Intelligence Workload	2023	VLDB	7.8473755e-05
3,136	Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries	2020	PODS	7.7210541e-05
3,453	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	7.4004131e-05
3,941	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	7.0074268e-05
4,630	Efficient Join Synopsis Maintenance for Data Warehouse	2020	SIGMOD	6.5955933e-05
4,985	Change Propagation Without Joins	2023	VLDB	6.412102e-05
6,332	Maintaining Acyclic Foreign-Key Joins under Updates	2020	SIGMOD	5.9107433e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,512	Poisson Sampling over Acyclic Joins	2026	SIGMOD
2	5,733	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB
3	10,169	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS
4	5,743	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB
5	1,664	Two-Level Sampling for Join Size Estimation	2017	SIGMOD
6	173	Simple Random Sampling from Relational Databases	1986	VLDB
7	3,453	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS
8	54	On Random Sampling over Joins	1999	SIGMOD
9	802	Random Sampling over Joins Revisited	2018	SIGMOD
10	9,719	Subset Sampling over Joins	2026	PODS