A New K-NN Query Algorithm Based On The Traversal And Search Of The Dynamic Rectangle

Along with the rapid development of the mobile computing, wireless communications and positioning technique, a large number of applications, such as traffic, trade, logistics, meteorological, military and so on , have piled up huge space data. People urgently need to carry on the query and analysis of these data in order to find the hidden knowledge or to make the correct decision.This paper first analyzes the merit and demerit of the K-NN algorithms by use of the traditional tree index and grid index , the traditional query algorithm will adopt the measurement distance and pruning strategy to improve the query performance by using the tree index, it needs to carry on a large amount of distance calculation to exclude the unnecessary queried region when continue to find the next nearest neighbor object, the cost of the time spent on the frequent distance calculation is great in the large amount of data objects, so the query efficiency is dramatically decreased, if adopts the grid index to conduct K-NN query, the query scope is not flexible, there will appear many empty grid cells, resulting in the slow searching speed and the low storage utilization.Based on the analysis and research of the previous K-NN algorithm, a new K-NN query algorithm based on the traversal and search of the dynamic rectangle is proposed in this paper, use the clustering method to cluster the spatial data objects to the horizontal and vertical directions of the queried object, select the appropriate rectangle to carry on dynamic movement and obtain the next query range to be searched, Adopt the dynamic rectangle to traverse and search the K-NN objects, due to carrying on clustering to the data objects, the distance between the data objects in the same class becomes smaller, the query region of the dynamic rectangle in each direction is not empty, the storage space is saved, use the number of the K-NN objects to be queried to select the size of the dynamic rectangle, it can exclude the artificial nature , so the search region has great randomness and is determined by the spatial distribution of actual data objects, the dynamic rectangle size will be more reasonable, while it is able to effectively exclude the current unnecessary queried area, the search in the four directions is circular, in the traversal process, the dynamic rectangle only carries on one division of the queried objects region in one direction, after finishing the query to the data objects in the rectangle of the former direction, it will turned to the next direction to divide the region to be searched, it can avoid a certain direction to be the occupied longer, since the next searched direction is the next direction having the minimum neighbor distance in the above traversal process, the order of the neighbor objects to be queried tends to be the order in the final sorting queue, it only needs to carry on a small amount of the adjustment among the objects, the query efficiency is improved,This paper will adopt Java language to achieve the simulation and testing of the new K-NN query algorithm based on the traversal and search of the dynamic rectangle, then uses the relevant performance standards already acknowledged in this field, applies a large number of space database test data set visited at random, and realizes the testing and comparison of the K-NN algorithm by use of the new K-NN algorithm ,tree index and grid index , the experiment show that the new K-NN algorithm is obviously superior to the traditional index algorithm in performance, compared to the tree index, it no longer needs to carry on much computation and pruning strategy to achieve the effective query region, compared with the grid index, the frequency of expanding the search region outward is also greatly reduced, the space utilization is significantly improved.