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

• 作者: 徐红波 郝忠孝
• 来源期刊: 计算机研究与发展
• 学科: 工学
• 关键词: Z曲线 最小网格 降维 近似 k-最近对
• 年，卷（期）: 2008,（2）
• 所属期刊栏目: 数据库技术与软件工程
• 页码范围: 310-317
• 页数: 8页
• 分类号: TP311.13
• 字数: 6121字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	郝忠孝	哈尔滨理工大学计算机科学与技术学院	152	1110	15.0	24.0
10	徐红波	哈尔滨理工大学计算机科学与技术学院	8	78	6.0	8.0