{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T19:37:29Z","timestamp":1775158649705,"version":"3.50.1"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF of Guangdong Province","award":["2023A151503027"],"award-info":[{"award-number":["2023A151503027"]}]},{"DOI":"10.13039\/501100001809","name":"NSF of China","doi-asserted-by":"crossref","award":["62372128 & 62072132"],"award-info":[{"award-number":["62372128 & 62072132"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Hong Kong Research Grants Council","award":["12202221 & C2004-21GF"],"award-info":[{"award-number":["12202221 & C2004-21GF"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>Nearest neighbor search is a fundamental task in various domains, such as federated learning, data mining, information retrieval, and biomedicine. With the increasing need to utilize data from different organizations while respecting privacy regulations, private data federation has emerged as a promising solution. However, it is costly to directly apply existing approaches to federated k-nearest neighbor (kNN) search with difficult-to-compute distance functions, like graph or sequence similarity. To address this challenge, we propose FedKNN, a system that supports secure federated kNN search queries with a wide range of similarity measurements. Our system is equipped with a new Distribution-Aware kNN (DANN) algorithm to minimize unnecessary local computations while protecting data privacy. We further develop DANN*, a secure version of DANN that satisfies differential obliviousness. Extensive evaluations show that FedKNN outperforms state-of-the-art solutions, achieving up to 4.8\u00d7 improvement on federated graph kNN search and up to 2.7\u00d7 improvement on federated sequence kNN search. Additionally, our approach offers a trade-off between privacy and efficiency, providing strong privacy guarantees with minimal overhead.<\/jats:p>","DOI":"10.1145\/3639266","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-26","source":"Crossref","is-referenced-by-count":10,"title":["FedKNN: Secure Federated k-Nearest Neighbor Search"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3085-4878","authenticated-orcid":false,"given":"Xinyi","family":"Zhang","sequence":"first","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, Hong Kong"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0959-5536","authenticated-orcid":false,"given":"Qichen","family":"Wang","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, Hong Kong"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7256-082X","authenticated-orcid":false,"given":"Cheng","family":"Xu","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, Hong Kong"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6358-2333","authenticated-orcid":false,"given":"Yun","family":"Peng","sequence":"additional","affiliation":[{"name":"Guangzhou University &amp; Guangdong Provincial Key Laboratory of Blockchain Security, Guangzhou, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9404-5848","authenticated-orcid":false,"given":"Jianliang","family":"Xu","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, Hong Kong"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"13th National People's Congress of the People's Republic of China. 2021. Personal Information Protection Law of the People's Republic of China. http:\/\/en.npc.gov.cn.cdurl.cn\/2021--12\/29\/c_694559.htm."},{"key":"e_1_2_1_2_1","volume-title":"Oblivious query processing. Preprint arXiv","author":"Arasu Arvind","year":"2013","unstructured":"Arvind Arasu and Raghav Kaushik. 2013. Oblivious query processing. Preprint arXiv (2013)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055334"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407854"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3429252"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Dmytro Bogatov Georgios Kellaris George Kollios Kobbi Nissim and Adam O'Neill. 2021. $varepsilon$psolute: Efficiently Querying Databases While Providing Differential Privacy. In ACM CCS. 2262--2276.","DOI":"10.1145\/3460120.3484786"},{"key":"e_1_2_1_7_1","unstructured":"California State Legislature. 2018. California Consumer Privacy Act. https:\/\/oag.ca.gov\/privacy\/ccpa."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"T-H. Hubert Chan Kai-Min Chung Bruce M. Maggs and Elaine Shi. 2019. Foundations of Differentially Oblivious Algorithms. In ACM SODA. 2448--2467.","DOI":"10.1137\/1.9781611975482.150"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2022.3153523"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Zhao Chang Dong Xie Sheng Wang and Feifei Li. 2022b. Towards Practical Oblivious Join. In ACM SIGMOD. 803--817.","DOI":"10.1145\/3514221.3517868"},{"key":"e_1_2_1_11_1","volume-title":"Enhanced nearest neighbour search on the R-tree. ACM SIGMOD Record","author":"Cheung King Lum","year":"1998","unstructured":"King Lum Cheung and Ada Wai-Chee Fu. 1998. Enhanced nearest neighbour search on the R-tree. ACM SIGMOD Record (1998), 16--21."},{"key":"e_1_2_1_12_1","volume-title":"Intel SGX explained. Cryptology ePrint Archive","author":"Costan Victor","year":"2016","unstructured":"Victor Costan and Srinivas Devadas. 2016. Intel SGX explained. Cryptology ePrint Archive (2016)."},{"key":"e_1_2_1_13_1","volume-title":"Joseph E Gonzalez, and Ion Stoica.","author":"Dave Ankur","year":"2020","unstructured":"Ankur Dave, Chester Leung, Raluca Ada Popa, Joseph E Gonzalez, and Ion Stoica. 2020. Oblivious coopetitive analytics using hardware enclaves. In ACM EuroSys. 1--17."},{"key":"e_1_2_1_14_1","volume-title":"Topology of strings: Median string is NP-complete. Theoretical computer science","author":"de la Higuera Colin","year":"2000","unstructured":"Colin de la Higuera and Francisco Casacuberta. 2000. Topology of strings: Median string is NP-complete. Theoretical computer science, Vol. 230, 1--2 (2000), 39--48."},{"key":"e_1_2_1_15_1","volume-title":"Federated Nearest Neighbor Machine Translation. ICLR","author":"Du Yichao","year":"2022","unstructured":"Yichao Du, Zhirui Zhang, Bingzhe Wu, Lemao Liu, Tong Xu, and Enhong Chen. 2022. Federated Nearest Neighbor Machine Translation. ICLR (2022)."},{"key":"e_1_2_1_16_1","volume-title":"Spatialhadoop: A mapreduce framework for spatial data","author":"Eldawy Ahmed","year":"2015","unstructured":"Ahmed Eldawy and Mohamed F Mokbel. 2015. Spatialhadoop: A mapreduce framework for spatial data. In IEEE ICDE. 1352--1363."},{"key":"e_1_2_1_17_1","unstructured":"European Parliament and Council of the European Union. 2016. General Data Protection Regulation. https:\/\/eur-lex.europa.eu\/eli\/reg\/2016\/679\/oj."},{"key":"e_1_2_1_18_1","first-page":"490","article-title":"Towards achieving keyword search over dynamic encrypted cloud data with symmetric-key based verification","volume":"18","author":"Ge Xinrui","year":"2019","unstructured":"Xinrui Ge, Jia Yu, Hanlin Zhang, Chengyu Hu, Zengpeng Li, Zhan Qin, and Rong Hao. 2019. Towards achieving keyword search over dynamic encrypted cloud data with symmetric-key based verification. IEEE TDSC, Vol. 18, 1 (2019), 490--504.","journal-title":"IEEE TDSC"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Craig Gentry. 2009. Fully homomorphic encryption using ideal lattices. In ACM STOC. 169--178.","DOI":"10.1145\/1536414.1536440"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Oded Goldreich. 1987. Towards a theory of software protection and simulation by oblivious RAMs. In ACM STOC. 182--194.","DOI":"10.1145\/28395.28416"},{"key":"e_1_2_1_21_1","volume-title":"An efficient approach for graph edit similarity computation","author":"Gouda Karam","unstructured":"Karam Gouda and Mosab Hassaan. 2016. CSI_GED: An efficient approach for graph edit similarity computation. In IEEE ICDE. 265--276."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.2478\/popets-2019-0034"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2022.3173291"},{"key":"e_1_2_1_24_1","volume-title":"Scape: Scalable Collaborative Analytics System on Private Database with Malicious Security","author":"Han Feng","year":"2022","unstructured":"Feng Han, Lan Zhang, Hanwen Feng, Weiran Liu, and Xiangyang Li. 2022. Scape: Scalable Collaborative Analytics System on Private Database with Malicious Security. In IEEE ICDE. 1740--1753."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Xi He Ashwin Machanavajjhala Cheryl Flynn and Divesh Srivastava. 2017. Composing differential privacy and secure computation: A case study on scaling private record linkage. In ACM CCS. 1389--1406.","DOI":"10.1145\/3133956.3134030"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5120\/19890-1930"},{"key":"e_1_2_1_27_1","volume-title":"AMD memory encryption. White paper","author":"Kaplan David","year":"2016","unstructured":"David Kaplan, Jeremy Powell, and Tom Woller. 2016. AMD memory encryption. White paper (2016)."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Jongik Kim. 2021. Boosting graph similarity search through pre-computation. In ACM SIGMOD. 951--963.","DOI":"10.1145\/3448016.3452780"},{"key":"e_1_2_1_29_1","volume-title":"Efficient oblivious database joins. PVLDB","author":"Krastnikov Simeon","year":"2020","unstructured":"Simeon Krastnikov, Florian Kerschbaum, and Douglas Stebila. 2020. Efficient oblivious database joins. PVLDB (2020), 2132--2145."},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Conglong Li Minjia Zhang David G Andersen and Yuxiong He. 2020. Improving approximate nearest neighbor search through learned adaptive early termination. In ACM SIGMOD. 2539--2554.","DOI":"10.1145\/3318464.3380600"},{"key":"e_1_2_1_31_1","volume-title":"Flare: A Fast, Secure, and Memory-Efficient Distributed Analytics Framework. PVLDB","author":"Li Xiang","year":"2023","unstructured":"Xiang Li, Fabing Li, and Mingyu Gao. 2023. Flare: A Fast, Secure, and Memory-Efficient Distributed Analytics Framework. PVLDB (2023), 1439--1452."},{"key":"e_1_2_1_32_1","volume-title":"SECRECY: Secure collaborative analytics in untrusted clouds. In USENIX NSDI. 1031--1056.","author":"Liagouris John","year":"2023","unstructured":"John Liagouris, Vasiliki Kalavri, Muhammad Faisal, and Mayank Varia. 2023. SECRECY: Secure collaborative analytics in untrusted clouds. In USENIX NSDI. 1031--1056."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-32456-8"},{"key":"e_1_2_1_34_1","volume-title":"Tsz Nam Chan, and Jianliang Xu","author":"Peng Yun","year":"2022","unstructured":"Yun Peng, Byron Choi, Tsz Nam Chan, and Jianliang Xu. 2022. LAN: Learning-based Approximate k-Nearest Neighbor Search in Graph Databases. In IEEE ICDE. 2508--2521."},{"key":"e_1_2_1_35_1","volume-title":"Raluca Ada Popa, and Joseph M Hellerstein","author":"Poddar Rishabh","year":"2021","unstructured":"Rishabh Poddar, Sukrit Kalra, Avishay Yanai, Ryan Deng, Raluca Ada Popa, and Joseph M Hellerstein. 2021. Senate: A Maliciously-Secure MPC Platform for Collaborative Analytics. In USENIX Security. 2129--2146."},{"key":"e_1_2_1_36_1","volume-title":"Adore: Differentially Oblivious Relational Database Operators. PVLDB","author":"Qin Lianke","year":"2023","unstructured":"Lianke Qin, Rajesh Jayaram, Elaine Shi, Zhao Song, Danyang Zhuo, and Shumo Chu. 2023. Adore: Differentially Oblivious Relational Database Operators. PVLDB (2023), 842--855."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v36i7.20775"},{"key":"e_1_2_1_38_1","volume-title":"Path oblivious heap: Optimal and practical oblivious priority queue","author":"Shi Elaine","unstructured":"Elaine Shi. 2020. Path oblivious heap: Optimal and practical oblivious priority queue. In IEEE S&P. 842--858."},{"key":"e_1_2_1_39_1","volume-title":"ObliDB: Oblivious Query Processing for Secure Databases. PVLDB","author":"Matei Zaharia Saba","year":"2019","unstructured":"Saba skandarian and Matei Zaharia. 2019. ObliDB: Oblivious Query Processing for Secure Databases. PVLDB (2019), 169--183."},{"key":"e_1_2_1_40_1","volume-title":"Practical techniques for searches on encrypted data","author":"Song Dawn Xiaoding","unstructured":"Dawn Xiaoding Song, David Wagner, and Adrian Perrig. 2000. Practical techniques for searches on encrypted data. In IEEE S&P. 44--55."},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Yongxin Tong Xuchen Pan Yuxiang Zeng Yexuan Shi Chunbo Xue Zimu Zhou Xiaofei Zhang Lei Chen Yi Xu Ke Xu et al. 2022. Hu-Fu: efficient and secure spatial queries over data federation. PVLDB (2022) 1159--1172.","DOI":"10.14778\/3514061.3514064"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Nikolaj Volgushev Malte Schwarzkopf Ben Getchell Mayank Varia Andrei Lapets and Azer Bestavros. 2019. Conclave: secure multi-party computation on big data. In ACM EuroSys. 1--18.","DOI":"10.1145\/3302424.3303982"},{"key":"e_1_2_1_43_1","first-page":"3582","article-title":"OblivGM: Oblivious Attributed Subgraph Matching as a Cloud Service","volume":"17","author":"Wang Songlei","year":"2022","unstructured":"Songlei Wang, Yifeng Zheng, Xiaohua Jia, Hejiao Huang, and Cong Wang. 2022. OblivGM: Oblivious Attributed Subgraph Matching as a Cloud Service. IEEE TIFS, Vol. 17 (2022), 3582--3596.","journal-title":"IEEE TIFS"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452808"},{"key":"e_1_2_1_45_1","volume-title":"Slicer: Verifiable, Secure and Fair Search over Encrypted Numerical Data Using Blockchain","author":"Wu Haotian","year":"2022","unstructured":"Haotian Wu, Rui Song, Kai Lei, and Bin Xiao. 2022. Slicer: Verifiable, Secure and Fair Search over Encrypted Numerical Data Using Blockchain. In IEEE ICDCS. 1201--1211."},{"key":"e_1_2_1_46_1","volume-title":"Differentially Oblivious Data Analysis with Intel SGX: Design, Optimization, and Evaluation","author":"Wu Pengfei","year":"2021","unstructured":"Pengfei Wu, Qi Li, Jianting Ning, Xinyi Huang, and Wei Wu. 2021. Differentially Oblivious Data Analysis with Intel SGX: Design, Optimization, and Evaluation. IEEE TDSC (2021)."},{"key":"e_1_2_1_47_1","unstructured":"Lee Xiong Chenyan Xiong Ye Li Kwok-Fung Tang Jialin Liu Paul N. Bennett Junaid Ahmed and Arnold Overwijk. 2021. Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval. In ICLR."},{"key":"e_1_2_1_48_1","volume-title":"Controlled-channel attacks: Deterministic side channels for untrusted operating systems","author":"Xu Yuanzhong","unstructured":"Yuanzhong Xu, Weidong Cui, and Marcus Peinado. 2015. Controlled-channel attacks: Deterministic side channels for untrusted operating systems. In IEEE S&P. 640--656."},{"key":"e_1_2_1_49_1","volume-title":"minIL: A Simple and Small Index for String Similarity Search with Edit Distance","author":"Yang Zhong","unstructured":"Zhong Yang, Bolong Zheng, Xianzhi Wang, Guohui Li, and Xiaofang Zhou. 2022. minIL: A Simple and Small Index for String Similarity Search with Edit Distance. In IEEE ICDE. 565--577."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0449-y"},{"key":"e_1_2_1_51_1","volume-title":"Obliv-C: A language for extensible data-oblivious computation. Cryptology ePrint Archive","author":"Zahur Samee","year":"2015","unstructured":"Samee Zahur and David Evans. 2015. Obliv-C: A language for extensible data-oblivious computation. Cryptology ePrint Archive (2015)."},{"key":"e_1_2_1_52_1","volume-title":"Jianyong Wang, Jianhua Feng, and Lizhu Zhou.","author":"Zeng Zhiping","year":"2009","unstructured":"Zhiping Zeng, Anthony KH Tung, Jianyong Wang, Jianhua Feng, and Lizhu Zhou. 2009. Comparing stars: On approximating graph edit distance. PVLDB (2009), 25--36."},{"key":"e_1_2_1_53_1","volume-title":"Minsearch: An efficient algorithm for similarity search under edit distance. In ACM SIGKDD. 566--576.","author":"Zhang Haoyu","year":"2020","unstructured":"Haoyu Zhang and Qin Zhang. 2020. Minsearch: An efficient algorithm for similarity search under edit distance. In ACM SIGKDD. 566--576."},{"key":"e_1_2_1_54_1","doi-asserted-by":"crossref","unstructured":"Xinyi Zhang Qichen Wang Cheng Xu Yun Peng and Jianliang Xu. 2023. FedKNN: Secure Federated k-Nearest Neighbor Search (Technical Report). https:\/\/www.comp.hkbu.edu.hk\/ db\/fedknn_cr_tech_report.pdf.","DOI":"10.1145\/3639266"},{"key":"e_1_2_1_55_1","volume-title":"Joseph E Gonzalez, and Ion Stoica.","author":"Zheng Wenting","year":"2017","unstructured":"Wenting Zheng, Ankur Dave, Jethro G Beekman, Raluca Ada Popa, Joseph E Gonzalez, and Ion Stoica. 2017. Opaque: An oblivious and encrypted distributed analytics platform. In USENIX NSDI. 283--298."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639266","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639266","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:12:26Z","timestamp":1755789146000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639266"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":55,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639266"],"URL":"https:\/\/doi.org\/10.1145\/3639266","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}