# Leveraging Reinforcement Learning for evaluating Robustness of KNN Search Algorithms

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 37 references that are in the map.
- First posted on arXiv 10 Feb 2021.

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

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Generalization through Memorization: Nearest Neighbor Language Models](https://mlsanity.com/paper/1911.00172/) (2019)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [Machine Learning in Python: Main developments and technology trends in data science, machine learning, and artificial intelligence](https://mlsanity.com/paper/2002.04803/) (2020)
- [EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph](https://mlsanity.com/paper/1609.07228/) (2016)
- [Deep Metric Learning and Image Classification with Nearest Neighbour Gaussian Kernels](https://mlsanity.com/paper/1705.09780/) (2017)

## Abstract (arXiv)

The problem of finding K-nearest neighbors in the given dataset for a given query point has been worked upon since several years. In very high dimensional spaces the K-nearest neighbor search (KNNS) suffers in terms of complexity in computation of high dimensional distances. With the issue of curse of dimensionality, it gets quite tedious to reliably bank on the results of variety approximate nearest neighbor search approaches. In this paper, we survey some novel K-Nearest Neighbor Search approaches that tackles the problem of Search from the perspectives of computations, the accuracy of approximated results and leveraging parallelism to speed-up computations. We attempt to derive a relationship between the true positive and false points for a given KNNS approach. Finally, in order to evaluate the robustness of a KNNS approach against adversarial points, we propose a generic Reinforcement Learning based framework for the same.