Abstract: As the overlap between minimum bounding rectangles in the directory of R-tree is increasing very rapidly with growing number of the data, the performance of the nearest neighbor query algorithm based on R-tree deteriorates rapidly. To avoid the problem, the paper presented a nearest-neighbor query algorithm based on grid partition of space filling curve. Space-filling curve has the properties of dimension reduction and data clustering. Using space-filling curve,the algorithm divides 2D space into equal-size grids, and map points in grids into linear space. It only visits points in the grid which query point lies in and points in near grids of ctuery point. The paper implemented nearest neighbor query algorithms based on Hilbert curve, Z curve and Gray curve, and compared the difference of mapping algorithm and data clustering between three curves. Experimental results indicate that the algorithm is better than brutcforce algorithm and near-neighbor cauery algorithm based on R-tree.

Key words: Nearest neighbors,Grid,Space-filling curve,Reduction of dimensionahty