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.662463e-05
Overall Rank: 2,310 | 84.48%
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,460	Fast Range Query Processing with Strong Privacy Protection for Cloud Computing	2014	VLDB	6.5878082e-05
4,772	Nearest Neighbor Search with Strong Location Privacy	2010	VLDB	6.422259e-05
4,885	Hu-Fu: Efficient and Secure Spatial Queries over Data Federation	2022	VLDB	6.3680345e-05
6,918	Adaptive Indexing over Encrypted Numeric Data	2016	SIGMOD	5.6435526e-05
7,488	OBIR-tree: An Efficient Oblivious Index for Spatial Keyword Queries on Secure Enclaves	2025	SIGMOD	5.5102404e-05
7,985	Shortest Path Computation with No Information Leakage	2012	VLDB	5.4109223e-05
9,255	Efficient Secure and Verifiable Location-Based Skyline Queries over Encrypted Data	2022	VLDB	5.2032182e-05
9,974	TransNet: Training Privacy-Preserving Neural Network over Transformed Layer	2020	VLDB	5.1014161e-05
11,037	Advances of Query Processing in Vector Databases	2026	VLDB	4.9769913e-05
11,532	Relational Algorithms for Top-k Query Evaluation	2024	SIGMOD	4.9769913e-05
11,742	TEE-based General-purpose Computational Backend for Secure Delegated Data Processing	2023	SIGMOD	4.9769913e-05
12,571	eSkyline: Processing Skyline Queries over Encrypted Data	2013	VLDB	4.9769913e-05
12,604	Authenticating Location-based Services without Compromising Location Privacy	2012	SIGMOD	4.9769913e-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
69	Privacy-Preserving Data Mining	2000	SIGMOD	0.00037940729
115	Executing SQL over Encrypted Data in the Database-Service-Provider Model	2002	SIGMOD	0.00031727517
311	Order Preserving Encryption for Numeric Data	2004	SIGMOD	0.00021317851
1,769	The New Casper: Query Processing for Location Services without Compromising Privacy	2006	VLDB	9.6832743e-05
3,149	Private Queries in Location Based Services: Anonymizers are not Necessary	2008	SIGMOD	7.5893784e-05
3,567	Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions	2007	SIGMOD	7.1981877e-05
4,651	Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach	2006	VLDB	6.4836419e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,710	Toward Efficient Homomorphic Encryption for Outsourced Databases through Parallel Caching	2023	SIGMOD
2	3,294	Privacy-preserving Anonymization of Set-valued Data	2008	VLDB
3	12,299	Fast Searchable Encryption With Tunable Locality	2017	SIGMOD
4	7,519	SPG: Structure-Private Graph Database via SqueezePIR	2023	VLDB
5	4,280	Querying Encrypted Data	2014	SIGMOD
6	6,918	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,213	Efficient Secure Query Evaluation over Encrypted XML Databases	2006	VLDB
9	3,307	FedKNN: Secure Federated k-Nearest Neighbor Search	2024	SIGMOD
10	5,124	Secure Query Processing with Data Interoperability in a Cloud Database Environment	2014	SIGMOD