A new multi-object K-NN query algorithm based on the MBR of having been queried data objects
Guobin Li, Jine Tang · 2010
K-nearest neighbor algorithm is an important class of search algorithm in space database, the traditional k-nearest neighbor query algorithm will search K-neighbor objects according to measure distance and pruning strategy, when continue to find the next neighbor, it often needs a lot of distance calculation in order to exclude unnecessary search area, the query algorithm is inefficient, in the case of a large amount of data, the time cost spent on frequent calculation is very large, the improved k-neighbor search algorithm in this paper is based on the first few neighbor objects already calculated to determine the next minimum bounding rectangle (MBR) to be queried, when the number of K-neighbor objects needed to be found is large, the next MBR to be queried is the one which contains the first neighbor object in each cluster direction, at the same time, the MINMAXDIST between this MBR and the queried object is the smallest, and the MBR contains the neighbor object not included in the queried neighbor object, so it will enhance the proportion of the achieved neighbor objects, and on this basis, it can optimize the multi-object K-NN query algorithm, the more the queried objects, the higher the implementation efficiency.