一种采用Z曲线高维空间范围查询算法  

High-dimensional Spatial Range Query Algorithm Based on Z Curve

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

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

出　　处：《小型微型计算机系统》2009年第10期1952-1955,共4页Journal of Chinese Computer Systems

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

摘　　要：低维空间中线性扫描算法及基于R树、VA文件和NB树的空间范围查询算法的效率较高,高维空间中它们的效率出现恶化现象.Z曲线将空间分割成大小相等网格并依次穿过它们,将网格中的点映射到线性空间中,从而能够使用B+树作为点集的索引结构.利用Z曲线聚类和降维特性,本文给出网格划分方法、搜索区域分解过程,提出一种高维空间范围查询算法.实验结果表明在高维空间中算法的效率优于上述算法.Spatial range query algorithms based on brute-force method, R-tree, VA-file, NB-tree achieve better performance in low- dimensional space, but their performances suffer greatly in high-dimensional space. Reduction of dimensionality is the key to spatial range query in high-dimensional space. Z curve has been used as a mapping method from high-dimensional space into linear space, divide space into grids, and imposes a linear order of points in grids. Based on Z curve, the paper presents a method of grid partition, a procedure of partitioning search region, and a high-dimensional spatial range query algorithm. Experimental results indicate its performance is better than that of spatial range query algorithms based on brute-force method, R-tree, VA-file, NB-tree.

关 键 词：空间范围查询 降维 Z曲线 网格划分 搜索区域 

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