前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >每周学点大数据 | No.27高维外存查找结构——KD 树

每周学点大数据 | No.27高维外存查找结构——KD 树

作者头像
灯塔大数据
发布2018-04-08 15:26:02
1.4K0
发布2018-04-08 15:26:02
举报
文章被收录于专栏:灯塔大数据

No.27期

高维外存查找结构——KD 树

Mr. 王:以往我们在数据结构中进行的查找,都是查找某一个键值或者某一个区间内的值,这样的查找称之为一维查找。

小可:难道说还有多维查找吗?

Mr. 王:现在我们就来介绍一种高维查找结构——KD 树。

小可:可是什么样的查找是高维查找呢?

Mr. 王:举个简单的例子。你平时会用到位置服务的App 吗?

小可笑着说:我今天中午还用大众点评查找过周围的饭店,饱餐了一顿呢。

Mr. 王:你的位置在定位系统和定位服务中就是一个坐标,这个坐标就是一个二维数据项。

你在查找周围的饭店时,就已经进行了一次二维空间内查找。我们现在要考虑的,就是如何能让计算机中存储的这种二维的点,并且可以以非常高的效率查找出来。

小可:原来是这样。那么如何来实现二维空间内的高效查找呢?

Mr. 王:计算机工作者们曾经提出过很多种二维空间内查找的方法,像网格文件、R 树、四叉树等,在实际应用中使用最多的应该是R 树。今天我们要讲的二维空间内查找结构叫作KD 树,之所以讲它,是因为它的性质比较容易保证。

小可:那什么又是KD 树呢?

Mr. 王:简单来说,KD 树很像是将两个二叉树叠在一起。考虑一下:当我们进行一维数据查找时,需要在一维上对数据进行索引,建立的就是一棵二叉查找树;而当我们要查找的点是一个二维数据时,就需要在两个数据维度上都建立索引,这时就需要两棵二叉树,这两棵二叉树分别索引的是x 轴和y 轴,我们可以在两棵轴上面进行二分搜索。而将两棵二叉树的层次交替存储,就合并成了KD 树。

小可:KD 树具体是如何定义的呢?

Mr. 王:在一棵KD 树上,我们用树的偶数层中的节点来表示空间中的水平线;相应地,我们用奇数层中的节点来表示空间中的垂直线;这些垂直线和水平线会对整个区域进行分割,直到点集被划分为每个区域内只有一个点为止。那么水平线和垂直线也就相应地对应着KD 树的内部节点,而在二维平面上,我们要检索的这些点就对应着KD 树的叶子节点。

小可带着疑惑的表情说:我还是不太明白。

Mr. 王:我们来举个例子吧。

左边是一棵KD 树,右边是一个二维平面。下面我们分步演示它的过程。

我们将树根定义为一条水平线,在区域中画下它代表的水平线。

下一层中的节点代表的是垂直线,我们在图中标示出这两条垂直线。

依此类推,这样所有的点都被放进了单独的一个区域里。也就是说,每一片叶子都已经仅仅代表一个节点,KD 树就建好了。

小可:哦,这样我就明白多了。那么对一棵建好的KD 树又是怎样进行查询的呢?

Mr. 王:在查询一棵KD 树时,我们会递归访问节点的相应交叉查询区域,并且报告在树/节点中且在查询中完全包含的点。

这样说太抽象了,我们还是举个具体的例子吧。看图中的绿色区域,在这个检索中,我们希望找出绿色区域中的点。

首先我们来看绿色区域的下界。

对一棵KD 树来说,它的根是一条水平线,我们就可以根据绿色区域的下界画一条水平线。

然后比较这条水平线和根的高低,在KD 树上,就是比较树根代表的水平线的高度值和检索区域的高度值。比如在这个例子中,我们发现根节点的高度比下界要高,这说明根节点的右子树一定都是候选集合,而根节点的左子树只有一部分是候选集合。

但是为了确定这一部分,我们就要访问它的左子树。然而树的第1 层(根是第0 层)是用来表示垂直线的,我们无法用它来判断水平维度的高低。我们再去访问第2 层,在第2 层中,可以用这个下界和第2 层中的两个节点进行比较,从而得出下一次,我们继续向右子树查找。

同理,我们可以不断地用区域的四个边界在树上进行查找,根据树的层次交替采用横纵的线条树上查找,直到最终确定绿色区域内部所有的点,也就是KD 树上的叶子节点。

现在我们来考虑一下KD 树的查询效率如何。现在你觉得这棵树是不是适合磁盘存储呢?

小可:虽然KD 树来用特殊的设计有效地表示了空间中的二维点,在设计思想上非常的巧妙,但是从本质上说,依然是一棵二叉树,它依然存在着二叉树不适合存储在磁盘上的问题,比如有旋转调整这样的麻烦。

Mr. 王:的确。由于KD 树同样具有二叉查找树的种种性质,所以也就同样存在二叉查找树在磁盘上存储种种不方便的问题。不过正是由于它和二叉树相似,所以我们不妨也采取和二叉树相似的改进方法。为了将查找树结构引入到磁盘上,我们引入了B 树。这次我们也可以发展KD 树,引入一种适合存储在硬盘上的数据结构——kdB 树。

小可:kdB 树是不是就是把KD 树和B 树融合到一起啊?

Mr. 王:是的,kdB 树结合了KD 树和B 树的思想,使得KD 树更加适合磁盘存储。在具体的实现中,逻辑结构依然采用KD 树,当叶子包含B/2 到B 个点时停止分割。在内部节点的BFS 块。

小可:那么如何在计算机中实际构建一个kdB 树呢?

Mr. 王:其实如果不考虑复杂度的话,这个算法还是很容易设计的。首先从所有的点中找到纵坐标y 轴的中位数,以这个中位数作为根节点的值。然后分别在两个区域中,寻找x 轴的中位数,这样就又画出了第二级中的两条垂直线,也就得到了树的第二层中的两个节点的值。

依此类推,递归地在新划分出来的区域中交替寻找x 轴和y 轴的中位数,这样KD 树就建好了。当然,我们还要将一定大小(数量)的节点像B 树一样封装在BFS 块中,这样kdB 树也就建好了。

这个算法是比较直观的,它的复杂度是

,不过它还是有一定的可优化空间的,我们还能给出一个更快的算法,其基本思想就是尝试对全体扫描一次完成构建

层,而不是像现在一样只构建一层。

小可:这里面数学符号太多了,没听懂。

Mr. 王:我们先来看看这个算法是怎么做的吧。

内容来源:灯塔大数据

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2017-02-24,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 灯塔大数据 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档