Secure kNN Computation on Encrypted Databases

Summary: SCONEDB: secure computation on encrypted databases, focused on kNN. Proposes ASPE, an asymmetric scalar-product-preserving encryption enabling two kNN schemes that resist different attacker knowledge levels, with empirical overhead evaluation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hd92cf230deed6a71
Venue: SIGMOD
Year: 2009
Pagerank: 8.6665657e-05
Overall Rank: 2,307 | 84.50%
DOI: 10.1145/1559845.1559862

Incoming Non-self Citations Over Time

Authors

1. W. K. Wong (University of Hong Kong)
2. David W. Cheung (University of Hong Kong)
3. Ben Kao (University of Hong Kong)
4. Nikos Mamoulis (University of Hong Kong)

BibTeX Citation

@inproceedings{wong_sigmod09,
        title = {{Secure kNN Computation on Encrypted Databases}},
        author = {Wong, W. K. and Cheung, David W. and Kao, Ben and Mamoulis, Nikos},
        series = {{SIGMOD} '09},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1559845.1559862},
        url = {https://dl.acm.org/doi/10.1145/1559845.1559862},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,458	Fast Range Query Processing with Strong Privacy Protection for Cloud Computing	2014	VLDB	6.5909281e-05
4,769	Nearest Neighbor Search with Strong Location Privacy	2010	VLDB	6.4253006e-05
4,883	Hu-Fu: Efficient and Secure Spatial Queries over Data Federation	2022	VLDB	6.3710505e-05
6,916	Adaptive Indexing over Encrypted Numeric Data	2016	SIGMOD	5.6462255e-05
7,482	OBIR-tree: An Efficient Oblivious Index for Spatial Keyword Queries on Secure Enclaves	2025	SIGMOD	5.5128501e-05
7,980	Shortest Path Computation with No Information Leakage	2012	VLDB	5.4134849e-05
9,245	Efficient Secure and Verifiable Location-Based Skyline Queries over Encrypted Data	2022	VLDB	5.2056825e-05
9,968	TransNet: Training Privacy-Preserving Neural Network over Transformed Layer	2020	VLDB	5.1038322e-05
11,028	Advances of Query Processing in Vector Databases	2026	VLDB	4.9793485e-05
11,526	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	4.9793485e-05
11,736	TEE-based General-purpose Computational Backend for Secure Delegated Data Processing	2023	SIGMOD	4.9793485e-05
12,565	eSkyline: Processing Skyline Queries over Encrypted Data	2013	VLDB	4.9793485e-05
12,598	Authenticating Location-based Services without Compromising Location Privacy	2012	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
68	Privacy-Preserving Data Mining	2000	SIGMOD	0.00037958605
115	Executing SQL over Encrypted Data in the Database-Service-Provider Model	2002	SIGMOD	0.00031742473
311	Order Preserving Encryption for Numeric Data	2004	SIGMOD	0.00021327947
1,768	The New Casper: Query Processing for Location Services without Compromising Privacy	2006	VLDB	9.6873901e-05
3,148	Private Queries in Location Based Services: Anonymizers are not Necessary	2008	SIGMOD	7.5929728e-05
3,566	Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions	2007	SIGMOD	7.2015969e-05
4,648	Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach	2006	VLDB	6.4867043e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,704	Toward Efficient Homomorphic Encryption for Outsourced Databases through Parallel Caching	2023	SIGMOD
2	3,293	Privacy-preserving Anonymization of Set-valued Data	2008	VLDB
3	12,293	Fast Searchable Encryption With Tunable Locality	2017	SIGMOD
4	7,514	SPG: Structure-Private Graph Database via SqueezePIR	2023	VLDB
5	4,279	Querying Encrypted Data	2014	SIGMOD
6	6,916	Adaptive Indexing over Encrypted Numeric Data	2016	SIGMOD
7	115	Executing SQL over Encrypted Data in the Database-Service-Provider Model	2002	SIGMOD
8	7,211	Efficient Secure Query Evaluation over Encrypted XML Databases	2006	VLDB
9	3,306	FedKNN: Secure Federated k-Nearest Neighbor Search	2024	SIGMOD
10	5,121	Secure Query Processing with Data Interoperability in a Cloud Database Environment	2014	SIGMOD