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: 6884
Venue: SIGMOD
Year: 2024
Pagerank: 4.4206222e-05
Overall Rank: 8,959 | 37.68%
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.1945683e-05
10,860	Exploring Exploratory Querying	2025	VLDB	4.1945683e-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.00092385438
211	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033981214
772	Answering Conjunctive Queries under Updates	2017	PODS	0.00016876498
1,056	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.0001441128
1,344	Counting and Sampling Triangles from a Graph Stream	2013	VLDB	0.00012473724
1,369	Random Sampling over Joins Revisited	2018	SIGMOD	0.00012339777
3,387	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration	2020	PODS	7.1573735e-05
3,668	The LDBC Social Network Benchmark: Business Intelligence Workload	2023	VLDB	6.8591612e-05
3,781	Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries	2020	PODS	6.7723513e-05
4,953	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8085795e-05
5,104	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	5.6946113e-05
5,150	Efficient Join Synopsis Maintenance for Data Warehouse	2020	SIGMOD	5.6626586e-05
5,967	Change Propagation Without Joins	2023	VLDB	5.250976e-05
6,695	Maintaining Acyclic Foreign-Key Joins under Updates	2020	SIGMOD	4.9582125e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
549	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00020376603
4,694	Scalable Reservoir Sampling on Many-Core CPUs	2019	SIGMOD	5.9944898e-05
10,254	Secure Multi-Party Sampling over Joins	2026	VLDB	4.1945683e-05
6,286	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	5.1280225e-05
6,493	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB	5.0424713e-05
2,254	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.1897043e-05
46	Simple Random Sampling from Relational Databases	1986	VLDB	0.00070894702
4,953	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8085795e-05
18	On Random Sampling over Joins	1999	SIGMOD	0.00092385438
1,369	Random Sampling over Joins Revisited	2018	SIGMOD	0.00012339777