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: 6885
Venue: SIGMOD
Year: 2024
Pagerank: 4.4163852e-05
Overall Rank: 8,964 | 37.71%
DOI: 10.1145/3654921

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,254	Secure Multi-Party Sampling over Joins	2026	VLDB	4.1905499e-05
10,864	Exploring Exploratory Querying	2025	VLDB	4.1905499e-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
18	On Random Sampling over Joins	1999	SIGMOD	0.00092569117
212	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033997204
770	Answering Conjunctive Queries under Updates	2017	PODS	0.0001686092
1,054	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00014397587
1,348	Counting and Sampling Triangles from a Graph Stream	2013	VLDB	0.00012461666
1,372	Random Sampling over Joins Revisited	2018	SIGMOD	0.0001233325
3,386	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration	2020	PODS	7.151562e-05
3,670	The LDBC Social Network Benchmark: Business Intelligence Workload	2023	VLDB	6.8557811e-05
3,785	Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries	2020	PODS	6.7658346e-05
4,926	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8184457e-05
5,085	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	5.7040225e-05
5,128	Efficient Join Synopsis Maintenance for Data Warehouse	2020	SIGMOD	5.6728511e-05
5,973	Change Propagation Without Joins	2023	VLDB	5.2459364e-05
6,699	Maintaining Acyclic Foreign-Key Joins under Updates	2020	SIGMOD	4.9534535e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
550	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00020346247
4,689	Scalable Reservoir Sampling on Many-Core CPUs	2019	SIGMOD	5.9899401e-05
10,254	Secure Multi-Party Sampling over Joins	2026	VLDB	4.1905499e-05
6,285	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	5.1231886e-05
6,481	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB	5.039683e-05
2,254	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.1871115e-05
46	Simple Random Sampling from Relational Databases	1986	VLDB	0.00071588702
4,926	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8184457e-05
18	On Random Sampling over Joins	1999	SIGMOD	0.00092569117
1,372	Random Sampling over Joins Revisited	2018	SIGMOD	0.0001233325