A Depth-first Adaptive KNN Searching Algorithm

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 r_min of the hyperball according to the rules, and then estimates the effective radius r_effective of other points´ hyperball. With the algorithm, the cost to find k nearest neighbors of one point is O(alphad)(1 les alpha Lt n),and the cost of preprocessing is O(dnlog₂n). Our experiment shows the algorithm performance is superior to other known algorithms