`

通过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
分享到:
评论

相关推荐

    hbase的Rowkey设计方案.pdf

    其核心特性之一便是通过Rowkey进行数据查询,因此Rowkey的设计对于HBase的读写性能至关重要。Rowkey不仅需要包含关键检索信息,还要兼顾查询方式和数据存储格式,以避免全表扫描导致的效率低下。 在HBase中,...

    rowkey设计案例.zip

    总的来说,这个案例展示了一个完整的流程:从Spark中处理数据,通过精心设计的RowKey算法确保数据在HBase中的均匀分布,以解决热点问题。同时,通过多进程多线程并行处理,提高了整个数据处理的效率。这样的实践对于...

    hbase的rowkey设计与hbase的协处理器运用.docx

    HBase RowKey 设计与协处理器运用 HBase 是一个基于 HDFS 的分布式、面向列的 NoSQL 数据库,具有高性能、可靠性和扩展性等特点。本文将详细介绍 HBase 的 RowKey 设计和协处理器运用。 HBase 的介绍 HBase 是一...

    大数据性能调优之HBase的RowKey设计.docx

    "大数据性能调优之HBase的RowKey设计" 大数据功能调优之HBase的RowKey设计是指在HBase中对RowKey的设计,以提高HBase的性能和可扩展性。RowKey是HBase中的一种二进制码流,可以是任意字符串,最大长度为64kb,但...

    HBase-RowKey与索引设计(高清)

    二级索引是通过在HBase中创建一个或多个额外的索引表来实现的,它可以用来优化对非RowKey字段的快速查询。组合索引则允许用户在一个索引表中索引多个字段的组合,以支持更复杂的查询需求。 在实际应用中,合理地...

    HBase分页查询的rowkey设计技巧

    用户历史订单列表查询rowkey设计技巧 最左前缀原则

    HBASE调优 rowkey

    更重要的是,合理设计rowkey,因为HBase是基于rowkey的字典顺序进行存储的。rowkey的设计应尽量短小,以减少存储空间的消耗和提高查询效率。 客户端调优涉及多个参数。例如,设置scanner缓存大小可以减少对服务器的...

    2-2+HBase-RowKey+与索引设计.zip

    本资料主要探讨了HBase中的RowKey(行键)设计以及如何利用它来实现高效的索引策略。下面我们将深入探讨这些关键概念。 **1. HBase的基本架构** HBase是基于Google Bigtable模型设计的,它将数据以表的形式存储,...

    hbase原理和设计

    ### HBase原理与设计 #### 一、HBase概述 HBase是一个开源的、高性能的分布式存储系统,基于Hadoop之上构建。它提供了一个高度可靠、面向列的存储方案,适用于处理大规模的数据集。HBase的设计特点包括: 1. **高...

    Hbase行键设计(rowkey)实现多条件查询

    在HBase中,行键(RowKey)的设计是至关重要的,因为它直接影响到数据的存取效率和查询性能。HBase是一种分布式、列式存储的NoSQL数据库,它以Key-Value的形式存储数据,并且主要依赖RowKey进行快速定位。由于HBase...

    HBase数据库设计.doc

    总的来说,HBase是一种面向大数据的列式存储系统,适用于需要实时查询和大规模扩展的场景,但其设计和使用需要对分布式存储有深入理解。在设计HBase数据库时,应充分考虑数据模型、行键策略以及集群的扩展性需求。

    bitcarmanlee#easy-algorithm-interview-and-practice#Hbase rowkey

    2)、RowKey散列原则:如果RowKey是按时间戳的方式递增,不要将时间放在二进制码的前面,建议将RowKey的高位作为散列字段,由程序循环生成,低位放时间

    非常使用的 基于geohash 找最近位置java代码

    非常使用的 基于geohash 找一定范围内的 最近位置java代码

    大数据书籍-Hbase架构设计(高清)

    书中详细阐述了Hbase的核心原理、生态环境以及在实际项目中的架构设计与性能优化策略,旨在帮助读者全面理解并掌握Hbase的运用。 Hbase作为Apache Hadoop生态系统的一部分,是一款开源的、非关系型的分布式数据库,...

    hbase 表设计

    HBase表设计通常围绕核心的查询模式,例如快速定位到特定的行,或在列族内快速扫描数据。HBase还提供了过滤器来优化查询,例如单列值过滤器、列前缀过滤器、分页过滤器等,这些过滤器可以在服务器端执行,从而减少了...

    HBase性能深度分析

    这一设计考虑到HBase对Rowkey的排序处理,随机Rowkey能够确保数据均匀分布于不同的region,充分发挥分布式数据库的优势。而Value的固定长度设置,则避免了数据变化对性能测试结果的影响。 #### 初次性能分析与集群...

Global site tag (gtag.js) - Google Analytics