A Depth-first Adaptive KNN Searching Algorithm
Xiaopeng Yu, Xiao-Gao Yu, Deyi Zhou · 2006
Given n data points in d-dimensional space, k nearest neighbors searching involves determining k nearest of these data points to a given query point. A depth-first adaptive kNN searching (DAKNNs) algorithm is proposed. The algorithm finds k nearest neighbors of the query point in a small hyperball in order to improve the efficiencies. It firstly determines the minimal radius rminof the hyperball according to the rules, and then estimates the effective radius reffectiveof other points' hyperball. With the algorithm, the cost to find k nearest neighbors of one point is O(ad)(1≤ a ≪n), and the cost of preprocessing is O(dnlog2n). Our experiment shows the algorithm performance is superior to other known algorithms.