# Federated Nearest Neighbor Classification with a Colony of Fruit-Flies: With Supplement

arXiv: https://arxiv.org/abs/2112.07157 · HTML: https://mlsanity.com/paper/2112.07157/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 48 references that are in the map.
- First posted on arXiv 14 Dec 2021.

## Builds on (most cited first, 10 of 10)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Recurrent Models of Visual Attention](https://mlsanity.com/paper/1406.6247/) (2014)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Can a Fruit Fly Learn Word Embeddings?](https://mlsanity.com/paper/2101.06887/) (2021)
- [Bio-Inspired Hashing for Unsupervised Similarity Search](https://mlsanity.com/paper/2001.04907/) (2020)
- [Near-optimal sample compression for nearest neighbors](https://mlsanity.com/paper/1404.3368/) (2014)

## Built on by (most cited first, 3 of 3)

- [FlyLoRA: Boosting Task Decoupling and Parameter Efficiency via Implicit Rank-Wise Mixture-of-Experts](https://mlsanity.com/paper/2510.08396/) (2025)
- [Fly-CL: A Fly-Inspired Framework for Enhancing Efficient Decorrelation and Reduced Training Time in Pre-trained Model-based Continual Representation Learning](https://mlsanity.com/paper/2510.16877/) (2025)
- [Optimal rates for density and mode estimation with expand-and-sparsify representations](https://mlsanity.com/paper/2602.06175/) (2026)

## Abstract (arXiv)

The mathematical formalization of a neurological mechanism in the olfactory circuit of a fruit-fly as a locality sensitive hash (Flyhash) and bloom filter (FBF) has been recently proposed and "reprogrammed" for various machine learning tasks such as similarity search, outlier detection and text embeddings. We propose a novel reprogramming of this hash and bloom filter to emulate the canonical nearest neighbor classifier (NNC) in the challenging Federated Learning (FL) setup where training and test data are spread across parties and no data can leave their respective parties. Specifically, we utilize Flyhash and FBF to create the FlyNN classifier, and theoretically establish conditions where FlyNN matches NNC. We show how FlyNN is trained exactly in a FL setup with low communication overhead to produce FlyNNFL, and how it can be differentially private. Empirically, we demonstrate that (i) FlyNN matches NNC accuracy across 70 OpenML datasets, (ii) FlyNNFL training is highly scalable with low communication overhead, providing up to 8× speedup with 16 parties.