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

一种基于邻居表的knn改进算法及其装置
技术领域
1.本发明涉及数据算法技术领域，具体涉及一种基于邻居表的knn改进算法以及应用于该算法的装置。


背景技术：

2.k最近邻(k-nearest neighbor，knn)分类算法，是一个理论上比较成熟的方法，其思路为：在特征空间中，如果一个样本附近的k个最近(即特征空间中最邻近)样本的大多数属于某一个类别，则该样本也属于这个类别。针对knn问题或者k近邻问题：给定一个数据集以及一个点，从数据集中找到距离给定点最近的k个数据，其在图像分类、信息获取、模式识别等方面有广泛的应用价值。
3.然而，针对在指定的平面区域内为一个特定的点查找距离最近的k个点的问题，现有knn算法在搜索区域中点的空间分布密度和有效搜索范围方面欠缺考虑，导致时间复杂度高；且此类算法不适合在gpu上大规模并行执行，故执行效率低。


技术实现要素：

4.本发明提供一种基于邻居表的knn改进算法及其装置，用以解决现有算法中存在的复杂度高、执行效率低等各种问题。
5.第一方面，本发明提供的一种基于邻居表的knn改进算法，该方法包括：
6.判断指定搜索区域的长宽比是否小于预设值；
7.如是，则将指定搜索区域作为搜索范围，根据预先设定好的阈值建立四叉树模型；
8.根据所建立的四叉树模型所划分的结点区域，通过空间位置找到每一个结点直接相邻的所有邻居结点，并行构建邻居表，其中，该邻居表用于在查找近邻点时快速确定有效搜索范围；
9.确定给定点所在的叶子结点区域；
10.基于查询邻居表的结点区域确定有效的搜索范围；
11.基于有效的搜索范围，并行计算该范围内所有点与给定点的距离，从而找出多个近邻点。
12.根据本发明提供的一种基于邻居表的knn改进算法，所述根据预先设定好的阈值建立四叉树模型，包括：使用四叉树方式逐层划分空间区域，先将初始空间区域划分为四个子区域，若子区域中点的数量大于预先设定好的阈值，则将该子区域进一步划分为四个更小的子区域，并按此方式不断递归，直至每个子区域中点的数量都不超过预先设定好的阈值，以确保每个叶子结点区域中点的分布密度相对均匀。
13.根据本发明提供的一种基于邻居表的knn改进算法，在建立四叉树模型的过程中，对每个子区域的边界点坐标进行存储，以及对包含的所有数据点的空间位置和数量等信息进行存储，从而将指定区域中的所有数据点相应地划分到四叉树模型的叶子结点对应的区域中，以确保每个叶子结点区域中点的分布密度相对均匀。
14.根据本发明提供的一种基于邻居表的knn改进算法，所述确定给定点所在的叶子结点区域，包括：根据给定点的空间位置，查找确定其所属四叉树中的叶子结点，即确定其所在叶子结点区域；若该叶子结点中点的个数》k值，则将其作为查询邻居表的结点；若该叶子结点中点的个数《k值，则将其父结点作为查询邻居表的结点。
15.根据本发明提供的一种基于邻居表的knn改进算法，所述基于查询邻居表的结点区域确定有效的搜索范围，包括：
16.初步确定搜索范围；基于查询邻居表的结点到邻居表中进行查询，查找与该结点直接相邻的邻居结点，将这些结点作为初步的第一搜索范围。
17.根据本发明提供的一种基于邻居表的knn改进算法，在初步确定第一搜索范围后，基于给定点到查询邻居表的结点边界的最远距离作为搜索半径，基于第一搜索范围内的结点到邻居表中进行查询，查找与这些结点直接相邻的邻居结点，并将处于或部分处于搜索半径内的结点作为第二搜索范围；
18.基于第一搜索范围和第二搜索范围，从而确定有效搜索范围。
19.根据本发明提供的一种基于邻居表的knn改进算法，基于有效搜索范围，采用多个线程并行计算该范围内所有点与给定点的距离，即可按照距离排序找到距离给定点最近的k个点。
20.根据本发明提供的一种基于邻居表的knn改进算法，在针对在指定的平面区域内为一个特定的点查找距离最近的k个点时，设置四叉树模型结点阀值大于k值，当按照搜索半径确定有效搜索范围时，若给定点的所在结点区域包含的数据点数量小于k，则以其父结点作为查询邻居表的结点，以确保给定点的k个最近邻点都已包含在有效搜索范围中。
21.根据本发明提供的一种基于邻居表的knn改进算法，所述判断指定搜索区域的长宽比是否小于预设值，包括：假设某个叶子结点所代表区域的长与宽分别为x，y，则搜索半径最长为该叶子结点所代表区域的斜边长，即由于搜索半径不大于该叶子结点的两倍长或者两倍宽，即不等式表示为或者化简后可以得到3*x2≥y2或者3*y2≥x2，也就是或者
22.第二方面，本发明还提供一种基于邻居表的knn改进算法装置，包括：
23.判断单元，用于判断指定搜索区域的长宽比是否小于预设值；
24.模型建立单元，如是，则用于将指定搜索区域作为搜索范围，根据预先设定好的阈值建立四叉树模型；
25.邻居表构建单元，用于根据所建立的四叉树模型所划分的结点区域，通过空间位置找到每一个结点直接相邻的所有邻居结点，并行构建邻居表，其中，该邻居表用于在查找近邻点时快速确定有效搜索范围；
26.结点区域确定单元，用于确定给定点所在的叶子结点区域；
27.搜索范围确定单元，基于查询邻居表的结点区域确定有效的搜索范围；
28.近邻点确定单元，基于有效的搜索范围，并行计算该范围内所有点与给定点的距离，从而找出多个近邻点。
29.由此可见，本发明在确定指定搜索区域的长宽比小于预设值后，可以根据点的空间分布密度合理划分搜索空间，并通过不同方法筛选出有效搜索范围，以提高查询效率；通
过预处理建立的邻居表和计算搜索半径，根据搜索半径确定的范围可进一步精确搜索范围，从而提高搜索效率。因此，本发明可降低knn搜索的时间复杂度，且实际搜索效率受指定区域大小和点的密度等因素的影响较小，适合在gpu上大规模并行执行，执行效率高，并行性高。
30.第三方面，本发明还提供一种电子设备，包括：
31.存储器，存储有计算机可执行指令；
32.处理器，配置为运行所述计算机可执行指令，
33.其中，所述计算机可执行指令被所述处理器运行时实现上述任一种的基于邻居表的knn改进算法的步骤。
34.第四方面，本发明还提供一种计算机可读存储介质，其中，所述计算机可读存储介质存储有计算机可执行指令，所述计算机可执行指令被处理器执行时实现上述任一种的基于邻居表的knn改进算法的步骤。
35.由此可见，本发明提供了一种基于邻居表的knn改进算法的电子设备以及存储介质，其包括：一个或多个存储器，一个或多个处理器。存储器用于存储程序代码和程序运行过程中产生的中间数据、模型输出结果的储存和模型及模型参数的储存；处理器用于代码运行所占用的处理器资源和训练模型时占用的多个处理器资源。
36.下面结合附图和具体实施方式对本发明作进一步详细说明。
附图说明
37.图1是本发明一种基于邻居表的knn改进算法实施例的流程图。
38.图2是本发明一种基于邻居表的knn改进算法实施例中关于在搜索空间建立四叉树模型(阈值为10)的示意图。
39.图3是本发明一种基于邻居表的knn改进算法实施例中关于建立邻居表的示意图。
40.图4是本发明一种基于邻居表的knn改进算法实施例中关于按照搜索半径确定搜索范围的示意图。
41.图5是本发明一种基于邻居表的knn改进算法装置实施例的原理图。
具体实施方式
42.为使本发明的目的、技术方案和优点更加清楚，下面将结合本发明中的附图，对本发明中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
43.参见图1，一种基于邻居表的knn改进算法，包括以下步骤：
44.步骤s1，判断指定搜索区域的长宽比是否小于预设值；
45.步骤s2，如是，则将指定搜索区域作为搜索范围，根据预先设定好的阈值建立四叉树模型；
46.步骤s3，根据所建立的四叉树模型所划分的结点区域，通过空间位置找到每一个结点直接相邻的所有邻居结点，并行构建邻居表，其中，该邻居表用于在查找近邻点时快速确定有效搜索范围；
47.步骤s4，确定给定点所在的叶子结点区域；
48.步骤s5，基于查询邻居表的结点区域确定有效的搜索范围；
49.步骤s6，基于有效的搜索范围，并行计算该范围内所有点与给定点的距离，从而找出多个近邻点。
50.在上述步骤s2中，根据预先设定好的阈值建立四叉树模型，包括：使用四叉树方式逐层划分空间区域，先将初始空间区域划分为四个子区域，若子区域中点的数量大于预先设定好的阈值，则将该子区域进一步划分为四个更小的子区域，直至每个子区域中点的数量都不超过预先设定好的阈值，以确保每个叶子结点区域中点的分布密度相对均匀。
51.其中，在建立四叉树模型的过程中，对每个子区域的边界点坐标进行存储，以及对包含的所有数据点的空间位置和数量等信息进行存储，从而将指定区域中的所有数据点相应地划分到四叉树模型的叶子结点对应的区域中，以确保每个叶子结点区域中点的分布密度相对均匀。
52.在上述步骤s4中，确定给定点所在的叶子结点区域，包括：根据给定点的空间位置，查找确定其所属四叉树中的叶子结点，即确定其所在叶子结点区域；若该叶子结点中点的个数》k值，则将其作为查询邻居表的结点；若该叶子结点中点的个数《k值，则将其父结点作为查询邻居表的结点。其中，在查找确定其所属四叉树中的叶子结点时，可以通过并行搜索引擎进行查找，也可以采用其他查找算法。
53.在上述步骤s5中，基于查询邻居表的结点区域确定有效的搜索范围，包括：
54.初步确定搜索范围；基于查询邻居表的结点到邻居表中进行查询，查找与该结点直接相邻的邻居结点，将这些结点作为初步的第一搜索范围。
55.在初步确定第一搜索范围后，基于给定点到查询邻居表的结点边界的最远距离作为搜索半径，基于第一搜索范围内的结点到邻居表中进行查询，查找与这些结点直接相邻的邻居结点，并将处于或部分处于搜索半径内的结点作为第二搜索范围，然后，基于第一搜索范围和第二搜索范围，从而确定有效搜索范围。
56.在上述步骤s6中，基于有效搜索范围，采用多个线程并行计算该范围内所有点与给定点的距离，即可按照距离排序找到距离给定点最近的k个点。
57.在本实施例中，在针对在指定的平面区域内为一个特定的点查找距离最近的k个点时，设置四叉树模型结点阀值大于k值(建议设置阈值大于4倍k值)，当按照搜索半径确定有效搜索范围时，若给定点的所在结点区域包含的数据点数量小于k，则以其父结点作为查询邻居表的结点，以确保给定点的k个最近邻点都已包含在有效搜索范围中。
58.在本实施例中，判断指定搜索区域的长宽比是否小于预设值，包括：假设某个叶子结点所代表区域的长与宽分别为x，y，则搜索半径最长为该叶子结点所代表区域的斜边长，即由于搜索半径不大于该叶子结点的两倍长或者两倍宽，即不等式表示为或者化简后可以得到3*x2≥y2或者3*y2≥x2，也就是或者
59.具体的，当指定区域满足长宽比小于将指定区域作为搜索范围，根据预先设定的阈值建立一棵四叉树。将空间区域逐层划分为四个子区域，如果子区域中点的数量大
于阈值则进一步划分为四个更小的子区域，直到每个子区域中点的数量都不超过阈值。在建树过程中，存储子区域的边界点坐标、包含的所有点的空间位置和数量等信息，从而将指定区域中的所有点相应地划分到四叉树的叶子结点对应的区域中，确保一个个结点区域中点的分布密度相对均匀，如图2所示。
60.接着，建立邻居表，基于已建立的四叉树所划分的结点区域，根据空间位置找到每一个结点直接相邻的所有邻居结点(每个结点最多有8个直接邻居)，并行构建一张包括所有结点的邻居表，用于查找近邻点时快速确定有效搜索范围，邻居表如图3所示。
61.然后，确定给定点所在叶子结点，根据给定点的空间位置，通过并行查找确定其所属四叉树中的叶子结点，即确定其所在叶子结点区域；如果该叶子结点中点的个数》k值，则将其作为查询邻居表的结点；如果该叶子结点中点的个数《k值，则将其父结点作为查询邻居表的结点。
62.然后，初步确定搜索范围，根据上一步确定的用于查询的结点到邻居表中进行查询，查找与该结点直接相邻的邻居结点，将这些结点作为初步的搜索范围。
63.然后，确定搜索范围，为进一步精确查找近邻点的搜索范围，基于给定点到查询邻居表的结点边界的最远距离作为搜索半径，将搜索半径内的结点区域作为更精确的搜索范围，从初步搜索范围中去掉不需要搜索的区域，以及新增给定点到所在叶子结点直接邻居的邻居结点作为有效搜索范围，如图3所示。
64.最后，计算距离找出k个近邻。基于搜索范围，采用多个线程并行计算该范围内所有点与给定点的距离，从而按距离排序找到距离给定点最近的k个点。
65.进一步的，对于四叉树结点阀值的说明：四叉树结点阀值是四叉树数据结构中很重要的一个参数，它表示了一个四叉树叶子结点中最多可以存储的二维数据点数量。在传统的四叉树建树过程中，当一个新的数据点插入一个其所包含数据点到达四叉树结点阀值的四叉树叶子结点时，这个四叉树叶子结点就会被分裂，产生四个孩子叶子结点，其原来包含的数据点也会分别转存在其孩子叶子结点内。从另外一个角度来说，任何一个四叉树非叶子结点，其子孙叶子结点所包含的数据点总数必定大于四叉树结点阀值。
66.在面向gpu的四叉树中，其结点阀值的设置与相关的应用有关。例如，当四叉树用于knn问题时，四叉树结点阀值要求比k大(建议设置阈值大于4倍k值)，因为这样可以保证当按照搜索半径确定搜索范围时(如图4所示)，范围内至少包含了一个非叶子结点，从而确保了范围内包含了大于k个数据点，可以从中取k个最近邻。
67.进一步的，对于指定区域满足长宽比小于的说明，包括：当使用基于四叉树邻居表来进行knn搜索时，为了算法的可行性，需要限制仅从用于查询的结点的前两环(第一环指直接邻居，第二环指邻居的邻居)同级邻居内搜索k个近邻。前两环邻居的含义如图4所示，被搜索点所在叶子结点是12，其第一环邻居是与结点12有直接相连的结点(上、下、左、右、左上、左下、右上、右下)，例如结点9，13，11，7，10，14，6，18。其第二环邻居则是结点12第一环邻居各自的第一环邻居，例如结点15，16，19，20，17，8，5等等。
68.假设叶子结点12所代表区域的长与宽分别为x，y。那么搜索半径最长则是叶子结点所代表区域的斜边长，即因为需要限制仅从前两环同级邻居内搜索k个近邻，那么搜索半径应该不大于结点12的两倍长或者两倍宽，即不等式或
者必须成立。化简后可以到3*x2≥y2或者3*y2≥x2，也就是或者根据四叉树的属性，所有结点(包括跟结点)所代表的范围长宽比都是一致的，所以本实施例得出了基于四叉树邻居表的knn算法的指定区域最好能满足长宽比小于的条件，
69.在实际应用中，在指定区域为给定点(图4中为小三角)找k个最近邻，其包括以下步骤：
70.(1)根据阈值为指定区域建一棵四叉树，得到图2所示的区域划分结果；
71.(2)根据(1)所建四叉树结果建立邻居表，如图3所示；
72.(3)确定给定点的位置在结点12对应区域；
73.(4)查邻居表可得，结点12的直接邻居结点为：10、11、14、13、18、7、6、9；
74.(5)基于搜索半径进一步精确搜索范围：去除结点10；新增结点：16、19(即邻居结点的邻居)；如图4所示，最后确定的搜索范围：11、14、13、18、7、6、9、16、19。
75.(6)并行计算搜索范围中所有点(图中为小圆点)与给定点的距离，找到距离给定点最短的k个近邻。
76.一种基于邻居表的knn改进算法装置实施例
77.如图5所示，本实施例提供一种基于邻居表的knn改进算法装置，包括：
78.判断单元10，用于判断指定搜索区域的长宽比是否小于预设值。
79.模型建立单元20，如是，则用于将指定搜索区域作为搜索范围，根据预先设定好的阈值建立四叉树模型。
80.邻居表构建单元30，用于根据所建立的四叉树模型所划分的结点区域，通过空间位置找到每一个结点直接相邻的所有邻居结点，并行构建邻居表，其中，该邻居表用于在查找近邻点时快速确定有效搜索范围。
81.结点区域确定单元40，用于确定给定点所在的叶子结点区域。
82.搜索范围确定单元50，基于查询邻居表的结点区域确定有效的搜索范围。
83.近邻点确定单元60，基于有效的搜索范围，并行计算该范围内所有点与给定点的距离，从而找出多个近邻点。
84.在模型建立单元20中，根据预先设定好的阈值建立四叉树模型，包括：使用四叉树方式逐层划分空间区域，先将初始空间区域划分为四个子区域，若子区域中点的数量大于预先设定好的阈值，则将该子区域进一步划分为四个更小的子区域，并按此方式不断递归，直至每个子区域中点的数量都不超过预先设定好的阈值，以确保每个叶子结点区域中点的分布密度相对均匀。
85.其中，在建立四叉树模型的过程中，对每个子区域的边界点坐标进行存储，以及对包含的所有数据点的空间位置和数量等信息进行存储，从而将指定区域中的所有数据点相应地划分到四叉树模型的叶子结点对应的区域中，以确保每个叶子结点区域中点的分布密度相对均匀。
86.在结点区域确定单元40中，确定给定点所在的叶子结点区域，包括：根据给定点的空间位置，查找确定其所属四叉树中的叶子结点，即确定其所在叶子结点区域；若该叶子结点中点的个数》k值，则将其作为查询邻居表的结点；若该叶子结点中点的个数《k值，则将其
only memory，rom)、磁带、软盘、闪存或光存储器等。易失性存储器可包括随机存取存储器(random access memory，ram)或外部高速缓冲存储器。作为说明而非局限，ram可以是多种形式，比如静态随机存取存储器(static random access memory，sram)或动态随机存取存储器(dynamic random access memory，dram)等。
97.此外，上述的存储器中的逻辑指令可以通过软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：u盘、移动硬盘、只读存储器(rom，read-only memory)、随机存取存储器(ram，random access memory)、磁碟或者光盘等各种可以存储程序代码的介质。
98.由此可见，本发明提供了一种基于邻居表的knn改进算法的电子设备以及存储介质，其包括：一个或多个存储器，一个或多个处理器。存储器用于存储程序代码和程序运行过程中产生的中间数据、模型输出结果的储存和模型及模型参数的储存；处理器用于代码运行所占用的处理器资源和训练模型时占用的多个处理器资源。
99.以上实施例的各技术特征可以进行任意的组合，为使描述简洁，未对上述实施例中的各个技术特征所有可能的组合都进行描述，然而，只要这些技术特征的组合不存在矛盾，都应当认为是本说明书记载的范围。
100.上述实施方式仅为本发明的优选实施方式，不能以此来限定本发明保护的范围，本领域的技术人员在本发明的基础上所做的任何非实质性的变化及替换均属于本发明所要求保护的范围。

技术特征：
1.一种基于邻居表的knn改进算法，其特征在于，包括：判断指定搜索区域的长宽比是否小于预设值；如是，则将指定搜索区域作为搜索范围，根据预先设定好的阈值建立四叉树模型；根据所建立的四叉树模型所划分的结点区域，通过空间位置找到每一个结点直接相邻的所有邻居结点，并行构建邻居表，其中，该邻居表用于在查找近邻点时快速确定有效搜索范围；确定给定点所在的叶子结点区域；基于查询邻居表的结点区域确定有效的搜索范围；基于有效的搜索范围，并行计算该范围内所有点与给定点的距离，从而找出多个近邻点。2.根据权利要求1所述的方法，其特征在于：所述根据预先设定好的阈值建立四叉树模型，包括：使用四叉树方式逐层划分空间区域，先将初始空间区域划分为四个子区域，若子区域中点的数量大于预先设定好的阈值，则将该子区域进一步划分为四个更小的子区域，并按此方式不断递归，直至每个子区域中点的数量都不超过预先设定好的阈值，以确保每个叶子结点区域中点的分布密度相对均匀。3.根据权利要求2所述的方法，其特征在于：在建立四叉树模型的过程中，对每个子区域的边界点坐标进行存储，以及对包含的所有数据点的空间位置和数量等信息进行存储，从而将指定区域中的所有数据点相应地划分到四叉树模型的叶子结点对应的区域中。4.根据权利要求3所述的方法，其特征在于：所述确定给定点所在的叶子结点区域，包括：根据给定点的空间位置，查找确定其所属四叉树中的叶子结点，即确定其所在叶子结点区域；若该叶子结点中点的个数>k值，则将其作为查询邻居表的结点；若该叶子结点中点的个数<k值，则将其父结点作为查询邻居表的结点。5.根据权利要求4所述的方法，其特征在于：所述基于查询邻居表的结点确定有效的搜索范围，包括：初步确定搜索范围；基于查询邻居表的结点到邻居表中进行查询，查找与该结点直接相邻的邻居结点，将这些结点作为初步的第一搜索范围。6.根据权利要求5所述的方法，其特征在于：在初步确定第一搜索范围后，基于给定点到查询邻居表的结点边界的最远距离作为搜索半径，基于第一搜索范围内的结点到邻居表中进行查询，查找与这些结点直接相邻的邻居结点，并将处于或部分处于搜索半径内的结点作为第二搜索范围；基于第一搜索范围和第二搜索范围，从而确定有效搜索范围。7.根据权利要求6所述的方法，其特征在于：基于有效搜索范围，采用多个线程并行计算该范围内所有点与给定点的距离，即可按照距离排序找到距离给定点最近的k个点。8.根据权利要求1至7任一项所述的方法，其特征在于：在针对在指定的平面区域内为一个特定的点查找距离最近的k个点时，设置四叉树模型结点阀值大于k值，当按照搜索半径确定有效搜索范围时，若给定点的所在结点区域包含
的数据点数量小于k，则以其父结点作为查询邻居表的结点，以确保给定点的k个最近邻点都已包含在有效搜索范围中。9.根据权利要求1至7任一项所述的方法，其特征在于：所述判断指定搜索区域的长宽比是否小于预设值，包括：假设某个叶子结点所代表区域的长与宽分别为x，y，则搜索半径最长为该叶子结点所代表区域的斜边长，即由于搜索半径不大于该叶子结点的两倍长或者两倍宽，即不等式表示为或者化简后可以得到3*x2≥y2或者3*y2≥x2，也就是y:或者x:10.一种基于邻居表的knn改进算法装置，其特征在于，包括：判断单元，用于判断指定搜索区域的长宽比是否小于预设值；模型建立单元，如是，则用于将指定搜索区域作为搜索范围，根据预先设定好的阈值建立四叉树模型；邻居表构建单元，用于根据所建立的四叉树模型所划分的结点区域，通过空间位置找到每一个结点直接相邻的所有邻居结点，并行构建邻居表，其中，该邻居表用于在查找近邻点时快速确定有效搜索范围；结点区域确定单元，用于确定给定点所在的叶子结点区域；搜索范围确定单元，基于查询邻居表的结点区域确定有效的搜索范围；近邻点确定单元，基于有效的搜索范围，并行计算该范围内所有点与给定点的距离，从而找出多个近邻点。

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


技术研发人员：何希 陈佳 农健 吕美妮 陈聪 王银清 徐健 庞安隆
受保护的技术使用者：梧州学院
技术研发日：2022.10.24
技术公布日：2023/1/6