一种基于GPU的KNN动态扩展查询策略

作者：汤佳; 龚奕利; 李文海

来源：计算机工程, 2018, 44(06): 1-7.

DOI：10.19678/j.issn.1000-3428.0047069

• 图形处理器
• 计算统一设备架构
• 测试指标
• K最近邻查询
• 格网索引

传统的图形处理器(GPU)执行PGrid索引K最近邻(KNN)查询方法时存在查询粒度大、冗余计算多、性能不稳定等问题。为此,基于空间KNN关系查询,提出一种基于细粒度划分查找范围的KNN查询策略。基于欧氏距离的三角不等特性构建Cell的动态查询范围扩展,实现查询范围相对于Cell各个边界距离的细粒度划分和扩展,分析给定K值时对象数量的优化格网尺度。实验结果表明,与传统KNN查询方法相比,该查询策略在不同K值和格网划分尺度下具有明显的性能优势。

• 单位
  软件工程国家重点实验室