基于空间填充曲线网格划分的最近邻查询算法

Nearest-neighbor Query Algorithm Based on Grid Partition of Space-filling Curve

在建树过程中,R树存在最小边界矩形之间重叠的现象。当数据量较大时,重叠现象尤为严重,基于R树最近邻查询算法的性能急剧恶化。针对该问题,利用空间填充曲线的降低维度特性和数据聚类特性,提出一种基于网格划分最近邻查询算法。该算法将整个数据空间划分成大小相等、互不重叠的网格,对网格中的点进行线性排序之后,只需要访问查询点所在网格中的点及其周边邻近网格中的点,就能够获得最近邻。在Hilbert曲线、Z曲线和Gray曲线上实现3种最近邻查询算法,在映射算法和数据聚类特性上实验比较3种曲线之间的性能差异。实验结果表明,算法的查询性能明显优于顺序扫描算法和基于R树的最近邻查询算法。

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 spacefilling 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 query 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 brute-force algorithm and near-neighbor query algorithm based on R tree.