FedKNN: Secure Federated k-Nearest Neighbor Search
Proceedings of the ACM on Management of Data · 12.03.2024 · 2 (1) · 1-26
DOI: 10.1145/3639266 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 26.03.2024. Verfasst von Xinyi Zhang und 4 weiteren Autor:innen. Die Arbeit wurde bisher 16-mal zitiert (Crossref) und nennt 55 Literaturangaben. Gefördert von: NSF of Guangdong Province, NSF of China, Hong Kong Research Grants Council.
Abstract (Originalsprache)
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× improvement on federated graph kNN search and up to 2.7× improvement on federated sequence kNN search. Additionally, our approach offers a trade-off between privacy and efficiency, providing strong privacy guarantees with minimal overhead.
Förderung
- NSF of Guangdong Province
- NSF of China
- Hong Kong Research Grants Council
Zitieren
APA
Zhang, X., Wang, Q., Xu, C., Peng, Y., & Xu, J. (2024). FedKNN: Secure Federated k-Nearest Neighbor Search. Proceedings of the ACM on Management of Data, 2(1), 1-26. https://doi.org/10.1145/3639266
Vancouver
Zhang X, Wang Q, Xu C, Peng Y, Xu J. FedKNN: Secure Federated k-Nearest Neighbor Search. Proceedings of the ACM on Management of Data. 2024;2(1):1-26. doi:10.1145/3639266
BibTeX
@article{Zhang2024,
author = {Zhang, Xinyi and Wang, Qichen and Xu, Cheng and Peng, Yun and Xu, Jianliang},
title = {FedKNN: Secure Federated k-Nearest Neighbor Search},
journal = {Proceedings of the ACM on Management of Data},
year = {2024},
volume = {2},
number = {1},
pages = {1--26},
doi = {10.1145/3639266}
}
EUVIMED