Authenticated Join Processing in Outsourced Databases

Summary: Three ADS-dependent authenticated join algorithms for outsourcing: AISM (single-ADS), AIM (ADS on both sides), ASM (no-ADS). Compared to benchmarks, they beat baselines and shift to service; extend to multi-way joins with selections and projections. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4167
Venue: SIGMOD
Year: 2009
Pagerank: 9.7171985e-05
Overall Rank: 1,804 | 87.63%
DOI: 10.1145/1559845.1559849

Incoming Non-self Citations Over Time

Authors

1. Yin Yang (Hong Kong University of Science and Technology)
2. Dimitris Papadias (Hong Kong University of Science and Technology)
3. Stavros Papadopoulos (Hong Kong University of Science and Technology)
4. Panos Kalnis (King Abdullah University of Science and Technology)

BibTeX Citation

@inproceedings{yang_sigmod09,
        title = {{Authenticated Join Processing in Outsourced Databases}},
        author = {Yang, Yin and Papadias, Dimitris and Papadopoulos, Stavros and Kalnis, Panos},
        series = {{SIGMOD} '09},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1559845.1559849},
        url = {https://dl.acm.org/doi/10.1145/1559845.1559849},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
876	Orthogonal Security With Cipherbase	2013	CIDR	0.00013467554
1,724	CorrectDB: SQL Engine with Practical Query Authentication	2013	VLDB	9.9199577e-05
3,122	FalconDB: Blockchain-based Collaborative Database	2020	SIGMOD	7.7356769e-05
4,304	VeriDB: An SGX-based Verifiable Database	2021	SIGMOD	6.7709608e-05
5,315	When Query Authentication Meets Fine-Grained Access Control: A Zero-Knowledge Approach	2018	SIGMOD	6.2688062e-05
5,426	Practical Authenticated Pattern Matching with Optimal Proof Size	2015	VLDB	6.2231556e-05
6,939	Multi-Tenant Cloud Data Services: State-of-the-Art, Challenges and Opportunities	2022	SIGMOD	5.7338637e-05
9,608	Lightweight Authentication of Linear Algebraic Queries on Data Streams	2013	SIGMOD	5.2470962e-05
9,770	PoneglyphDB: Efficient Non-interactive Zero-Knowledge Proofs for Arbitrary SQL-Query Verification	2025	SIGMOD	5.2209769e-05
10,347	BPI: A Novel Efficient and Reliable Search Structure for Hybrid Storage Blockchain	2026	SIGMOD	5.093636e-05
12,354	Efficient Verification of Web-Content Searching Through Authenticated Web Crawlers	2012	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
310	Order Preserving Encryption for Numeric Data	2004	SIGMOD	0.00021766789
437	Dynamic Authenticated Index Structures for Outsourced Databases	2006	SIGMOD	0.00018489863
562	Querying the Internet with PIER	2003	VLDB	0.00016509814
617	Verifying Completeness of Relational Query Results in Data Publishing	2005	SIGMOD	0.00015711988
785	Middle-Tier Database Caching for e-Business	2002	SIGMOD	0.00014068999
829	Proactive Re-Optimization	2005	SIGMOD	0.00013769838
2,350	Query Execution Assurance for Outsourced Databases	2005	VLDB	8.7114376e-05
3,524	Lazy, Adaptive RID-List Intersection, and Its Application to Index Anding	2007	SIGMOD	7.3448437e-05
4,381	Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams	2007	VLDB	6.7333392e-05
4,455	CADS: Continuous Authentication on Data Streams	2007	VLDB	6.6923409e-05
4,501	GhostDB: Querying Visible and Hidden Data Without Leaks	2007	SIGMOD	6.6601566e-05
4,760	Integrity Auditing of Outsourced Data	2007	VLDB	6.5206581e-05
5,153	Structural Signatures for Tree Data Structures	2008	VLDB	6.3428063e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,947	Querying with Access Patterns and Integrity Constraints	2015	VLDB
2	2,244	Join Queries with External Text Sources: Execution and Optimization Techniques	1995	SIGMOD
3	13,231	Using Semiouterjoins to Process Queries in Multidatabase Systems	1984	PODS
4	1,176	Outerjoins as Disjunctions	1994	SIGMOD
5	7,879	Authenticated Online Data Integration Services	2015	SIGMOD
6	5,315	When Query Authentication Meets Fine-Grained Access Control: A Zero-Knowledge Approach	2018	SIGMOD
7	4,760	Integrity Auditing of Outsourced Data	2007	VLDB
8	4,887	Scalable Verification for Outsourced Dynamic Databases	2009	VLDB
9	2,350	Query Execution Assurance for Outsourced Databases	2005	VLDB
10	437	Dynamic Authenticated Index Structures for Outsourced Databases	2006	SIGMOD