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

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

作　　者：徐红波[1] 郝忠孝[1,2] 

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,哈尔滨150080 [2]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《计算机科学》2010年第1期184-188,共5页Computer Science

基　　金：黑龙江省自然科学基金(F200601)资助

摘　　要：在建树过程中,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.

关 键 词：空间填充曲线 网格划分 最近邻 降维 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]