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

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

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

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 grid...