Leveraging Reinforcement Learning For Evaluating Robustness Of KNN Search Algorithms

Abstract

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.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyvadiraja2021leveraging

Related papers

• Certifiable Robustness For Nearest Neighbor Classifiers (2022)0.00
• Revisiting \(k\)-nearest Neighbor Graph Construction On High-dimensional Data : Experiments And Analyses (2021)0.00
• High-dimensional Approximate Nearest Neighbor Search: With Reliable And Efficient Distance Comparison Operations (2023)13.44
• Distributionally Robust Weighted \(k\)-nearest Neighbors (2020)0.00
• Adaptive Estimation For Approximate K-nearest-neighbor Computations (2019)0.00
• A Scalable Solution To The Nearest Neighbor Search Problem Through Local-search Methods On Neighbor Graphs (2017)3.58
• Effective And General Distance Computation For Approximate Nearest Neighbor Search (2024)5.84
• Adaptive Nearest Neighbor: A General Framework For Distance Metric Learning (2019)0.00