摘要：We present a new nearest neighbor (NN) search algorithm, the Partial KD-Tree Search (PKD), which couples the Friedman’s algorithm and the Partial Distance Search (PDS) technique. Its efficiency was tested using a wide spectrum of input datasets of various sizes and dimensions. The test datasets were both generated artificially and selected from the UCI repository. It appears that our hybrid algorithm is very efficient in comparison to its components and to other popular NN search technique - the Slicing Search algorithm. The results of tests show that PKD outperforms up to 100 times the brute force method and is substantially faster than other techniques. We can conclude that the Partial KD-Tree is a universal and efficient nearest neighbor search scheme.
