一种基于Z曲线近似 k-最近对查询算法

摘要

k-最近对查询是空间数据库中重要操作之一.在低维空间中基于R*树分枝限界最近对查询算法(k-self-CPQ)和Brute-Force算法的查询效率较高,而在高维空间中其性能急剧恶化,降低空间维度成为解决问题的关键.依据Z曲线构造过程,将高维空间分割成大小相等的网格,以此将网格中的点映射到线性空间中.提出了基于网格划分的降维方法及最小网格概念,给出了基于Z曲线近似 k-最近对查询算法.利用最小网格的边长,算法优化线性扫描过程.实验结果表明在高维空间中算法性能优于Brute-Fore和 k-self-CPQ,且近似 k-最近对质量较好.