`

通过GeoHash核心原理来分析hbase rowkey设计

 
阅读更多
   注:本文是结合hbase实战以及网上的博文概述了一下,以作后期使用时的备份。
   参考资料:http://www.cnblogs.com/LBSer/p/3310455.html


   百度地图,美团,大众点评等等等等,都会有查找附近的功能,如何实现呢?计算所在位置P与北京所有餐馆的距离,然后返回距离<=1000米的餐馆。餐馆何其多啊,这样计算不得了,既然知道经纬度了,那它应该知道自己在西城区,那应该计算所在位置P与西城区所有餐馆的距离啊,机机运用了递归的思想,想到了西城区也很多餐馆啊,应该计算所在位置P与所在街道所有餐馆的距离,这样计算量又小了,效率也提升了。通过过滤的方法来减小参与计算的餐馆数目,从某种角度上讲,就是索引技术。

     首先我们先来看一下上一篇文章中使用到的复合rowkey在空间索引中为什么不适合。首先每个点都有一个X点和Y点,我们先按经度在按维度来组合一个行健然后将各个点连接起来是什么效果:如下


     我们可以看到1到9之间的排序,因为先按经度在按维度,所以会出现这种南北位置跳跃存储的情况。所以说空间位置不一定就是hbase的存储位置,在存储空间字段时候我们要同时考虑经度和维度,因为它们同等重要
      GeoHash将二维的经纬度转换成字符串,比如下图展示了北京9个区域的GeoHash字符串,分别是WX4ER,WX4G2、WX4G3等等,每一个字符串代表了某一矩形区域。也就是说,这个矩形区域内所有的点(经纬度坐标)都共享相同的GeoHash字符串,这样既可以保护隐私(只表示大概区域位置而不是具体的点),又比较容易做缓存,比如左上角这个区域内的用户不断发送位置信息请求餐馆数据,由于这些用户的GeoHash字符串都是WX4ER,所以可以把WX4ER当作key,把该区域的餐馆信息当作value来进行缓存,而如果不使用GeoHash的话,由于区域内的用户传来的经纬度是各不相同的,很难做缓存。
     

字符串越长,表示的范围越精确。如图所示,5位的编码能表示10平方千米范围的矩形区域,而6位编码能表示更精细的区域(约0.34平方千米)


字符串相似的表示距离相近(特殊情况后文阐述),这样可以利用字符串的前缀匹配来查询附近的POI信息。如下两个图所示,一个在城区,一个在郊区,城区的GeoHash字符串之间比较相似,郊区的字符串之间也比较相似,而城区和郊区的GeoHash字符串相似程度要低些。


通过上面的介绍我们知道了GeoHash就是一种将经纬度转换成字符串的方法,并且使得在大部分情况下,字符串前缀匹配越多的距离越近,回到我们的案例,根据所在位置查询来查询附近餐馆时,只需要将所在位置经纬度转换成GeoHash字符串,并与各个餐馆的GeoHash字符串进行前缀匹配,匹配越多的距离越近。

下面以北海公园为例介绍GeoHash算法的计算步骤
根据经纬度计算GeoHash二进制编码

地球纬度区间是[-90,90], 北海公园的纬度是39.928167,可以通过下面算法对纬度39.928167进行逼近编码:

1)区间[-90,90]进行二分为[-90,0),[0,90],称为左右区间,可以确定39.928167属于右区间[0,90],给标记为1;

2)接着将区间[0,90]进行二分为 [0,45),[45,90],可以确定39.928167属于左区间 [0,45),给标记为0;

3)递归上述过程39.928167总是属于某个区间[a,b]。随着每次迭代区间[a,b]总在缩小,并越来越逼近39.928167;

4)如果给定的纬度x(39.928167)属于左区间,则记录0,如果属于右区间则记录1,这样随着算法的进行会产生一个序列1011100,序列的长度跟给定的区间划分次数有关。

根据纬度算编码
bitminmidmax
1 -90.000 0.000 90.000
0 0.000 45.000 90.000
1 0.000 22.500 45.000
1 22.500 33.750 45.000
1 33.7500 39.375 45.000
0 39.375 42.188 45.000
0 39.375 40.7815 42.188
0 39.375 40.07825 40.7815
1 39.375 39.726625 40.07825
1 39.726625 39.9024375 40.07825
    

同理,地球经度区间是[-180,180],可以对经度116.389550进行编码。

根据经度算编码
bit min mid max
1 -180 0.000 180
1 0.000 90 180
0 90 135 180
1 90 112.5 135
0 112.5 123.75 135
0 112.5 118.125 123.75
1 112.5 115.3125 118.125
0 115.3125 116.71875 118.125
1 115.3125 116.015625 116.71875
1 116.015625 116.3671875116.71875


通过上述计算,纬度产生的编码为10111 00011,经度产生的编码为11010 01011。偶数位放经度,奇数位放纬度,把2串编码组合生成新串:11100 11101 00100 01111。

最后使用用0-9、b-z(去掉a, i, l, o)这32个字母进行base32编码,首先将11100 11101 00100 01111转成十进制,对应着28、29、4、15,十进制对应的编码就是wx4g。同理,将编码转换成经纬度的解码算法与之相反,具体不再赘述。

可以看出,当geohash base32编码长度为8时,精度在19米左右,而当编码长度为9时,精度在2米左右,编码长度需要根据数据情况进行选择。


上文讲了GeoHash的计算步骤,仅仅说明是什么而没有说明为什么?为什么分别给经度和维度编码?为什么需要将经纬度两串编码交叉组合成一串编码?本节试图回答这一问题。

如图所示,我们将二进制编码的结果填写到空间中,当将空间划分为四块时候,编码的顺序分别是左下角00,左上角01,右下脚10,右上角11,也就是类似于Z的曲线,当我们递归的将各个块分解成更小的子块时,编码的顺序是自相似的(分形),每一个子快也形成Z曲线,这种类型的曲线被称为Peano空间填充曲线。

这种类型的空间填充曲线的优点是将二维空间转换成一维曲线(事实上是分形维),对大部分而言,编码相似的距离也相近, 但Peano空间填充曲线最大的缺点就是突变性,有些编码相邻但距离却相差很远,比如0111与1000,编码是相邻的,但距离相差很大。



由于GeoHash是将区域划分为一个个规则矩形,并对每个矩形进行编码,这样在查询附近POI信息时会导致以下问题,比如红色的点是我们的位置,绿色的两个点分别是附近的两个餐馆,但是在查询的时候会发现距离较远餐馆的GeoHash编码与我们一样(因为在同一个GeoHash区域块上),而较近餐馆的GeoHash编码与我们不一致。这个问题往往产生在边界处。



解决的思路很简单,我们查询时,除了使用定位点的GeoHash编码进行匹配外,还使用周围8个区域的GeoHash编码,这样可以避免这个问题。

2)我们已经知道现有的GeoHash算法使用的是Peano空间填充曲线,这种曲线会产生突变,造成了编码虽然相似但距离可能相差很大的问题,因此在查询附近餐馆时候,首先筛选GeoHash编码相似的POI点,然后进行实际距离计算。
  • 大小: 93.1 KB
  • 大小: 116.3 KB
  • 大小: 92.2 KB
  • 大小: 219.8 KB
  • 大小: 37 KB
  • 大小: 27.8 KB
  • 大小: 92.3 KB
分享到:
评论

相关推荐

    阿里面试问题总结.pdf

    41. **HBase RowKey设计**:设计合理的RowKey可实现数据均匀分布,减少热点。 42. **TCP三次握手与四次挥手**:描述ACK、FIN、序号的作用及状态转换。 43. **垃圾收集**:理解不同GC算法,如Minor GC、Major GC、...

    阿里面试问题总结.docx

    #### HBase rowkey设计 - **主要内容**:为了使数据均匀分布,需合理设计rowkey,考虑数据访问模式和分布策略。 - **考察点**:NoSQL数据库基础知识、HBase使用经验。 #### 分布式知识 - **主要内容**:包括但不...

    Dify智能体:JSON 修复.yml

    Dify智能体:JSON 修复.yml

    陕西省2025年初中学业水平考试实验操作考试试题及评分细则.zip

    陕西省2025年初中学业水平考试实验操作考试试题及评分细则.zip

    西门子S7-1200 PLC污水处理系统:博途V17版KTp1200屏程序设计与优化

    内容概要:本文详细介绍了西门子S7-1200 PLC在污水处理项目中的应用,涵盖模拟量处理、设备轮换、Modbus通讯以及事件记录等多个方面。文中展示了如何利用博途V17进行程序设计,包括具体的SCL代码实例,如液位检测的滑动窗口滤波法、提升泵的轮换逻辑、Modbus TCP对变频器的控制以及报警信息管理等。此外,还分享了一些实用技巧,如防止信号跳变、避免设备过度磨损、确保通讯稳定性和提高报警记录效率的方法。 适合人群:从事工业自动化领域的工程师和技术人员,尤其是熟悉西门子PLC和博途软件的从业者。 使用场景及目标:适用于污水处理项目的PLC编程和系统集成,旨在提高系统的稳定性和可靠性,减少维护成本并优化设备性能。 其他说明:文中不仅提供了详细的代码示例,还分享了许多来自实际项目的经验教训,帮助读者更好地理解和应用相关技术。

    基于PLC的自动药片装瓶机控制系统设计与仿真

    内容概要:本文详细介绍了基于PLC(西门子S7-1200)的自动药片装瓶机控制系统的设计与仿真过程。涵盖了硬件选型(伺服电机、光电传感器)、软件编程(梯形图、结构化文本)、关键算法(传送带定位、振动盘控制、药片计数)、异常处理以及仿真测试等方面的内容。重点讨论了如何通过精确的硬件配置和优化的控制逻辑来确保系统的稳定性和高效性。 适合人群:从事工业自动化领域的工程师和技术人员,尤其是对PLC编程和机电一体化感兴趣的读者。 使用场景及目标:适用于制药行业及其他需要自动化包装设备的企业。主要目标是提高生产效率、减少人工干预、提升产品质量和稳定性。 其他说明:文中提供了大量实际案例和调试经验,帮助读者更好地理解和应用相关技术和方法。同时强调了仿真测试的重要性,为后续的实际部署提供了宝贵的经验和改进建议。

    基于元启发式算法优化四级倒立摆系统的LQR控制器设计与应用

    内容概要:本文介绍了一种利用元启发式算法(如粒子群优化,PSO)优化线性二次调节器(LQR)控制器加权矩阵的方法,专门针对复杂的四级倒立摆系统。传统的LQR控制器设计中,加权矩阵Q的选择往往依赖于经验和试错,而这种方法难以应对高维度非线性系统的复杂性。文中详细描述了如何将控制器参数优化问题转化为多维空间搜索问题,并通过MATLAB代码展示了具体实施步骤。关键点包括:构建非线性系统的动力学模型、设计适应度函数、采用对数缩放技术避免局部最优、以及通过实验验证优化效果。结果显示,相比传统方法,PSO优化后的LQR控制器不仅提高了稳定性,还显著减少了最大控制力,同时缩短了稳定时间。 适合人群:控制系统研究人员、自动化工程专业学生、从事机器人控制或高级控制算法开发的技术人员。 使用场景及目标:适用于需要精确控制高度动态和不确定性的机械系统,特别是在处理多自由度、强耦合特性的情况下。目标是通过引入智能化的参数寻优手段,改善现有控制策略的效果,降低人为干预的需求,提高系统的鲁棒性和性能。 其他说明:文章强调了在实际应用中应注意的问题,如避免过拟合、考虑硬件限制等,并提出了未来研究方向,例如探索非对角Q矩阵的可能性。此外,还分享了一些实践经验,如如何处理高频抖动现象,以及如何结合不同类型的元启发式算法以获得更好的优化结果。

    LLC谐振变换器设计与仿真的关键技术解析及实战工具应用

    内容概要:本文详细介绍了LLC谐振变换器的设计方法及其仿真模型的应用。首先,通过参数设计程序,如Excel表格和Matlab脚本,进行关键参数的计算,确保设计符合预期性能。其次,利用Matlab/Simulink构建闭环控制仿真模型,优化PID控制器和PWM生成模块,提高系统的稳定性和响应速度。最后,提供了详细的模态分析和波形解读,帮助理解和规避常见设计陷阱。文中强调了参数选择的重要性,如电感比k值、死区时间和谐振元件的实际测量值,并分享了多个实战经验和调试技巧。 适合人群:从事电力电子设计的技术人员,尤其是对LLC谐振变换器感兴趣的工程师。 使用场景及目标:适用于需要高效、稳定的电源转换解决方案的研发项目。主要目标是掌握LLC谐振变换器的设计原理和技术要点,能够独立完成从参数计算到闭环调试的全过程。 其他说明:文中提供的工具和方法不仅有助于初学者快速入门,也能为有经验的工程师提供宝贵的参考资料。特别提到了一些容易忽视的细节和常见的错误,帮助读者避免不必要的损失。

    深度强化学习在电力系统中的应用:多智能体自主电压控制框架的Python实现

    内容概要:本文探讨了利用深度强化学习(DRL)解决现代电网复杂控制问题的方法,特别是针对自主电压控制(AVC)的应用。文中介绍了多智能体系统(MAS)与深度确定性策略梯度(MADDPG)相结合的MA-AVC算法,展示了如何将电网划分为多个子区域,每个子区域由一个智能体负责,通过集中训练和分散执行的方式进行电压控制。文章详细解释了智能体网络的设计、训练过程、奖励机制以及在伊利诺伊200总线系统上的实验验证。结果显示,相比传统方法,该算法在处理负荷突变、N-1故障和通信延迟等方面表现出显著优势。 适合人群:对深度强化学习、电力系统自动化感兴趣的科研人员和技术开发者,尤其是希望了解如何将AI应用于实际工业场景的研究者。 使用场景及目标:适用于需要提高电网稳定性和响应速度的实际应用场景,特别是在可再生能源接入和快速需求响应的要求下。目标是通过智能化手段提升电网的自适应能力和鲁棒性。 其他说明:文章提供了详细的代码示例和实验结果,帮助读者理解和复现相关算法。特别强调了奖励函数设计和电网仿真的重要性,指出了一些常见的实现陷阱及其解决方案。

    MIMO通信系统中空间编码、系统容量与信道仿真的Matlab实现

    内容概要:本文详细介绍了MIMO通信系统的三个重要方面:空间编码、系统容量计算以及信道特性仿真。首先探讨了Alamouti空时编码的具体实现方法及其在接收端的解码过程,展示了如何通过共轭转置排列实现分集增益。其次,深入讲解了MIMO系统容量公式的推导及其在Matlab中的高效实现,特别强调了使用奇异值分解提高数值稳定性的技巧。最后,讨论了信道矩阵的条件数对系统性能的影响,并提出了应对病态信道的方法如MMSE检测。 适合人群:具备一定通信理论基础和技术背景的研究人员、工程师及高校学生。 使用场景及目标:适用于希望深入了解MIMO通信系统内部机制的人群,帮助他们掌握空间编码、系统容量计算和信道建模的实际应用技能,为后续研究提供理论支持和技术储备。 其他说明:文中提供了大量实用的Matlab代码片段,便于读者快速理解和实践。同时提醒读者注意实际工程中可能遇到的问题,如数值稳定性、信道相关性和噪声增强等。

    【工业自动化】西门子PLC与测量光栅Modbus通讯实现:硬件配置、软件调试及参数设置详解文档的主要内容

    内容概要:本文档详细介绍了西门子PLC与意普测量光栅通过Modbus RTU协议进行通信的方法。硬件方面,使用了1214DC/DC/DC PLC、CB1214通讯板、ESM4810NQ-2测量光栅以及USB转485串口线缆等设备。软件部分采用博图V18进行编程,并利用调试助手modbuSCAN和sscom来辅助配置与测试。文中具体描述了创建MASTER_COMM_LOAD指令、添加MB_MASTER主站指令及轮询程序编写的步骤,包括详细的报文格式解析如站号、功能码、寄存器地址、内容及CRC校验码等信息。此外,还提供了针对光栅的初始化、波特率、奇偶校验和停止位等参数配置示例及其对应的报文解释。; 适合人群:熟悉PLC编程并希望深入了解Modbus通讯协议的应用工程师和技术人员。; 使用场景及目标:①实现PLC作为主站与测量光栅之间的稳定通信;②掌握Modbus RTU协议的具体应用细节,包括报文结构的理解与配置;③解决实际项目中可能遇到的通信问题,如线路连接、参数设置等。; 阅读建议:建议读者在阅读时结合实际硬件设备进行操作练习,同时注意文中提到的一些常见问题及其解决方案,如线序连接错误导致的乱码现象等。

    工业通信基于Qt的Modbus协议开发详解:涵盖协议原理、开发流程及应用案例

    内容概要:本文详细介绍了基于Qt的Modbus协议开发,涵盖协议原理、Qt框架支持、开发流程、代码示例及常见问题解决方案。Modbus协议支持串行通信(RTU/ASCII)和以太网(TCP/IP)两种传输方式,具有功能码定义、数据模型和通信模式等核心功能。Qt通过Qt Serial Bus模块提供对Modbus的支持,主要类有QModbusDevice、QModbusClient(含QModbusTcpClient和QModbusRtuSerialMaster)、QModbusDataUnit和QModbusReply。开发环境配置需在Qt项目的.pro文件中添加相应模块,并准备硬件设备。文中给出了Modbus客户端(TCP)的连接、读取和写入寄存器的代码示例,以及Modbus服务器的实现步骤。还列举了常见的问题与调试技巧,包括通讯不稳定、数据异常和性能优化的方法。最后介绍了该技术在工业自动化、能源管理和智能家居的应用场景。; 适合人群:具备一定Qt编程基础,对工业通信协议感兴趣的开发者。; 使用场景及目标:①学习Modbus协议的基本原理及其在Qt中的实现方法;②掌握Qt Modbus框架的核心类及其用法;③能够独立开发Modbus客户端和服务器程序,解决常见问题。; 阅读建议:本文内容详实,涉及多个知识点和技术细节,在阅读过程中应结合实际开发环境进行实践操作,以便更好地理解和掌握相关技术。

    2021 SEO新手入门:掌握谷歌优化策略

    本书《SEO for Beginners 2021》旨在向读者介绍如何使用搜索引擎优化(SEO)技术,在谷歌上提升网站排名,吸引新客户,从而实现业务增长。作者加里·戈丁和阿伦·肯尼迪通过实例和策略指导,帮助读者了解SEO的基础知识,包括关键词研究、网站设置、链接构建、社交媒体SEO优化以及如何使用谷歌分析工具来监控SEO效果。书中还特别强调了SEO在商业世界中的重要性,并提供了在谷歌广告平台上进行有效广告投放的技巧和策略。此外,作者还分享了如何通过解决SEO常见问题、设置广告账户、撰写广告文案、创建着陆页以及监控转化率等方法,进一步优化搜索引擎营销效果。

    基于Logistic映射的混沌系统图像加密算法:循环移位扰乱与扩散技术的应用

    内容概要:本文详细介绍了利用混沌系统进行图像加密的方法,重点探讨了Logistic映射生成混沌序列用于图像加密的具体实现。首先,通过Python代码生成混沌序列,确保其随机性和不可预测性。然后,采用循环移位扰乱技术对图像像素进行重新排列,使图像的像素位置发生改变。接着,通过水平和垂直扩散技术进一步打乱像素之间的关联性,增加加密强度。文中还展示了加密效果评估方法,如直方图分析、信息熵计算以及相关系数测量,验证了加密算法的有效性。 适合人群:对图像加密技术和混沌系统感兴趣的科研人员、信息安全专家及有一定编程基础的研究者。 使用场景及目标:适用于需要高强度图像加密保护的场合,如军事、医疗等领域的重要图像资料保护。目标是提供一种高效、安全的图像加密解决方案。 其他说明:文中提供了详细的Python代码示例,便于读者理解和实践。同时强调了实际应用中需要注意的问题,如参数选择和性能优化等。

    FLAC3D中双线隧道与临近基坑开挖的数值模拟及关键技术实现

    内容概要:本文详细介绍了利用FLAC3D软件进行双线隧道开挖和临近既有隧道的基坑开挖的数值模拟方法和技术要点。首先,针对隧道开挖部分,采用反力支撑法控制应力释放,并使用shell壳单元模拟喷射混凝土支护结构。其次,在基坑开挖过程中,采用了地连墙加对撑的方式,分层开挖并及时安装水平对撑。文中还提供了多个关键代码片段,展示了具体的实现步骤。此外,文章强调了监测点数据采集和处理的重要性,以及如何通过调整接触面参数解决潜在问题。最后,作者分享了一些实用技巧,如固定云图色标范围、正确设置接触面摩擦系数等。 适合人群:从事地下工程、岩土工程及相关领域的研究人员和工程师。 使用场景及目标:适用于需要进行复杂地质条件下隧道和基坑开挖数值模拟的研究人员和工程师,旨在帮助他们更好地理解和掌握FLAC3D软件的应用,提高模拟精度和效率。 其他说明:文章不仅提供了详细的代码示例,还结合实际案例进行了深入分析,有助于读者将理论知识应用于实际工程项目中。

    Android多数据类型传输(数据的交互)

    实现多数据类型的传输

    《2024年中国物联网产业创新白皮书》

    内容概要:《2024年中国物联网产业创新白皮书》由深圳市物联网产业协会与AIoT星图研究院联合编制,汇集了全国30多个省市物联网组织的智慧。白皮书系统梳理了中国物联网产业的发展历程、现状及未来趋势,涵盖了物联网的概念、产业结构、市场规模、投融资情况、面临的问题与机遇。书中详细分析了感知层、传输层、平台层及应用层的关键技术,探讨了智慧城市、智能工业、车联网、智慧医疗等九大产业物联网应用领域,以及消费物联网的发展特征与热门单品。此外,白皮书还关注了物联网数据安全、法规遵从、人才短缺等挑战,并提出了相应的解决方案。 适用人群:物联网从业者、企业决策者、政策制定者及相关研究机构。 使用场景及目标:①帮助从业者深入了解物联网产业的现状和发展趋势;②为企业决策者提供战略规划依据;③为政策制定者提供政策支持和法规制定参考;④为研究机构提供详尽的数据和案例支持。 其他说明:白皮书不仅限于技术科普,更从宏观角度结合市场情况,多维度讨论了物联网产业生态,旨在为物联网企业、从业者找到最适合的技术应用场景,促进产业健康发展。报告还特别鸣谢了参与市场调研的企业,感谢他们提供的宝贵行业信息。由于时间和资源的限制,报告可能存在信息不充分之处,欢迎各界人士提出宝贵意见。

    车辆动力学中质心侧偏角-横摆角速度相平面法的Simulink实现与应用

    内容概要:本文介绍了如何利用Simulink实现‘质心侧偏角-横摆角速度’相平面法,用于分析车辆的动力学行为。作者详细描述了模型的构建过程,包括输入模块、车辆动力学模型以及相平面生成模块的设计。通过调整车辆速度、路面附着系数和前轮转角等参数,可以直观地观察到车辆稳定性的变化。此外,文中还提供了详细的代码示例和结果分析,帮助读者更好地理解和应用这一方法。 适合人群:对车辆动力学感兴趣的工程师和技术人员,特别是那些希望通过Simulink进行车辆稳定性分析的人。 使用场景及目标:适用于需要评估车辆在不同行驶条件下稳定性的场合,如汽车制造商的研发部门、交通安全研究机构等。目标是通过相平面法直观展示车辆动态响应,辅助优化车辆设计和改进驾驶安全性能。 其他说明:附带完整代码和Simulink模型文件,便于读者动手实践。同时,文中提到的一些调试技巧和常见问题解决方法也非常有价值。

    Minecraft PEB 1.21.90.20 v8a原版.apks

    Minecraft PEB 1.21.90.20 v8a原版.apks

    【Python毕设】p116基于Flask的酒类数据分析可视化系统.zip

    项目资源包含:可运行源码+sql文件+; mysql5.7+Flask+html+jieba+pandas+pillow+scikit-learn+wordcloud+matplotlib 适用人群:学习不同技术领域的小白或进阶学习者;可作为毕设项目、课程设计、大作业、工程实训或初期项目立项。 系统功能介绍: 数据可视化:品牌数据可视化、城市价格可视化、地址销量可视化、品牌付款可视化 词云图:商品、地址、商家词云图 价格预测:模型训练、参数调整、模型预测、线性回归预测 用户模块:用户登陆/注册、个人信息修改、添加日志 管理员模块:登陆、个人信息修改、用户管理、日志管理、价格预测、酒类数据维护

Global site tag (gtag.js) - Google Analytics