A Theory-based Evaluation Of Nearest Neighbor Models Put Into Practice

Abstract

In the \(k\)-nearest neighborhood model (\(k\)-NN), we are given a set of points \(P\), and we shall answer queries \(q\) by returning the \(k\) nearest neighbors of \(q\) in \(P\) according to some metric. This concept is crucial in many areas of data analysis and data processing, e.g., computer vision, document retrieval and machine learning. Many \(k\)-NN algorithms have been published and implemented, but often the relation between parameters and accuracy of the computed \(k\)-NN is not explicit. We study property testing of \(k\)-NN graphs in theory and evaluate it empirically: given a point set \(P \subset \mathbb\{R\}^\delta\) and a directed graph \(G=(P,E)\), is \(G\) a \(k\)-NN graph, i.e., every point \(p \in P\) has outgoing edges to its \(k\) nearest neighbors, or is it \(\epsilon\)-far from being a \(k\)-NN graph? Here, \(\epsilon\)-far means that one has to change more than an \(\epsilon\)-fraction of the edges in order to make \(G\) a \(k\)-NN graph. We develop a randomi

Stats

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

Related papers

• Revisiting \(k\)-nearest Neighbor Graph Construction On High-dimensional Data : Experiments And Analyses (2021)0.00
• An Adaptive Nearest Neighbor Rule For Classification (2019)0.00
• Minimax Optimal Algorithms With Fixed-\(k\)-nearest Neighbors (2022)0.00
• Explaining The Success Of Nearest Neighbor Methods In Prediction (2025)18.63
• Graph-based Nearest Neighbor Search: From Practice To Theory (2019)0.00
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph (2023)0.00
• EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based On Knn Graph (2016)0.00
• Adaptive Nearest Neighbor: A General Framework For Distance Metric Learning (2019)0.00