Author Login Editor-in-Chief Peer Review Editor Work Office Work

Computer Engineering ›› 2018, Vol. 44 ›› Issue (6): 1-7. doi: 10.19678/j.issn.1000-3428.0047069

Previous Articles     Next Articles

A KNN Dynamic Extended Query Strategy Based on GPU

TANG Jia,GONG Yili,LI Wenhai   

  1. State Key Laboratory of Software Engineering,Computer School,Wuhan University,Wuhan 430072,China
  • Received:2017-05-04 Online:2018-06-15 Published:2018-06-15

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

汤佳,龚奕利,李文海   

  1. 武汉大学 计算机学院 软件工程国家重点实验室,武汉 430072
  • 作者简介:汤佳(1991—),男,硕士,主研方向为并行计算;龚奕利、李文海,副教授。

Abstract:

Traditional Graphics Processing Unit(GPU) executing PGrid index K-Nearest Neighbor(KNN) query method has problems such as large query granularity,redundant calculation,and unstable performance.Therefore,facing spatial KNN relation queries,a KNN query strategy based on fine-grained partition search is proposed.Based on the Euclidean distance trigonometric inequality feature,the dynamic query range expansion based on Cell is constructed to realize the fine-grained partition and expansion of the query range with respect to each boundary distance of the Cell,and the optimum grid scales of object numbers for a given K value scale are theoretically analyzesd.Experimental results show that compared with the traditional KNN query method,the query strategy has obvious performance advantages under different K values and grid division scales.

Key words: Graphics Processing Unit(GPU), Compute Unified Device Architecture(CUDA), test indicators, K-Nearest Neighbor(KNN) query, grid index

摘要:

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

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

CLC Number: