一种新方法来构造KD树根据预分类结果

文摘

搜索是最基本的操作之一,在许多复杂的系统。然而,复杂的高维空间中搜索过程将显著增加。k维(KD)树,作为经典的数据结构,已广泛应用于高维数据搜索至关重要。然而,目前常用的方法提出了KD树建设不稳定或耗时。本文提出了一种新的算法来构造一个平衡KD树基于预分类的结果。与前面类似的方法相比,新算法可以降低施工过程的复杂性(不包括预分类过程)O (KNlog₂O (Nlog N)水平₂N)水平,K是维度和N的数量数据的数量。此外,借助预分类结果,新方法的性能不再受初始条件,扩大应用范围的KD树。

1。介绍

如何快速搜索是最基本的问题之一,在许多研究领域1- - - - - -3),如网格重新映射,模式识别,射线追踪。然而,搜索问题的复杂性显著增加在高维空间中。的基本问题找到最近的点为目标点在高维空间为例。最直观的方法是计算距离的所有其他点,然后挑出点最短的距离。然而,维数越高,越昂贵的计算距离。计算目标点之间的距离和所有其他点在高维情况下很快就会变得不可接受。在这一点上,一个有效的算法来避免不必要的计算尤为重要。

KD树(4)是一个经典的数据结构存储k维点由二叉树的形式快速检索。不同于标准的二叉树,KD树的每一层可以划分不同的维度。由于其良好的性能在解决多维搜索的问题,它已广泛应用于多维搜索的关键数据(例如,区域搜索和最近邻搜索(5,6])。

有两个重要的业务建立KD树:一个是选择维度划分,另一种是选择准确的分割点。选择分裂维度、维度和最大方差或最宽的色散一般推荐(7),因为这样的选择可以分为搜索空间更加均匀。不过,为了简单起见,可以接受以循环的方式划分维度在许多情况下,特别是当点是均匀分布的。至于选择分割点,由于没有有效的平衡技术可用于KD树重建目前(8),中值点通常是建议直接选择建立一个平衡树(9]。

各种方法,针对中值快速而准确地指出,目前已经开发出来。快速排序(10)是最受欢迎的排序算法之一,在O (Nlog找中位数₂N)时间。此外,一种改进的方法(即。快速选择算法(11])甚至可以减少时间O (N)的水平,这被认为是最快的一个方法。不幸的是,这两种方法的性能可能会降低O (N²在最坏的情况)水平。尽管一些其他方法(例如,归并排序(12)可能保障在O (Nlog获取值₂N),他们的表现仍然是有点令人失望。

我们都知道,排序算法目前已经相对成熟。因此,它应该是一个直观的想法建立KD树基于预分类的结果。然而,一些以前的文献都关心这个想法。最好的作者的知识,布朗(13)是第一个提出一个方法来建立基于KD树在O (KNlog预分类结果₂在最坏的情况。曹(14)进一步提高该方法的性能通过替换超键与键预分类和建筑业。然而,这两种方法都必须保持K指数数组施工,这削弱了从O (Nlog施工过程的复杂性₂O (KNlog N)₂N)。此外,分裂的选择维度限制为了数组重用。

本文提出了一种新的方法来构造KD树根据预分类结果,不仅可以建立在O (Nlog KD树₂任意N)时间在任何情况下,也选择了分裂维度。节中详细描述的新方法2。实验的验证和分析部分所示3。最后,得出结论4。

2。算法

2.1。基本思想

布朗的方法将准备一个有序数组索引为每个分区。每个分区可以迅速实现根据它取决于索引数组。以分裂的顺序通过布朗(也就是一个例子。分裂,x,y和z反过来对3 d数据),假设索引数组排列从小型到大型,元素小于中位数属于左子树,而元素大于中位数是正确的子树(这条规则将通过本文采用)。第一个分区的基础上x索引数组。中间的元素x索引数组中值点。索引数组的元素在上部属于左子树,元素在数组的下部属于右子树。选择中值点的开销仅仅是O(1)。为了准备第二个分区,它需要一个新的形式y索引数组后O (N)的比较。理论上,新y索引数组,第二个分区已经能够成功进行。然而,z索引数组也更新了布朗在第一分区。事实上,这是第三个分区的准备完成。如果z在第一个分区,索引数组不更新程序将无法确定哪些子树中的元素z在第二个分区索引数组属于,这将导致形成新的的失败z索引数组在第三分区。然而,这样的行动导致退化的复杂性从O (Nlog KD树结构₂O (KNlog N)₂N)。

因此,为了建立一个在O (Nlog KD树₂N)时间,只有下一个分区的索引数组有用可以保持施工。为了实现这一目标,我们需要确保每个元素清楚地知道哪些子树它属于每个分区。因此,我们设计了三个额外的整数数组记录对应元素的状态。他们是BN数组,党卫军数组,数组和坏蛋。每个数组的大小n . BN (我是用来记录的起始位置的子树的元素我属于。党卫军(j是用来记录剩下的子树的元素的数量元素的起始位置j。坏蛋(k)是用来记录元素的数量已经安排子树的元素的起始位置k。如果坏蛋(BN (我]]是不到一半的党卫军(BN (我]],这意味着元素我应该属于当前子树的左子树。类似地,如果坏蛋(BN (我]]大于一半的党卫军(BN (我]],这意味着元素我应该属于正确的当前子树的子树。如果坏蛋(BN (我]]等于一半的党卫军(BN (我]],这意味着元素我的中位数是当前子树。然后,BN (我]应该指向子树的中间领域,占据了(假设它指向米),学生(米应该设置为0。当坏蛋(BN (我]]= SS (BN (我]],这意味着所有元素在当前子树已经被处理,和相应的元素SS和坏蛋数组应该重置,准备下一个分裂。更具体地说,假设的起始位置当前子树的左子树和右子树l和R分别,然后SS (l和学生R)应设置为一半的党卫军(BN (我]],而坏蛋(l和坏蛋R应该设置为0。

让我们来建立一个KD树七2 d点作为一个例子。这七个点的坐标信息显示在图的左边1在“元组。“索引数组值的预分类x和y坐标列出从小型到大型列示在“预分类的结果。“BN的初始化、SS和坏蛋数组显示在“初始。“BN被初始化为0,表明当前子树的数据集从位置0开始。党卫军被初始化为7,这意味着有7元素在当前子树,和坏蛋被初始化为0,表明在当前子树的元素已经安排。应该注意,党卫军数组和坏蛋数组,只有党卫军[0]和坏蛋[0]是有意义的,对其他元素和作业对最终的结果没有影响。

完成这些准备工作之后,KD树的建设正式开始。为了简单起见,子树的每一层都除以x和y顺序和周期性。然后,第一个分区是通过处理的元素x索引数组依次从上到下。元素2、4和3小于中位数,所以他们属于左子树,应该留在的上部域被当前子树(即占领。BN数组中,相应的值应该是0 0)元素是中值,所以它应该位于当前子树(即中间。,BN[0] should be 3). Moreover, as this point will no longer belong to any subtree after being an intermediate node of the KD tree, SS[3] should be set to 0. Elements 5, 6, and 1 are greater than the median, so they belong to the right subtree and should be left in the lower part of the domain occupied by the current subtree (i.e., their corresponding value in the BN array should be 4). In the process of traversing the subtree starting from 0, the value of CUR[0] increases continuously, which is used to determine whether the current element belongs to the left subtree or the right subtree. After all the elements in the current subtree have been visited, CUR[0] is reset to 0. At the same time, the number of elements in the left and right subtrees will also be reset; that is, SS[0] and SS[4] will be set to 3. After the first partition, the values of these three arrays are shown in Figure1在“后第一次分裂。”可以看出,坏蛋数组是一个辅助数组,它只影响当前的分区。当前分区完成后,它将返回0。因此,其状态将不再显示在随后的分区的过程。第二个分区将根据完成y索引数组。的第一个元素y索引数组是0,(即当前元素的开始位置。BN[0])是3。党卫军[3]是零,这意味着当前元素不需要处理。第二个元素是2,2(即元素的起始位置。,BN[2]) is 0, and the number of elements in the current subtree is 3. Therefore, element 2 belongs to the left subtree of the current subtree, and BN[2] should be 0. The third element is 6, starting at 4 and belonging to the left subtree of the current subtree, so BN[6] is 4. The fourth element is 1, and the starting position is 4, which should be the median of the current subtree. Therefore, BN[4] is set to 5, and SS[5] is set to 0. The remaining elements can be processed similarly. The results are shown in Figure1在“后第二次分裂。“当所有的元素都选了KD树中的一个节点,党卫军数组中的所有元素为零,如图所示在“后第三分裂”图1。然后,最后的索引数组(即。,F array in the right side of Figure1)用于构造KD树可以很容易地从BN获得数组(这可以通过将完成我在BN的位置我F的数组)。它可以看到从上面的过程提出了构建KD树时,新方法并不管理准备一个完整的为每个分区索引数组,但只有保持下次的分区数据集。这个想法使新方法不再需要每次更新K索引数组。因此,它降低了时间成本。

应该注意的是,我们刚刚得到最后的索引数组结构,不是最终KD树。以前的算法使用递归方法来构建KD树,所以子节点可以轻松链接回到父节点。然而,前面的过程不再使用递归,所以是不可能转移子节点的父节点的信息,除非更多的空间用于存储信息的父节点。幸运的是,在获得最终的索引数组,我们可以再次访问索引数组按照相同的规则和秩序构建KD树递归地像以前一样。所不同的是,当前的递归遍历过程不再需要找到中间点只需要中间点从数组中范围的子树。应该注意的是,如果分割尺寸的选择不遵循一些固定的规则,需要额外的数组记录分割尺寸的选择结果之前建筑KD树递归。

2.2。详细描述

建立一个KD树的详细描述基于新方法如图2。第一步是预分类和初始化,在那之后,选择分裂维度和处理BN, SS,反复和坏蛋数组,直到党卫军数组中的每个元素为零。随后,最后根据BN数组索引数组构造F(事实上,F的结构数组也可以完成在分区没有BN数组)的帮助。最后,KD树正是构建递归地根据F数组。处理的主要流程BN, SS,坏蛋数组大框所示。D索引数组中的元素(即。,the splitting dimension) will be visited in turn from the beginning to the end. Suppose that the current element is tmpi. If the current element has already been selected (i.e., tmpsize is 0), it no longer needs to be processed. Otherwise, it is whether it belongs to the left subtree or the right subtree or is the median will be judged according to CUR[tmpBN]. If it belongs to the left subtree or the right subtree, BN[tmpi] will point to the starting position of the corresponding left or right subtree. Otherwise, BN[tmpi] will point to the middle of the segment occupied by the current subtree, and its corresponding value in the SS array will be set to zero. When all the elements in the current subtree have been processed, the corresponding elements in SS and CUR arrays will be reset as described in the foregoing subsection.

构建KD树递归的过程根据最后的索引数组F如图3。第一步是获得分裂维度。分裂维度可以遵循相同的规则或先前记录的分区结果。下一步是选择中值点。事实上,部分被当前子树的中间元素正是我们想要的。随后,起始位置和左和右子树的元素数量计算,分别。最后,左和右子树将构建递归直到在当前子树的元素数量为零。

2.3。复杂性分析

从上述讨论,众所周知,KD树构建的整个过程是由两部分组成。第一部分是建设以形成最终的索引数组,而第二部分是完全根据最终构建KD树索引数组。在第一个过程中,其中的一个预分类索引数组期间将遍历每个分区。虽然每个元素可能以不同的顺序访问,最后的结果是,所有的元素会被处理一次。因此,每个分区的时间复杂度是O (N)。有O (log₂N)分区的时候需要,所以第一个过程的时间复杂度是O (Nlog₂N)。值得注意的是,虽然每个分区将访问一些选定的节点,头顶上是有限的,对最终的执行时间的影响可以忽略不计。在第二个进程,每个KD节点的选择是O(1)时间来完成的。因此,它需要O (N)时间来构建KD树。增加这两个部分的复杂性,最后的新方法的时间复杂度是O (N日志₂N + N)。当N很大时,总时间可以被认为是O (Nlog复杂性₂N)。值得注意的是,新方法的时间复杂度是独立于最初的原始元素的顺序。这意味着,即使是在最糟糕的情况下,新方法的时间复杂度是O (Nlog₂N)的水平,也就是我们所期待的。

3所示。实验

新方法是用C语言来实现的。随着预分类过程不是本文的重点,为了简单起见,该函数“qsort”, C标准库提供的,用于预分类。有两个数据集用于测试。一个拥有2²⁴6-dimensional真实元素,与6 0到100之间的随机生成有效的小数位。其他拥有2¹⁷6-dimensional真正相同的元素范围。这两个数据集之间的主要区别是,后者的数据集的元素排列在每个维度由大变小。

图4显示了施工时间(秒)2¹⁸≤N≤2²⁴四维随机生成的真实元素基于新方法和改进方法(更详细的改进方法中可以看到[14])。因为这两个方法的执行时间是N日志应该成正比₂N,x设在扩展因子的日志₂N,所以结果可以安装两条直线。基于新方法的施工时间,圆圈和安装为实线,虽然建设时间基于改进的方法特点是钻石和安装虚线。从这幅图中可以清楚的看到,这两个方法的执行时间与Nlog几乎线性增加₂N的确,这表明我们的正确性分析新方法的复杂性。更重要的是,新方法的性能总是比改进的方法在目前的情况下,这正是我们预期。此外,建筑的开销增长快一点当元素的数量太大,这可能是由于缓存失败的增加引起的大规模数据。

为了进一步验证新方法的性能在不同的维度,我们仔细比较的新方法改进的方法和快速选择方法(更详细的流程的快速选择方法中可以找到15])。因为建设时间的所有三种方法往往与维度的增加线性增长,这三种方法的结果也安装在直线(见图5)。取悦是发现新方法几乎等效性能的快速选择方法。虽然基于新方法的执行时间仍然比快速选择方法的基础上,考虑到快速选择方法是最好的在处理随机数据,新方法表现得足够好。此外,改进后的方法执行同样在我们的3 d情况下更好的在我们的二维情况下,这是因为改进方法不保持不必要的索引数组在处理二维数据。与此同时,操作采用改进后的方法更简单。维护所有索引数组的缺点改进的方法是只显示在处理高维问题。

本文中采用的快速选择方法总是选择第一个元素的主元分区剩余的子数组。因此,它的性能在每个递归将降低O (N²)级别,当数组从大到小排列。图6显示了施工时间(秒)2¹⁷真正的元素(元素排列在每个维度从大到小)在不同的维度。基于新方法的施工时间接近零,新方法的结果是这个数字放大了100倍。比较图5执行时间,可以看出基于图的快速选择方法6甚至超过处理2的时间成本²⁴元素在图5。相比之下,新方法的性能相当稳定,而执行远比快速选择方法。它说明了新方法的性能不受初始条件影响的数据。

4所示。结论

在本文中,我们提出了一种新的方法,它可以确保在O (Nlog构造KD树₂N)时间(不包括预分类过程的开销),三个额外的帮助下整数数组。与以前的方法相比,新方法几乎相同的性能,基于随机数据的快速选择方法和在极端条件下表现更好。虽然改进方法(14)执行更好的在二维情况下,新方法的好处在高维情况下很快变得明显。

新方法适用于复杂的系统,需要大量数据的多维查询。例如,在一个基于键-值对云存储系统模型,多维查询通常需要一个完整的扫描整个数据集,这是非常低效的。的帮助下KD树,查询的效率将会大大提高(16),我们的方法将大大提高建筑KD树的效率。

为了进一步减少KD树建设的执行时间,并行性是至关重要的(17- - - - - -20.]。通常基于递归的施工方法进行施工并行的左、右子树。然而,主要的部分不再雇佣新方法递归计划。因此,发现数据结构的特点和过程的新方法,开发新的并行算法是我们今后研究的重点。

数据可用性

使用的数据来支持本研究的发现可以从相应的作者。

的利益冲突

作者宣称没有利益冲突有关的出版。

确认

我们之前工作的改进方法已经发表在“2020年IEEE 11软件工程和服务科学国际会议(ICSESS)”[14]。在本文中,作者提出了一种新的方法来构造KD树没有不断更新预分类索引数组,它执行比在高维情况下改进的方法。作者要感谢来自中国国家重点研发项目的资金(2018 yfc1406202)和中国国家自然科学基金(41830964)。

引用

1. W.-F。侯,D.-W。许,c . et al .,”一个高级k最近邻分类算法基于kd tree,”《2018年IEEE国际会议的安全生产信息化(IICSPI)重庆,页902 - 905年,中国,2018年12月。视图:谷歌学术搜索
2. 崔b . r . Komuravelli诉陆et al .,“平行SAH k d树结构,”诉讼的高性能图形(高压天然气会议10)萨尔布吕肯,页77 - 86年,德国,2010年6月。视图:谷歌学术搜索
3. m . Shevtsov a Soupikov, a·卡普”高度并行快速kd tree建设互动射线跟踪的动态场景,”计算机图形学论坛,26卷,不。3、395 - 404年,2007页。视图:出版商的网站|谷歌学术搜索
4. j·l·本特利“多维二叉搜索树用于关联搜索,“ACM的通信,18卷,不。9日,第517 - 509页,1975年。视图:出版商的网站|谷歌学术搜索
5. 肖b . g .圆珠笔,“最近邻搜索问题的并行算法在高维度,“暹罗期刊在科学计算,38卷,不。5,667 - 699年,2016页。视图:出版商的网站|谷歌学术搜索
6. Md。m . a . Patwary n . r . Satish n .他et al。“熊猫:Extreme scale平行再在分布式架构,”国际平行诉讼和分布式处理研讨会(IPDPS),页494 - 503年,芝加哥,2016年5月,美国。视图:谷歌学术搜索
7. j·h·弗里德曼,j·l·本特利和r·a·芬克尔”一个算法寻找最佳匹配对数预期的时间,“ACM交易的数学软件,3卷,不。3、209 - 226年,1977页。视图:出版商的网站|谷歌学术搜索
8. g . Adelson-velskii和e·兰迪斯”信息的组织,一个算法”苏联科学院学报》上卷,146年,第266 - 263页,1962年。视图:谷歌学术搜索
9. p . k . Agarwal k·福克斯,k . Munagala et al .,“并行算法构造范围和近邻搜索的数据结构,”美国第35届ACM SIGMOD-SIGACT-SIGAI研讨会美国,旧金山,CA, 2016年6月。视图:谷歌学术搜索
10. c·a·r·霍尔“快速排序”,电脑杂志,5卷,不。1,10到16,1962页。视图:出版商的网站|谷歌学术搜索
11. t·h·科尔曼、c . e .雷瑟尔森·r·l·莱维斯特et al .,算法导论美国剑桥,麻省理工学院出版社,MA,第3版,2009年版。
12. j . Zhang Y.-P。高,Y.-S。他et al .,“基于OpenMP双向归并排序的算法改进,”应用力学和材料,卷3682,不。1403年,24-29,2015页。视图:谷歌学术搜索
13. r·a·布朗,“建立一个平衡的k d树在O (kn O (log n))的时间,”计算机图形学技术杂志》上4卷,50 - 68年,2015页。视图:谷歌学术搜索
14. 曹y, X.-J。张,B.-H。段et al .,“一种改进的方法根据预分类结果,构建KD树”软件工程学报》第11届国际会议上和服务科学,第75 - 71页,北京,中国,2020年10月。视图:谷歌学术搜索
15. 曹y, b . Wang W.-J。赵et al .,”研究为非结构化网格搜索算法重新映射基于kd树”学报》第三届国际会议上计算机和通信工程技术,页29-33,北京,中国,2020年8月。视图:谷歌学术搜索
16. f . j .他y . Wu杨et al .,“多维云指数基于kd tree和r - tree,”《计算机应用,34卷,不。11日,第3221 - 3218页,2014年。视图:谷歌学术搜索
17. gdp Fatta d .抚摸,“并行动态负载平衡kd tree k - means, "学报2010年IEEE 10计算机和信息技术国际会议布拉德福德,页2478 - 2485年,英国,2010年6月。视图:谷歌学术搜索
18. l . Hu s Nooshabadi m·艾哈迈迪,“大规模并行kd tree建设和最近邻搜索算法,”《2015年IEEE国际研讨会上电路和系统(ISCAS 2015)5卷,第2755 - 2752页,里斯本,葡萄牙,2015年5月。视图:谷歌学术搜索
19. d . Wehr和r . Radkowski“平行kd tree GPU自适应分割和建设策略,”国际期刊的并行编程,46卷,不。6,1139 - 1156年,2018页。视图:出版商的网站|谷歌学术搜索
20. 基于m . Cheng“平行SAH KD树构造算法,”先进材料的研究卷,433 - 440,3543 - 3547年,2012页。视图:谷歌学术搜索

版权

版权©2020余曹等。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。