Towards Practical Oblivious Join

Summary: Proposes a practical oblivious join over the cloud by integrating B-tree indices into ORAMs to support general binary and multiway equi-joins. Key contributions: secure index-access patterns, bounded total block accesses, and an index-nested-loop join enabling some band joins, with orders-of-magnitude speedups over baselines. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h0ac77e7f1c949f9b
Venue: SIGMOD
Year: 2022
Pagerank: 8.4071729e-05
Overall Rank: 2,465 | 83.48%
DOI: 10.1145/3514221.3517868

Incoming Non-self Citations Over Time

Authors

1. Zhao Chang (Xidian University)
2. Dong Xie (Pennsylvania State University)
3. Sheng Wang (Alibaba)
4. Feifei Li (Alibaba)

BibTeX Citation

@inproceedings{chang_sigmod22,
        title = {{Towards Practical Oblivious Join}},
        author = {Chang, Zhao and Xie, Dong and Wang, Sheng and Li, Feifei},
        series = {{SIGMOD} '22},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3514221.3517868},
        url = {https://dl.acm.org/doi/10.1145/3514221.3517868},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,319	FedKNN: Secure Federated k-Nearest Neighbor Search	2024	SIGMOD	7.4141554e-05
7,504	OBIR-tree: An Efficient Oblivious Index for Spatial Keyword Queries on Secure Enclaves	2025	SIGMOD	5.4920201e-05
7,578	Doquet: Differentially Oblivious Range and Join Queries with Private Data Structures	2023	VLDB	5.475693e-05
8,647	Veil: A Storage and Communication Efficient Volume-Hiding Algorithm	2023	SIGMOD	5.2816403e-05
9,602	OasisDB: An Oblivious and Scalable System for Relational Data	2025	VLDB	5.1376962e-05
9,693	SODA: A Set of Fast Oblivious Algorithms in Distributed Secure Data Analytics	2023	VLDB	5.1258854e-05
10,554	Loom: Weaving PCS-Preserving and Searchable Cloud Backups for Secure Messaging	2026	SIGMOD	4.9605343e-05
10,795	Secure Multi-Party Sampling over Joins	2026	VLDB	4.9605343e-05
10,823	Enabling Index-free Adjacency in Oblivious Graph Processing with Delayed Duplications	2026	VLDB	4.9605343e-05
11,281	SPECIAL: SynoPsis AssistEd Secure CollaboratIve AnaLytics	2025	VLDB	4.9605343e-05
11,289	Jodes: Efficient Oblivious Join in the Distributed Setting	2025	VLDB	4.9605343e-05
11,387	GORAM: Graph-oriented ORAM for Efficient Ego-centric Queries on Federated Graphs	2025	VLDB	4.9605343e-05
11,502	Towards Practical Oblivious Map	2025	VLDB	4.9605343e-05

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
115	Executing SQL over Encrypted Data in the Database-Service-Provider Model	2002	SIGMOD	0.00031623329
279	Towards Practical Differential Privacy for SQL Queries	2018	VLDB	0.00022277389
421	Processing Analytical Queries over Encrypted Data	2013	VLDB	0.00018470619
793	Random Sampling over Joins Revisited	2018	SIGMOD	0.00013903938
1,170	PrivateSQL: A Differentially Private SQL Query Engine	2019	VLDB	0.00011687052
1,719	The Tao of Inference in Privacy-Protected Databases	2018	VLDB	9.7830522e-05
1,880	Information Sharing Across Private Databases	2003	SIGMOD	9.427621e-05
2,032	Shrinkwrap: Efficient SQL Query Processing in Differentially Private Data Federations	2019	VLDB	9.1412376e-05
2,086	Efficient Oblivious Database Joins	2020	VLDB	9.0498577e-05
2,349	Answering Multi-Dimensional Analytical Queries under Local Differential Privacy	2019	SIGMOD	8.5881783e-05
2,583	Secure Database-as-a-Service with Cipherbase	2013	SIGMOD	8.2435615e-05
2,593	Secure Yannakakis: Join-Aggregate Queries over Private Data	2021	SIGMOD	8.2282707e-05
2,595	Privacy at Scale: Local Differential Privacy in Practice	2018	SIGMOD	8.2260539e-05
4,233	Answering Multi-Dimensional Range Queries under Local Differential Privacy	2021	VLDB	6.7041094e-05
4,296	Querying Encrypted Data	2014	SIGMOD	6.6647442e-05
5,144	Secure Query Processing with Data Interoperability in a Cloud Database Environment	2014	SIGMOD	6.2413538e-05
5,594	Oblivious RAM: A Dissection and Experimental Evaluation	2016	VLDB	6.0549457e-05
5,769	SDB: A Secure Query Processing System with Data Interoperability	2015	VLDB	5.9831062e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,757	What Is the Price for Joining Securely? Benchmarking Equi-Joins in Trusted Execution Environments	2022	VLDB
2	1,603	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
3	11,289	Jodes: Efficient Oblivious Join in the Distributed Setting	2025	VLDB
4	7,578	Doquet: Differentially Oblivious Range and Join Queries with Private Data Structures	2023	VLDB
5	4,481	Fast Range Query Processing with Strong Privacy Protection for Cloud Computing	2014	VLDB
6	11,800	Cracking-Like Join for Trusted Execution Environments	2023	VLDB
7	10,515	Differentially Oblivious Multi-way Join	2026	SIGMOD
8	5,594	Oblivious RAM: A Dissection and Experimental Evaluation	2016	VLDB
9	11,502	Towards Practical Oblivious Map	2025	VLDB
10	2,086	Efficient Oblivious Database Joins	2020	VLDB