Secure Multi-Party Sampling over Joins

Summary: First efficient MPC protocol for sampling over joins, enabling approximate relational analytics without revealing inputs or metadata (e.g., degrees, join sizes). Near-linear complexity; supports multi-way joins, comparisons, group-by, with large speedups over secure join-then-sample baselines. (summarized by gpt-5.4-mini on May 27 2026)

Paper ID: 14291
Venue: VLDB
Year: 2026
Pagerank: 4.1945683e-05
Overall Rank: 10,254 | 28.67%
DOI: 10.14778/3801059.3801062

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 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
217	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00033536712
943	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015145883
1,204	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00013319541
1,307	SMCQL: Secure Querying for Federated Databases	2017	VLDB	0.0001266709
1,323	Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters	2016	SIGMOD	0.00012601997
1,369	Random Sampling over Joins Revisited	2018	SIGMOD	0.00012339777
1,442	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011956109
2,580	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	8.5058814e-05
2,670	Efficient Oblivious Database Joins	2020	VLDB	8.3379158e-05
2,796	Hypertree Decompositions and Tractable Queries	1999	PODS	8.1112658e-05
3,024	Secure Yannakakis: Join-Aggregate Queries over Private Data	2021	SIGMOD	7.692511e-05
3,159	Towards Practical Oblivious Join	2022	SIGMOD	7.4630494e-05
7,017	Query Evaluation by Circuits	2022	PODS	4.8603097e-05
8,959	Reservoir Sampling over Joins	2024	SIGMOD	4.4206222e-05
9,652	Secure Sampling for Approximate Multi-party Query Processing	2023	SIGMOD	4.3109001e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,939	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00010025655
3,104	Computing Local Sensitivities of Counting Queries with Joins	2020	SIGMOD	7.5578613e-05
1,369	Random Sampling over Joins Revisited	2018	SIGMOD	0.00012339777
18	On Random Sampling over Joins	1999	SIGMOD	0.00092385438
2,670	Efficient Oblivious Database Joins	2020	VLDB	8.3379158e-05
6,899	SecretFlow-SCQL: A Secure Collaborative Query pLatform	2024	VLDB	4.8925595e-05
6,493	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB	5.0424713e-05
7,064	Residual Sensitivity for Differentially Private Multi-Way Joins	2021	SIGMOD	4.8450749e-05
9,652	Secure Sampling for Approximate Multi-party Query Processing	2023	SIGMOD	4.3109001e-05
8,959	Reservoir Sampling over Joins	2024	SIGMOD	4.4206222e-05