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

摘要：

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

关键词：Z曲线、最小网格、降维、近似、k-最近对

所属期刊栏目：45

分类号：TP311.13(计算技术、计算机技术)

资助基金：黑龙江省自然科学基金F00-06

在线出版日期：2008-05-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：310-317