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: he7562ac6d4ea35ef
Venue: VLDB
Year: 2026
Pagerank: 4.9605343e-05
Overall Rank: 10,795 | 27.64%
DOI: 10.14778/3801059.3801062
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

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

Authors

1. Qiyao Luo (Ant Financial)
2. Quanqing Xu (Ant Financial)
3. Chuanhui Yang (Ant Financial)

BibTeX Citation

@article{luo_vldb26,
        title = {{Secure Multi-Party Sampling over Joins}},
        author = {Luo, Qiyao and Xu, Quanqing and Yang, Chuanhui},
        journal = {PVLDB},
        series = {{VLDB} '26},
        volume = {19},
        number = {7},
        pages = {1455--1468},
        doi = {10.14778/3801059.3801062},
        url = {https://doi.org/10.14778/3801059.3801062},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
57	On Random Sampling over Joins	1999	SIGMOD	0.0003999751
135	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00029805026
138	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00029532435
318	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021178303
594	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015814493
770	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00014086699
793	Random Sampling over Joins Revisited	2018	SIGMOD	0.00013903938
841	Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters	2016	SIGMOD	0.00013503124
1,096	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012035761
1,499	SMCQL: Secure Querying for Federated Databases	2017	VLDB	0.00010445281
2,014	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	9.1775869e-05
2,086	Efficient Oblivious Database Joins	2020	VLDB	9.0498577e-05
2,376	Hypertree Decompositions and Tractable Queries	1999	PODS	8.5345413e-05
2,465	Towards Practical Oblivious Join	2022	SIGMOD	8.4071729e-05
2,593	Secure Yannakakis: Join-Aggregate Queries over Private Data	2021	SIGMOD	8.2282707e-05
6,545	Query Evaluation by Circuits	2022	PODS	5.7329641e-05
7,490	Reservoir Sampling over Joins	2024	SIGMOD	5.499011e-05
10,003	Secure Sampling for Approximate Multi-party Query Processing	2023	SIGMOD	5.0845476e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,086	Efficient Oblivious Database Joins	2020	VLDB
2	7,668	SecretFlow-SCQL: A Secure Collaborative Query pLatform	2024	VLDB
3	10,515	Differentially Oblivious Multi-way Join	2026	SIGMOD
4	10,518	DP-S4S: Accurate and Scalable Select-Join-Aggregate Query Processing with User-Level Differential Privacy	2026	SIGMOD
5	5,841	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB
6	6,823	Residual Sensitivity for Differentially Private Multi-Way Joins	2021	SIGMOD
7	10,825	Secure Join Operations in Multi-Identifier Databases: Performance and Practicality	2026	VLDB
8	10,464	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS
9	10,003	Secure Sampling for Approximate Multi-party Query Processing	2023	SIGMOD
10	7,490	Reservoir Sampling over Joins	2024	SIGMOD