  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.
