A New K-NN Query Algorithm Based on the Clustering and Sorting of Minimum Bounding Rectangle

The K-neighbor query algorithm is an important class of search algorithm in the spatial database, this paper will adopt the K-means algorithm to carry on sorting to the smallest enclosing rectangle in accordance with orientation relationship based on the measurement of distance and pruning strategies of MBR in the traditional K-nearest neighbor query, it can carry on the K-neighbor queries after sorting, as a result, the new algorithm can omit the need of a great amount of distance calculation between the queried object and the MBR as well as the need of the judgment when carry on pruning, the experiment shows that the algorithm query efficiency is enhanced, and has a wide range of applications in practice.