14 | 空间检索(下):“查找最近的加油站”和“查找附近的人”有何不同?
该思维导图由 AI 生成,仅供参考
直接进行多次查询会有什么问题?
- 深入了解
- 翻译
- 解释
- 总结
本文介绍了在地理位置服务中,如何实现动态调整范围的高效检索方案。作者首先讨论了针对不固定查询范围的应用需求,如查找最近的加油站或医院,需要找到最近的一批满足要求的结果。为了解决多次查询的问题,作者介绍了利用四叉树动态调整查询范围的方法。四叉树的结构和特点被详细解释,并且说明了如何利用四叉树完成自动调整范围的Top K检索。通过引入四叉树,可以避免重复检索的开销,提升检索效率。此外,文章还介绍了如何利用非满四叉树优化存储空间以及如何用前缀树优化GeoHash编码的索引。总结来说,利用树形结构来划分空间提高检索效率的方案,它的应用非常广泛。对于更高维度空间的最近邻检索,还可以使用类似的检索方案来划分空间。文章内容涵盖了四叉树、非满四叉树、前缀树以及k-d树等多种树形结构,为读者提供了一种高效的解决方案。
《检索技术核心 20 讲》,新⼈⾸单¥59
全部留言(15)
- 最新
- 精选
- 奕当前地址的 GeoHash 编码为 wx4g6yc8,这个根据上节学的编码规范,前4个字母代码纬度,后面四个代表经度,如果去掉最后一个字符 不是代表纬度不变,经度的范围扩大 2 ^ 5 倍,这样的范围不应该是一个长方形吗? 怎么会是图中的正方形呢? ---------------- 作者回复: 你看得很仔细。Geohash由于是5个比特位为一个字符,因此的确是去掉一个字符的时候,范围形状是长方形。再去掉一个字符,就又变成正方形。 不过如果你再仔细看的话,你会发现这个图示是以二进制区域编码为例子的,因为它每次扩大只是四倍,而不是32倍。32倍的图不好画。。 我看看让编辑在图示里加上说明优化一下吧。 ----------------------- 老师,这里我在追问一下,在上一条下面评论怕你看不见: 也就是经度和纬度的字符交替的去掉吗?我看文中是连续去了最后的两个字母,也就是只操作了经度,纬度没变。还有就是下面Trie树是不是也不应该按照字母的顺序形成一个链了?也应该是经度,纬度交替的形成了?
作者回复: 的确评论是没有提醒的,不过评论有。所以大家可以多提问。关于geohash去掉一个字符时的查询范围变化,我在这里也补充一下。 Geohash一个字符是5个比特位,由于5是奇数,因此去掉的经纬度的个数是不相等的。比如说去掉了3个经度,2个纬度。因此就会从正方形变成长方形。 而如果再去掉一个字符,那这一次正好反过来,会去掉2个经度,3个纬度。和上一次去掉的3个经度和2个纬度合起来,就正好一共去掉5个经度,5个纬度。因此又恢复成正方形。
2020-04-285 - 那时刻在四叉树从当前子节点去搜索附近子节点时,需要去到上层父节点。如果子节点以双向链表类似B+树,是否可行呢?
作者回复: 你这个思考很好。四叉树能否使用b+树类似的双向链表呢?我来说说我的理解。 如果是满四叉树的话,那么我们可以将所有叶子节点使用双向链表连接起来。当我们查询到一个叶子节点不满足k个结果时,我们需要扩大范围,那么我们可以沿着左右两个方向去扩展。但是,我们是要扩展多少才OK呢?我们并不好判断新节点和当前节点的位置关系。你可以结合我文中的满四叉树的例子看看,如果查询到的节点是0110,其实离它最近的点可能是在1001区域中(见13讲中的区域编码图),它需要往右边走三个元素才能到达这个节点。因此,遍历并无法判断当前节点和新扩展节点之间的关系。不如递归便捷。 而如果是非满四叉树的话,叶子节点不是一个层级的,并且节点还会分裂。进行链表管理会更加麻烦。
2020-04-274 - 时隐时现老师好,有2个问题 1、文中所有树叶子节点里存放的是该区域内倒排索引的指针,还是倒排索引的所有key? 2、四叉树和Tire树省去的只有从根节点到叶子节点的遍历,如果对GeoHash编码采用B+树,整个树高度顶多4层,这种提升是很有限的吧?还是说查询次数很多,每次查询省去1个IO就能累积节省很多?
作者回复: 1.叶子节点其实存一个数组,记录所有属于这个区域的点就可以了。当然,如果你对于这个数组中的点还有其他的查询要求的话,也可以根据你的需要选用合适的数据结构,比如说不用数组,改用链表,或者位图。 2.提升的确是有限的,不是数量级的提升。但是在工程实现上,倍数级的提升其实也值得去优化。一次查询+递归返回,比多次查询会有倍数级的提升。
2020-05-083 - 那时刻在GeoHash通过去掉最后一位编码的方式来扩大搜索范围,比如这次搜索了四个编码块,下次搜索16个编码块。在这16个编码块里有上次已经搜索的四个编码块,请问老师,这里应该有去重处理吧?来避免重复查询。 想到一个方式就是对于已经搜索过的hash编码标记下,避免重复搜索。
作者回复: 你说的对,肯定会有去重处理。不过16个编码块是覆盖4个编码块的,因此我们直接使用16个编码块的检索结果就好了。否则对四个编码块再进行去重比较,其实代价是差不多的。
2020-04-2743 - 那时刻想到一种情况一个节点不一定生成四个叶子结点,比如某个城市的加油站都集中在某个小范围区域内,在上层节点看分裂子节点数量可能小于四。
作者回复: 是的。极端情况就是所有插入的数据都属于一个小区域,那么根节点就不需要分裂出其他分叉了。
2020-04-273 - 峰刚看到四叉树那段,就想着这不前缀树嘛,看到前缀树,想空间检索怎么能木有kd-tree,然后r-tree呢,我放心了,没有了哈哈哈。 以我的认知看,到了高维,先不是数据结构高效不高效的问题,先是高维诅咒引发的相似度不再有效问题,大家都很相似肿么搞,于是才有一帮人搞什么流形学习,在高维空间找低维表示,知识的世界就怎么无限延展开,我要老了=_=,哈哈哈,这个落点😜 最后回答下问题,这跟插入数据的分布情况有关,就比如根节点0011 0010 1001 1000,分裂,那根节点就可以多出两个二层节点00 10,然后一个节点指向0011 0010 ,另一个指向1001 1000,这种做法就偏b树的分裂方式,当然也可以优先对前缀最多的子节点集合进行分裂下推,都是动态分裂的策略问题,看你想达到什么效果,比如数据库b+树的分裂不会是两边子节点一样多,而是会让id 大的那边空一点,考虑的是id 经常是自增的,所以一般再有元素插入就在id 大的那边。
作者回复: 哈哈,的确四叉树的这个用法和思路其实和前缀树很像。从这个角度来看,空间检索和字符串检索是有相似的地方的。 k-d树必须有,不过就像你说的,到了高维度以后,会有着无法精准检索的问题,因此许多高维度的相似检索问题都是使用近似最近邻检索方案来完成,而不是使用k-d树。这在后面会有介绍。
2020-04-273 - Lukia老师好,请教一个问题,在使用4叉树做精确查找时感觉依然存在性能问题(需要同时查看周围的八个格子,在四叉树的表现上就是需要先查看当前节点的父节点,再查看父节点的兄弟节点的八个字节点
作者回复: 是的,如果是精确距离查找的话,需要用九宫格法查询周围八个格子。性能开销会变大。不过这是精准查找和非精准查找的区别,不是四叉树和数组(或二叉树)的区别。同样是精准距离查找,四叉树和数组相比,依然性能会更好一些。
2020-08-041 - 范闲四叉树最终分裂的时候不是4个节点,可能是因为数据分布造成的.假设有00 01 和10三类节点,如果00和01的数据量大,那分裂的时候可能就只有00和01.10被分到了01节点上
作者回复: 不会的哦。如果有10这个数据的话,那么它会是和01平行的独立一个分支,并不会合并到01中。 其实你在前面已经说出了正确答案了,就是“数据分布造成的,假设有00,01和10三类节点”。 你可以看这么一个例子,根节点阈值是4,目前只存有3个数据,分别属于00,01和10三个区域。如果再加一个00区域的数据,引发了根节点分裂,那么由于数据分布只在00,01和10三个区域上,因此只需要分裂出这三个叶子节点就好,并不需要分裂出11这个没有存任何数据的叶子节点。
2020-04-2721 - 愤怒的虾干老师你好,我有个疑问,如果四叉树中间节点不存数据,那么当往上遍历到父节点时仍然需要递归遍历父节点的其他子节点,这样不就和开始讲的原始流程一层层向外遍历判断一样了吗?感觉并没有减少检索次数,还请帮我解答这个疑问。
作者回复: 性能会有一些优化。 往上遍历,那么定位到父节点的时间代价只有o(1),然后再往父节点的其他子节点查找,数据一定是非空的(如果其他子节点数据都是空的,那么通过父节点的数据总量统计可以快速得知,从而能快速返回更上一层)。 但如果是向外遍历,每次都要去检查周边一圈最小单位的格子是否有数据,这里面就可能有大量无效操作。 因此,基于树的查询方案会效率更高,原因是可以快速跳过许多无效检查。
2021-03-09 - 胡鑫老师你好 这种四叉树或者前缀树一般都是存在内存中吧,怎么才能保证这些内存中的数据不丢失? 是不是如果我们已经构建了四叉树的索引,就不需要倒排索引了,我所说的倒排索引是类似key=0101 value 等于0101上所有的点。谢谢
作者回复: 1.内存数据如何持久化存储,这是另一个话题。其实可以参考Redis的做法,通过将内存数据存入磁盘完成持久化。 2.索引是可以单独使用,也可以组合使用的。如果单独使用的话,使用了树形索引,就不需要使用倒排索引;不过也可以组合使用:在上面几层使用树形索引,叶子节点使用倒排索引。具体的组合索引的例子,可以参考第二阶段的测试题中的例子。
2021-01-24