空间索引 - GeoHash算法及其实现优化

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
简介:

转自原文 空间索引 - GeoHash算法及其实现优化

 

上篇博客中提到了空间索引的用途和多种数据库对空间索引的支持情况,那么在应用层以下,好学的小伙伴应该会考虑空间索引的实现原理了。

目前空间索引的实现有 R树和其变种GIST树、四叉树、网格索引等。 网格索引不再多提,使用普通的hash表存储地点和风格之间的映射来实现。今天要介绍的GeoHash算法实现的空间索引,虽然是以B树实现,但我认为它也借用网格索引的一部分思想。

GeoHash

原理

GeoHash 算法的原理说起来是很简单的,如下图:

  1. 从横向上将整个方形纸分为左右两份,左侧部分为标记为 0, 右侧部分标记为 1
  2. 再将红点所在的部分划分为左右两块,再对红点位置做同样的标识,最后得出红点在横向上的标识为 10;
  3. 在纵向上对方形纸做同样的划分,左侧标识为0,右侧标识为 1,得出红点位置在纵向上的标识为 01;
  4. 将横向标识和纵向标识合并,规则为 纵向在奇数位,横向在偶数位 (也可纵横相反,但要在整个系统内保持一致),得出红点在方形纸上的标识为 1001;

只标记一个方格显得看不出什么规律,如果我们把这些都空格都标识后会发现 被划分在角落里的四个方格会有同样的前缀,如下图所示。

 

同样的前缀意味着可以使用 B树 索引查找有相同前缀的点作为附近的点,GeoHash 算法便是这些同样的前缀上面做文章。

墨卡托投影

墨卡托投影,是正轴等角圆柱投影。由荷兰地图学家墨卡托(G.Mercator)于1569年创立。假想一个与地轴方向一致的圆柱切或割于地球,按等角条件,将经纬网投影到圆柱面上,将圆柱面展为平面后,即得本投影。墨卡托投影在切圆柱投影与割圆柱投影中,最早也是最常用的是切圆柱投影。

墨卡托投影简单地说,就是可以 把整个地球平面作为一个正方形来处理,当然地球平面不是严格的正方形,此投影在两极附近的点会有误差,本文专注于原理,纠偏就不多提了(我也不懂,逃)。

实现

按照墨卡托投影的平面,我们可以按照上面划分方格纸的方式来将整个地球表面划分为各个小方格。

如(116.276349, 40.040875)这个点的经度划分:

  1. 经度在 [-180,0) 范围内的标识为0,经度范围在 [0, 180) 度的标识为 1;
  2. 继续划分,经度范围在 [0,90) 的标识为 0,经度范围在 [90,180) 的标识为 1;
  3. 这样,我们划分 20 次,方格的精度(见文末对照表)已达到 2m,得到经度的标识二进制串为11010010101011110111;
  4. 对纬度同样划分,得到纬度的标识二进制串为10111000111100100111;
  5. 我们对它组合,得到40位的二进制串11011 01110 00010 01110 11100 10111 01001 11111;
  6. 我们将这个二进制串使用 base32编码(原理同base64,可以见我的另一篇文章:WEB开发中的字符集和编码,位编码映射表见下),得到 GeoHash 编码为 3OCO4XJ7;

那么GeoHash编码前缀为 3OCO4XJ7的地理点就是离 (116.276349, 40.040875)两米内的点。如果我们把地理位置点和其GeoHash编码存入数据库的话,我们要查找 附近两米点的点,只需要限定条件 geo_code like '3OCO4XJ7%'就行了;

边界点问题

可是最简版的 GeoHash 还有一个弱点,如下图:

如果每个方格的精度为 2km,那么我们直接按照前缀查询红点附近 2km 的点是查找不到离它很近的黑点的。

要解决这个问题,我们就需要所其周边八个方格也考虑上,将自身方格和周边八个方格内的点都遍历一次,再返回符合要求的点。那么如何知道周边方格的前缀呢?

仔细观察相邻方格,我们会发现两个小方格会在 经度或纬度的二进制码上相差1;我们通过 GeoHash 码反向解析出二进制码后,将其经度或纬度(或两者)的二进制码加一,再次组合为 GeoHash 码。


Redis的GEO函数

问题

我们常见的需求是查找 n米 范围内的点,那么 n米 与 GeoHash 码位数之间的映射如何实现呢?由于 GeoHash 码是由5位二进制码组成,每少一位,精度就会损失 2e(5/2)

方法当然有的,我们将二进制GeoHash码直接索引就可以,但很长的索引长度会导致 B树 索引查询效率会迅速下降。

方案

于是我们接着寻找解决方案,既然使用 base32 转换为 32进制码 会不好控制精度,保持二进制又导致索引长度过长,那么进制位数和索引长度有没有一个平衡呢?

另外 Redis 的 sorted set 支持 64位 的 double 类型的 score,我们把二进制的 GeoHash 码转为十进制放入 Redis 的 sorted set 中,不是可以实现 log(n)的查询效率了么。

说实话第一次看到 Redis 的 GEO 系列函数的时候我的内心是崩溃的,原来自己感觉极其良好的设计早已被人实现了(虽然这种情况经常出现)。。。

当然不能就这么算了,于是我使用PHP造了一遍轮子。。。

主要步骤如下:


代码实现

实现中我将 GeoHash 的最大精度设置为26位,此时它的距离精度为 0.3m。当然我们也可以充分利用 Redis 的 sorted set 的 score,设置精度为 32 位,刚好使用它的 double 类型。

放上GitHub源码地址:空间索引-GeoHash

数据入库:

将经纬度通过 GeoHash 算法获取到二进制 GeoHash 码,并将其转成十进制作为这个点的 score 存入 Redis 的 sorted set;

// GeoHash核心方法 传入float类型的度数和其对应的范围,经度和纬度公用方法
public function getBits($loc, $range, $level = self::LEVEL_MAX) {
    $bits = '';
    for ($i = 0; $i < $level; $i++) {
        $mid = ($range['min'] + $range['max']) / 2;
        if ($loc < $mid) {
            $bits .= '0';
            $range = ['min' => $range['min'], 'max' => $mid];
        } else {
            $bits .= '1';
            $range = ['min' => $mid, 'max' => $range['max']];
        }
    }

    return $bits;
}     

另外 php 的 bindec($bin_str) 方法能快速把二进制字符串转为十进制数字。

根据查询范围半径获取精度

上文说过,精度是由地图的划分次数决定的,划分次数多了,范围就小了,查询的出的数据就不全;划分次数少了,范围就会大了,我们对数据过滤时就会有过多的损耗。

private function getLevel($range_meter){
    $level = 0;
    $global = self::MERCATOR_LENGTH;
    while ($global > $range_meter) {
        $global /= 2;
        $level++;
    }

    return $level;
}   

上面代码的思想来自redis geo函数源码,真的很巧妙。

在墨卡托投影下,地球的表面可以作为一个正方形来看,它的边是地球周长中最长的一个。而学过初中地理的我们知道:“地球是一个两极稍扁,赤道略鼓的球体”,那么它最长的一个周长就是赤道周长了,于是我们得知墨卡托投影的长边为 2*PI*R=40075452.74M;

于是我们拿正方形的一个边来不停地进行二次划分,直到划分后的结果刚好比范围半径长,那么它构成的一个方块,便是我们需要的方格。

数据查询

数据查询时,我们需要获取中间方块的最小 score 值和其范围,最小 score 值很简单,直接将二进制位不足52位的在后面补0

此外,为了避免边界点问题,我们还需要把周围八个方格的 score 值范围也获取到。

我们在划分地图时,每多划分一次,会添加经度和纬度两个二进制位,在精度最高时,那么每一个方格的最大值和最小值之间差1。由此,我们通过下面的方法获取到一个方格的最大和最小 score 值之差。

private function getLevelRange($level) {
    $range = pow(2, 2 * (self::LEVEL_MAX - $level));

    return $range;
}

再由上面提过的边界点问题的解决方案,获取到周边八个方格的最小 score 值。

使用 Redis 的ZRANGEBYSCORE key hashInt hashInt+range命令将这九个方格内的点全部取到,再遍历九个方格,将距离不符合的数据过滤掉。


小结

花费了十多个小时,总算将 GeoHash 完全整体了一遍,完全理解 GeoHash 并没有想像中的那么简单。除了 GeoHash,四叉树和R树据说查询效率会更高,有时间再研究一下。

如果您觉得本文对您有帮助,可以点击下面的 推荐 支持一下我。博客一直在更新,欢迎 关注 。

参考:

GeoHash核心原理解析

Redis GEO 源码注释

GeoHash位数精度对照表(wiki百科):

GeoHash length lat bits lng bits lat error lng error km error
1 2 3 ±23 ±23 ±2500
2 5 5 ±2.8 ±5.6 ±630
3 7 8 ±0.70 ±0.70 ±78
4 10 10 ±0.087 ±0.18 ±20
5 12 13 ±0.022 ±0.022 ±2.4
6 15 15 ±0.0027 ±0.0055 ±0.61
7 17 18 ±0.00068 ±0.00068 ±0.076
8 20 20 ±0.000085 ±0.00017 ±0.019

base32 编码映射表:

Value Symbol Value Symbol Value Symbol Value Symbol
0 A 9 J 18 S 27 3
1 B 10 K 19 T 28 4
2 C 11 L 20 U 29 5
3 D 12 M 21 V 30 6
4 E 13 N 22 W 31 7
5 F 14 O 23 X    
6 G 15 P 24 Y    
7 H 16 Q 25 Z    
8 I 17 R 26 2  

 

 

没有整理与归纳的知识,一文不值!高度概括与梳理的知识,才是自己真正的知识与技能。 永远不要让自己的自由、好奇、充满创造力的想法被现实的框架所束缚,让创造力自由成长吧! 多花时间,关心他(她)人,正如别人所关心你的。理想的腾飞与实现,没有别人的支持与帮助,是万万不能的。


    本文转自wenglabs博客园博客,原文链接:http://www.cnblogs.com/arxive/p/8138245.html,如需转载请自行联系原作者





相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore &nbsp; &nbsp; ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库&nbsp;ECS 实例和一台目标数据库&nbsp;RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&amp;RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
相关文章
|
10天前
|
算法
基于GA遗传算法的PID控制器参数优化matlab建模与仿真
本项目基于遗传算法(GA)优化PID控制器参数,通过空间状态方程构建控制对象,自定义GA的选择、交叉、变异过程,以提高PID控制性能。与使用通用GA工具箱相比,此方法更灵活、针对性强。MATLAB2022A环境下测试,展示了GA优化前后PID控制效果的显著差异。核心代码实现了遗传算法的迭代优化过程,最终通过适应度函数评估并选择了最优PID参数,显著提升了系统响应速度和稳定性。
|
7天前
|
算法
基于WOA鲸鱼优化的购售电收益与风险评估算法matlab仿真
本研究提出了一种基于鲸鱼优化算法(WOA)的购售电收益与风险评估算法。通过将售电公司购售电收益风险计算公式作为WOA的目标函数,经过迭代优化计算出最优购电策略。实验结果表明,在迭代次数超过10次后,风险价值收益优化值达到1715.1万元的最大值。WOA还确定了中长期市场、现货市场及可再生能源等不同市场的最优购电量,验证了算法的有效性。核心程序使用MATLAB2022a实现,通过多次迭代优化,实现了售电公司收益最大化和风险最小化的目标。
|
11天前
|
算法
通过matlab分别对比PSO,反向学习PSO,多策略改进反向学习PSO三种优化算法
本项目使用MATLAB2022A版本,对比分析了PSO、反向学习PSO及多策略改进反向学习PSO三种优化算法的性能,主要通过优化收敛曲线进行直观展示。核心代码实现了标准PSO算法流程,加入反向学习机制及多种改进策略,以提升算法跳出局部最优的能力,增强全局搜索效率。
|
7天前
|
算法
通过matlab对比遗传算法优化前后染色体的变化情况
该程序使用MATLAB2022A实现遗传算法优化染色体的过程,通过迭代选择、交叉和变异操作,提高染色体适应度,优化解的质量,同时保持种群多样性,避免局部最优。代码展示了算法的核心流程,包括适应度计算、选择、交叉、变异等步骤,并通过图表直观展示了优化前后染色体的变化情况。
|
11天前
|
算法
基于大爆炸优化算法的PID控制器参数寻优matlab仿真
本研究基于大爆炸优化算法对PID控制器参数进行寻优,并通过Matlab仿真对比优化前后PID控制效果。使用MATLAB2022a实现核心程序,展示了算法迭代过程及最优PID参数的求解。大爆炸优化算法通过模拟宇宙大爆炸和大收缩过程,在搜索空间中迭代寻找全局最优解,特别适用于PID参数优化,提升控制系统性能。
|
11天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于贝叶斯优化CNN-GRU网络的数据分类识别算法matlab仿真
本项目展示了使用MATLAB2022a实现的贝叶斯优化、CNN和GRU算法优化效果。优化前后对比显著,完整代码附带中文注释及操作视频。贝叶斯优化适用于黑盒函数,CNN用于时间序列特征提取,GRU改进了RNN的长序列处理能力。
|
9天前
|
算法 决策智能
基于遗传优化算法的TSP问题求解matlab仿真
本项目使用遗传算法解决旅行商问题(TSP),目标是在四个城市间找到最短路径。算法通过编码、选择、交叉、变异等步骤,在MATLAB2022A上实现路径优化,最终输出最优路径及距离。
|
8天前
|
算法
基于WOA算法的SVDD参数寻优matlab仿真
该程序利用鲸鱼优化算法(WOA)对支持向量数据描述(SVDD)模型的参数进行优化,以提高数据分类的准确性。通过MATLAB2022A实现,展示了不同信噪比(SNR)下模型的分类误差。WOA通过模拟鲸鱼捕食行为,动态调整SVDD参数,如惩罚因子C和核函数参数γ,以寻找最优参数组合,增强模型的鲁棒性和泛化能力。
|
14天前
|
机器学习/深度学习 算法 Serverless
基于WOA-SVM的乳腺癌数据分类识别算法matlab仿真,对比BP神经网络和SVM
本项目利用鲸鱼优化算法(WOA)优化支持向量机(SVM)参数,针对乳腺癌早期诊断问题,通过MATLAB 2022a实现。核心代码包括参数初始化、目标函数计算、位置更新等步骤,并附有详细中文注释及操作视频。实验结果显示,WOA-SVM在提高分类精度和泛化能力方面表现出色,为乳腺癌的早期诊断提供了有效的技术支持。
|
2天前
|
存储 算法
基于HMM隐马尔可夫模型的金融数据预测算法matlab仿真
本项目基于HMM模型实现金融数据预测,包括模型训练与预测两部分。在MATLAB2022A上运行,通过计算状态转移和观测概率预测未来值,并绘制了预测值、真实值及预测误差的对比图。HMM模型适用于金融市场的时间序列分析,能够有效捕捉隐藏状态及其转换规律,为金融预测提供有力工具。