Secure Yannakakis: Join-Aggregate Queries over Private Data

Summary: Secure Yannakakis: secure two-party evaluation of free-connex join-aggregate queries. Linear-time in data, polynomial in query; outperforms garbled-circuit approaches, reducing practical runtimes from years to minutes on TPC-H. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h4408874e222d87b9
Venue: SIGMOD
Year: 2021
Pagerank: 8.2555687e-05
Overall Rank: 2,584 | 82.64%
DOI: 10.1145/3448016.3452808

Incoming Non-self Citations Over Time

Authors

1. Yilei Wang (Hong Kong University of Science and Technology)
2. Ke Yi (Hong Kong University of Science and Technology)

BibTeX Citation

@inproceedings{wang_sigmod21,
        title = {{Secure Yannakakis: Join-Aggregate Queries over Private Data}},
        author = {Wang, Yilei and Yi, Ke},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3452808},
        url = {https://dl.acm.org/doi/10.1145/3448016.3452808},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 21 of 21 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,456	Towards Practical Oblivious Join	2022	SIGMOD	8.4350645e-05
3,192	HEDA: Multi-Attribute Unbounded Aggregation over Homomorphically Encrypted Database	2023	VLDB	7.5480909e-05
3,307	FedKNN: Secure Federated k-Nearest Neighbor Search	2024	SIGMOD	7.4387525e-05
4,885	Hu-Fu: Efficient and Secure Spatial Queries over Data Federation	2022	VLDB	6.3680345e-05
5,895	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	5.9534254e-05
6,432	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS	5.7857524e-05
6,533	Query Evaluation by Circuits	2022	PODS	5.7519838e-05
6,576	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	5.7428578e-05
7,341	Space-Time Tradeoffs for Conjunctive Queries with Access Patterns	2023	PODS	5.5465684e-05
7,653	Disclosure-Compliant Query Answering	2024	SIGMOD	5.4746904e-05
7,922	Avoiding Materialisation for Guarded Aggregate Queries	2025	VLDB	5.4250308e-05
8,627	Veil: A Storage and Communication Efficient Volume-Hiding Algorithm	2023	SIGMOD	5.2991626e-05
9,972	Secure Sampling for Approximate Multi-party Query Processing	2023	SIGMOD	5.1014161e-05
10,449	Differentially Oblivious Multi-way Join	2026	SIGMOD	4.9769913e-05
10,512	Sketch-based Secure Query Processing for Streaming Data	2026	SIGMOD	4.9769913e-05
10,673	NSHEDB: Noise-Sensitive Homomorphic Encrypted Database Query Engine	2026	SIGMOD	4.9769913e-05
10,734	Secure Multi-Party Sampling over Joins	2026	VLDB	4.9769913e-05
11,194	Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized	2025	SIGMOD	4.9769913e-05
11,225	SPECIAL: SynoPsis AssistEd Secure CollaboratIve AnaLytics	2025	VLDB	4.9769913e-05
11,233	Jodes: Efficient Oblivious Join in the Distributed Setting	2025	VLDB	4.9769913e-05
11,309	Alchemy: A Query Optimization Framework for Oblivious SQL	2025	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
276	Towards Practical Differential Privacy for SQL Queries	2018	VLDB	0.00022332903
420	Processing Analytical Queries over Encrypted Data	2013	VLDB	0.00018531799
538	TrustedDB: A Trusted Hardware based Database with Privacy and Data Confidentiality	2011	SIGMOD	0.00016756835
1,496	SMCQL: Secure Querying for Federated Databases	2017	VLDB	0.00010479934
1,570	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	0.0001020376
2,020	Shrinkwrap: Efficient SQL Query Processing in Differentially Private Data Federations	2019	VLDB	9.1714694e-05
2,076	Efficient Oblivious Database Joins	2020	VLDB	9.0798814e-05
2,178	Two Can Keep a Secret: A Distributed Architecture for Secure Database Services	2005	CIDR	8.9117503e-05
2,576	Secure Database-as-a-Service with Cipherbase	2013	SIGMOD	8.2709065e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,466	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS
2	2,076	Efficient Oblivious Database Joins	2020	VLDB
3	11,036	Instance-Optimal Acyclic Joins: From Theory to Systems	2026	VLDB
4	10,512	Sketch-based Secure Query Processing for Streaming Data	2026	SIGMOD
5	6,811	Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores	2025	VLDB
6	813	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD
7	6,469	Output-sensitive Conjunctive Query Evaluation	2024	PODS
8	6,576	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS
9	5,895	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD
10	10,734	Secure Multi-Party Sampling over Joins	2026	VLDB