k近邻（KNN）是许多机器学习，数据发掘和科学核算运用程序中运用的首要内核之一。虽然现已提出了依据kd树的O(log n)杂乱度算法来核算KNN，但因为其固有的次序性，实际上仍是在运用线性算法。这将此类办法的适用性约束在数百万个数据点上，而关于科学范畴的大数据分析应战而言，可扩展性有限。在本文中，提出了适用于散布式体系结构的并行且高度优化的依据kd树的KNN算法（结构和查询）。咱们的算法运用了新颖办法，包括修剪查找空间、改善节点和线程之间分配的负载平衡。运用来自天体物理学，等离子物理学和粒子物理学的三个科学运用TB级巨细的数据集，证明了能够运用50,000个中心在48秒内可结构包括1,890亿个节点的kd-tree，还演示了在12秒内核算190亿次查询的KNN。咱们展现了同享和散布式内存核算机的近似线性加快。咱们的算法比前期完成的算法功能稀有量级的进步，从根本上改善对最新的大数据分析问题的适用性。
k最近邻（KNN）算法是机器学习的根本分类和回归办法。 KNN用于许多使命，例如文本分类[1]，经济事情的猜测[2]，医学确诊[3]，图画中的方针分类，蛋白质相互作用的猜测等。 KNN经过在特征空间中找到与给定查询点的k个最接近的点来作业。然后运用街坊的相应值（例如对离散分类问题运用大都表决，或在接连回归设置中取均匀值）来核算查询的接连或离散猜测输出值。
跟着杂乱数据搜集机制的呈现，在大型数据集上进行机器学习变得十分重要。比如宇宙学和等离子物理学之类的科学学科在数十亿个粒子的范围内履行模仿，而且每个时刻步长发生数TB的数据[4]。大亚湾和大型强子对撞机等现代粒子物理试验布置了不计其数个能够在纳秒级精度捕获数据的传感器。
这样的试验每年能够发生1000 TB的数据。关于如此大的数据集，数据一般散布在机器集群中多个节点的内存中，而机器学习办法（例如KNN）有必要能够运用此数据并对它们履行散布式核算。此外，关于仿真数据，每个仿真时刻步有必要在几分钟的时刻内运转，以便对该范畴科学家适用，而且这也对机器学习模型施加了严厉的运转时刻约束。在数十亿个点的规划上，重要的是运用硬件中一切可用的并行性（在集群等级和每个核算节点内部），以便在适宜的时刻范围内供给成果。
因为KNN是在各种机器学习环境中运用的根本算法，因而已花费很多时刻使其在并行结构硬件上快速运转[5]，[6]，[7]。可是，大部分的作业都是为了下降算法的杂乱度或进行同享内存环境中的并行化。一项重要的算法奉献是引入了加快数据结构，例如kd-trees [8]（将一个k维空间中的点分层），然后将每个查询的近邻查找的点从线性削减到对数杂乱度。这样的数据结构在数据维数不是很高的各种科学运用中都能很好地作业，而且关于大型数据集至关重要，因为在大型数据会集无法为每个查询扫描整个数据集。此外，现已开发了能够运用单个同享存储机的多个内核来加快依据kd树的KNN的并行算法[5]，[6]，[7]。可是，在散布式环境中为并行处理做的作业还很少，散布式KNN的从前作业首要会集在每个查询的暴力线性时刻办法上，而不运用加快数据结构[9]，[10]。最近一种聚类算法，是在散布式环境中履行依据半径查找的最近邻核算。在散布式环境中，依据半径的查找是一个更简略处理的问题。固定半径可轻松修剪需求查找的点；实际上，关于较大的半径值，或许需求将整个数据集搜集到一个节点。这使其不适用于先验半径不知道的KNN。
kd树的KNN算法考虑简略的数据并行办法，其间数据在节点之间均匀散布；每个节点都构建自己的本地kd树。虽然这使得kd-tree结构简直平行，可是每个最近街坊查询都有必要在一切节点上运转，然后有必要在每个节点的成果上运转top-k算法以查找大局最近街坊。这会导致节点之间的互连上发生不必要的网络流量以及不必要的kd-tree遍历进程-实际上是为了找到k个最近的街坊，很简略看出咱们核算并传输了p*k个街坊，并丢掉了除最近的k以外的点。假如咱们能够在空间上对数据进行分区并在节点之间分配分区，则能够做得更好。实际上，咱们能够构建一个大局kd树，其间包括来自这些空间分区的所稀有据点。在这种情况下，均匀而言，关于每个查询，将仅查询O（log（P））节点，然后进步了可扩展性。这也相应地削减了通讯时刻。这儿的权衡是花费更多的时刻来构建kd-tree自身，可是kd-tree在大大都运用程序上下文中被很多重用。
kd树的构建和运用高度依赖于根底数据集的散布。除了挑选随机数据集外，还运用HPC模仿（宇宙学和等离子体物理学）和反应堆中微子试验（大亚湾）中的科学数据集。宇宙学和等离子物理学数据集代表了空间，遭到重力和电磁力影响的颗粒散布；大亚湾数据集代表了离散的时空事情。
在本文中，咱们演示了依据kd树的KNN核算的彻底散布式完成。据咱们所知，这是第一项此类作业。除了选用大局kd-tree办法之外，咱们还专心于各种优化，以运用集群和节点内的一切并行等级，然后快速构建和查询。此外，咱们经过软件流水线堆叠核算和通讯来进步网络功能。咱们得到的完成比单个节点上的从前办法快一个数量级以上。并跟着中心和节点的数量线 TB数据集）的kd树，并在12秒内对该数据集运转19B查询。
• 是第一个依据散布式kd-tree的KNN代码，已证明可扩展至约50,000个内核。
• 是第一个在大规划数据集上运转的KNN算法，来自不同科学范畴的海量数据集高达100B。
鉴于在科学运用中常常生成或观察到的数据集很大，因而有必要运用体系中一切可用的并行度来完成最佳功能。在许多触及数十亿个粒子的大型科学模仿中，每个模仿进程都需求针对大部分粒子运转k最近邻查询，这对散布式KNN查询提出了高功能要求。因为此类仿真一般处理低维数据，因而加快结构（如kd树）能够很好地作业，而且关于下降KNN查询的次序杂乱度至关重要。
曾经有关散布式KNN查询的大大都作业都是在一切节点上运用穷举查找，而不是运用kd树 [9]，[10]。虽然kd树供给了较低阶的杂乱性，但结构和查询此类树的确触及更多的大局数据重新分配和操控差异。然后有必要对kd-tree的结构和查询履行细心的优化，以取得改善的次序杂乱性。此外，在kd-tree的构建时刻与生成树的质量（决议查询时刻）之间要进行权衡。在典型的模仿场景中，粒子在每次迭代结束时移动，而且期望每隔几回迭代就重建一个新的kd树，以坚持快速查询。这意味着在散布式环境中优化kd-tree结构和查询的功能很重要，也能够运用结构的灵活性。
在本节中，描绘了用于散布式构建的kd树和查询k最近邻的算法（称为PANDA）。咱们的算法运用了多重节点，多核和SIMD。咱们还描绘了在kd-tree构建和查询之间进行的权衡。
如前所述，咱们的算法是第一个彻底可扩展并优化的kd-tree构建算法，可扩展至50，000个内核。咱们经过在硬件的一切等级上运用并行性来完成这一方针：多节点，多核和SIMD。 kd树具有大局组件和部分组件。大局组件（称为大局kd树），是指数据集在节点之间依照其几许结构区分的树。部分组件（称为部分kd树）是指由给定节点之间构成的kd树。
（1）一种挑选是不对点进行大局重新分配，而让每个节点结构一个自己的（负载平衡的）点子集的独立kdtree。这样能够在树结构上完成杰出的功能，可是查询要慢得多，因为有必要将每个查询发送到一切节点才干取得正确的答案。
（2）另一个挑选是为一切点创立一个大的kd树。这必定触及点的大局重新分配，可是因为每个查询仅需求节点的一小部分来答复，因而削减了查询的运转时刻。
1.大局kd树结构：假定每个节点读取的点数大致持平（无特定次序）。在kd树的每个等级，都需求将数据点大致均等地分为两个子集。经过挑选一个维度和一个沿着该维度的拆分点来履行此拆分。挑选切割点后，节点需求重新分配，以便每个节点仅具有归于子集之一的点。这必定触及跨网络的通讯。该进程一向持续到每个节点都具有一个不堆叠的点子集中止。
2.部分kd树（数据并行）：然后，咱们持续履行此进程，以核算切割点并在每个节点的部分点上进行改组。在同享内存环境中，改组阶段仅触及移动索引，而不触及点自身。在部分kd树的顶层，没有满足的分支来运用线程级并行性，因而，咱们运用数据并行性来核算切割点和混洗点，并以广度优先的办法进行（一次一个等级）。一旦有满足的分支（一般为10个线程），咱们将进入下一个阶段。
3. 本地kd树（并行线程）：在此阶段，每个线程都从一组共同的，不堆叠的点开始创立kd树。为了保证缓存的部分性，这种树的构建以深度优先的办法进行。当节点中的点数到达阈值（最大存储桶巨细）时，咱们将其声明为叶节点。
4.SIMD打包：固定每个存储桶中的点后，咱们将对数据集进行混洗，以便将存储桶中的点定位在内存中。因为在查询时对bucket中的一切点（假如选中）履行穷举间隔核算，因而能够进步查询功能。
bucket巨细（等级数）的挑选：大局kd树有log2p个等级，其间P是节点数。在部分kd树中，咱们创立新的等级，直到叶节点中的点数≤预界说的bucket巨细。一旦到达此方针，咱们将中止创立新关卡并将点打包到存储桶中。较大的存储桶能够缩短构建时刻，但会使查询价值更加大（运用存储桶进行查询十分翔实）。依据经历，咱们发现32巨细的存储桶具有最佳功能
有用的最近街坊查询的关键是运用部分性，即咱们需求保证在几许上相邻的点也在内存中进行部分化。这用穷举查找办法是不或许完成的。可是，咱们能够结构一个彻底散布式的kd树，以保证几许域在节点之间进行分区。这意味着任何查询仅需转到一小部分节点即可精确核算最近邻。