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

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

近邻问题的亚线性算法研究现状综述

大数据时代已经来临,海量数据计算要求设计亚线性算法。本文选择了大数据分析问题中比较重要的问题、即近邻问题,包括近似最近邻问题、近似k-最近邻问题以及全k-最近邻问题,对其亚线性算法的研究现状做了综述。