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

摘要

低维空间中线性扫描算法及基于R树、VA文件和NB树的空间范围查询算法的效率较高,高维空间中它们的效率出现恶化现象.Z曲线将空间分割成大小相等网格并依次穿过它们,将网格中的点映射到线性空间中,从而能够使用B+树作为点集的索引结构.利用Z曲线聚类和降维特性,本文给出网格划分方法、搜索区域分解过程,提出一种高维空间范围查询算法.实验结果表明在高维空间中算法的效率优于上述算法.