6.2.4. 附录(背景)

1. Geohash描述

(1) GeoHash 编码

地理位置检索服务在日常生活中随处可见,小到共享单车、高德地图,大到飞行航线轨迹。上述服务中很多相关功能都可以通过GeoHash来实现,Lucene/Solr中也有应用到GeoHash,通过GeoHash创建索引、查询索引以及距离的计算等等。

Lucene内部sandbox包支持地理位置检索,默认实现可以支持方形,圆形和多边形的地理位置检索。

GeoHash算法本质上是空间索引的一种方式。我们可以将整个地球设想为一个二维平面,将地球上所有区域展开平铺之后通过递归分解将该平面切分为32个模块。之后再将其中的模块再进行分块,随着范围不断缩小,位置精度也越来越高。每个分块都由一定的标识来表示该块。而地球上所有经纬度坐标都会通过GeoHash算法转变为一个唯一的base32标识,该标识对应上述分块的标识,一层一层的确定分块位置,最终便可通过标识找到具体的地理位置。

首先贴出base32编码表:

img

base32编码表

对于给定的一组经纬度数据(116.389550, 39.928167),使用二分法无限逼近。对纬度39.928167进行编码:

1) 区间[-90,0),[0,90],39.928167在右区间内,取1;

2) 区间 [0,45),[45,90],39.928167在左区间内,取0;

3) 区间 [0,22.5),[22.5,45],39.928167在右区间内,取1;

4) 不断递归进行二分拆解,慢慢缩小范围(最多缩小13次)...

5) 最终纬度编码为1 1 0 1 0 0 1 0 1 1 0 0 0 1 0;

对经度116.389550做上述操作,可得经度编码1 0 1 1 1 0 0 0 1 1 0 0 0 1 1。

得到经纬度的二进制位后需要对其进行合并。奇数位取纬度,偶数位取经度,每次取其二进制位的一位(不足为取0),最终合并成一个新的二进制串:

11100 11101 00100 01111 0000 01101

每5位为一个10进制数,换算过来为28、29、4、15,0,13。通过换算过来的5个十进制数便可对照上面的base32表得到该经纬度对应的encode标识:wx4g0e。将标识编码转换为经纬度的decode算法与之相反。

经过以上过程,便可将一长串经纬度数据简化为一段短小的URL标识——wx4g0e。

在得到标识之后,便可以只通过标识在地图上寻找对应的具体位置了。首先现在已分好的板块中找到W。找到W块后,再将W块进行分块,从子块之中找到X块。随后继续将X块细分,从X块的子块中找到4块。以此类推...随着不断地细分,直至找到wx4g0e对应的子块。

在该子块对应的区域内,即一定的经纬度范围内,他们的标识相同。也就是说,每一个字符串标识,都代表了而某一矩形区域。在这个矩形区域内的所有点,都共享GeoHash字符串标识,这样既可以保护隐私,又容易做缓存。

(2) GeoHash优势

GeoHash因为是字符串查询,本身是比较耗时的。但当其做了索引之后,其查询速度是快于普通查询的,尤其是当第二次命中时查询速度比普通查询二次命中会更快。原因也很简单:单列索引、单列命中显然是高于多列的。GeoHash查询出来的仅仅是某个范围内的数据,需要对返回的数据在进行距离运算,排序后最近的便是。其优化效率主要体现在范围查询上。由上述分析可知,GeoHash是相当有用且高效的一个算法,这个算法通过无穷的细分,能确保将每一个小块的GeoHash值确保在一定的范围之内,这样就为灵活的周边查找和范围查找提供了可能。

(3) GeoHash缺陷

GeoHash算法也存在一定的缺陷。由于GeoHash算法采用的是Peano空间填充曲线,虽然能够将将二维空间转换成一维曲线,但Peano空间填充曲线最大的缺点就是突变性,有些编码相邻但距离却相差很远,比如0111与1000,编码是相邻的,但距离相差很大。虽然geo确实尽可能的将位置相近的点hash到了一起,可是这并不是严格意义上的(实际上也并不可能,因为毕竟多一维坐标),例如在图中的红点虽然和上方的白点离的很近,可是它们的GeoHash值一定有差别,因为他们所属子块并不同;虽然在视野上红点和黑点离的很远,但他们因为同属一个子块,事实上GeoHash值相同。很多时候我们对GeoHash的值进行简单的排序比较,结果貌似真的能够找出相近的点,并且似乎还是按照距离的远近排列的,可是实际上会有一些点被漏掉了。

img

GeoHash误差示意图

2. Morton码

眼下有一替代GeoHash的方案——morton码(莫顿码)代替GeoHash。针对现有剖分模型的不足,有效避免了传统经纬度格网模型在高纬度地区的形状退化和正多面体格网模型的面片形状不规则问题。通过morton码,实现了面片编码与传统地理坐标之间的转换和邻接关系的计算,弥补了上述GeoHash算法中因地球不规则性和纬度变化带来的缺陷。

Morton码可以将多维数据转化为一维数据编码,根据一维编码位数可确定多维数据保留精度,是一种比较常用的压缩编码方法,尤其是作为哈希表的映射算法等,加速了树结构数据的存储和访问速度。

Morton编码也叫z-order code ,因为其编码顺序按照空间z序,编码结果展现为一种Z形的填充曲线。

img

Morton编码示意图

(1) lucene在实现地理位置检索上的缺点

由于morton码仅能用来表达一个方形的区域,而lucene在实现圆形,多边形地理位置检索的时候是先基于morton筛选出一个大致的范围,然后对筛选出来的每一条记录进行二次验证与剪切,以达到精确匹配的目的。

目前lucene的二次验证采用的是DocValues实现,DocValues字段是一个面向列存储的字段,DocValues是在Lucene4.0引入的新特性,属于正向索引。它存储文档编号到字段值正向关系的索引。

基于DocValues实现二次验证和剪切存在较多的随机IO,如果命中的记录条数很多,会导致整体地理位置检索性能非常的差。

(2) 改进办法

原先采用docvalues或正排数据进行地理位置(如圆形,多边形)的二次校验,也即原先进行地理位置(如圆形,多边形)的二次校验读取的数据分布在磁盘的不同位置,不连续。如下图所示:

img

数据分布示意图

更改为将相同的地理位置的数据存储存储在一起,通过构造连续数据,减少随机读取的次数:

img

修改之后数据分布示意图

Copyright © lucene.xin 2020 all right reserved修改时间: 2021-07-02 11:42:23

results matching ""

    No results matching ""