一种基于邻居表的KNN改进算法及其装置

摘要

本发明提供一种基于邻居表的KNN改进算法及其装置，该方法包括判断指定搜索区域的长宽比是否小于预设值；如是，则将指定搜索区域作为搜索范围，根据预先设定好的阈值建立四叉树模型；根据所建立的四叉树模型所划分的结点区域，通过空间位置找到每一个结点直接相邻的所有邻居结点，并行构建邻居表，其中，该邻居表用于在查找近邻点时快速确定有效搜索范围；确定给定点所在的叶子结点区域；基于查询邻居表的结点区域确定有效的搜索范围；基于有效的搜索范围，并行计算该范围内所有点与给定点的距离，从而找出多个近邻点。本发明用以解决目前现有算法中存在的复杂度高、执行效率低等各种问题，适合在GPU上大规模并行执行，执行效率高，并行性高。