【摘要】 考虑到在低维空间中基于线性扫描、R树、VA文件和NB树的空间范围查询算法的查询效率较高,而在高维空间中这些算法均出现不同程度的性能恶化现象,将降低空间维度作为解决高维空间范围查询问题的关键,并利用基于Z曲线的网格划分方法降低空间维度,使用Z区域聚类相似数据给出了一种改进的索引结构B~Z树,提出了一种深度优先高维空间范围查询算法ZRRQ。该算法采用高效剪枝策略,能够快速遍历B~Z树。实验结果表明,在高维空间中该算法优于基于线性扫描、R树、VA文件和NB树的空间范围查询算法。更多还原

【Abstract】 In consideration of the fact that the spatial range query algorithms based on linear scan, R-tree, VA-file and NB-tree can achieve better performances in low-dimensional space, but in high-dimensional space their performances suffer a great loss, the paper regards that the reduction of the dimensionality is the key to the spatial range query in high-dimensional space, and uses the Z curve-based grid partition method to reduce the dimensionality, giving an index structure of B~Z-tree and presenting a depth first high-dimensional spatial range query algorithm ZRRQ. It adapts an effective cutbranch strategy, can traverse B~Z-tree fast. The experimental results indicate that its performance is better than that of spatial range query algorithms based on linear scan, R-tree, VA-file and NB-tree.更多还原