注:本文是结合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,序列的长度跟给定的区间划分次数有关。
根据纬度算编码
同理,地球经度区间是[-180,180],可以对经度116.389550进行编码。
根据经度算编码
通过上述计算,纬度产生的编码为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点,然后进行实际距离计算。
参考资料: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,序列的长度跟给定的区间划分次数有关。
根据纬度算编码
bit | min | mid | max |
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.3671875 | 116.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点,然后进行实际距离计算。
发表评论
-
Sort-based Shuffle的设计与实现
2016-03-15 08:49 760原文 http://www.cnblogs.com/hsea ... -
spark的几个重要概念
2015-12-04 14:09 0本节主要记录以下几个概念 一:RDD的五大特点 二:RDD 窄 ... -
spark部署安装调试
2015-12-02 11:28 706本节记录spark下载-->编译-->安装--&g ... -
spark基本概念
2015-11-12 10:45 738记录一下课堂笔记: ... -
hadoop计算能力调度器配置
2015-10-29 10:39 970问题出现 hadoop默认调度器是FIFO,其原理就是先按照作 ... -
HBase在各大应用中的优化和改进
2015-10-28 14:59 640Facebook之前曾经透露过Facebook的hbase架构 ... -
一篇很好的解决系统问题过程描述文章
2015-09-23 08:40 462在网上看到的一篇解决h ... -
从OpenTsdb来分析rowkey设计
2015-09-06 16:04 4905讨论此问题前,先理解 ... -
HBase中asynchbase的使用方式
2015-08-25 10:32 8116Hbase的原生java 客户端是完全同步的,当你使用原生AP ... -
HBase 中mapreduce join的使用
2015-08-06 16:48 981首先介绍常用的几种 map ... -
Mapreduce优化的点滴
2015-07-16 15:18 795注:转载 1. 使用自定义Writable 自带的Text ... -
hadoop 如何自定义类型
2015-07-15 09:37 1211记录一下hadoop 数据类型章节的笔记,以便后期使用,本文是 ... -
napreduce shuffle 过程记录
2015-07-10 11:23 728在我看来 hadoop的核心是mapre ... -
ZooKeeper伪分布式集群安装及使用
2015-02-13 08:29 8821. zookeeper介绍 ZooKeeper是一个为分 ... -
hadoop-mahout 核心算法总结
2015-02-07 10:08 1505其实大家都知道hadoop为我们提供了一个大的框架,真正的 ... -
推荐引擎内部原理--mahout
2015-01-22 11:11 542转载自:https://www.ibm.com/devel ... -
hadoop 动态添加删除节点
2015-01-20 13:39 638转自:http://www.cnblogs.com/rill ... -
hbase hadoop zookeeper
2015-01-19 14:47 0hadoop 部署手册 http://www.iteblo ... -
mapreduce 开发以及部署
2015-01-16 13:56 794前面几篇文章的梳理让我对hadoop新yarn 框架有了一 ... -
hadoop yarn几个问题的记录
2015-01-13 11:48 614本文主要介绍以下几 ...
相关推荐
作为Nosql数据库的⼀员,HBase查询只能通过其 Rowkey来查询(Rowkey⽤来表⽰唯⼀⼀⾏记录),Rowkey设计的优劣直接影响读写性能。 由于HBase是通过Rowkey查询的,⼀般Rowkey上都会存⼀些⽐较关键的检索信息,我们需要...
阿里云 吴阳平(明惠) 阿里云HBase业务架构师 主要章节:
Spark存储数据到HBase实现RowKey完全散列-多进程多线程间Random完全随机,完美解决热点问题
更特定言之,本发明涉及对点、线、面二维矢量数据映射到一维的字符串型rowkey索引,使之能够用hbase存储海量矢量数据,提供高性能空间查询分析服务,特别是一种基于hbase和geohash的矢量数据空间索引方法
该文档是介绍hbase的rowkey设计与hbase的协处理器运用,与大家分享!
HBase-RowKey与索引设计(高清) HBase-RowKey与索引设计(高清)HBase-RowKey与索引设计(高清)
用户历史订单列表查询rowkey设计技巧 最左前缀原则
大数据性能调优之HBase的RowKey设计.docx
HBase的模式Schema设计的一些概念和原则 5 1)模式的创建与更新 5 2)列族的数量 6 3)行键设计RowKey 6 5. HBase的拓扑结构是什么? 7 1)拓扑结构 7 2)HBase与ZooKeeper的关系是什么? 7 3)HBase的内部结构管理...
HBase中,表会被划分为1...n个Region,被托管在RegionServer中。Region二个重要的属性:StartKey与EndKey表示这个Region维护的rowKey范围,当我们要读/写数据时,如果rowKey落在某个start-endkey范围内,那么就会定位...
2)、RowKey散列原则:如果RowKey是按时间戳的方式递增,不要将时间放在二进制码的前面,建议将RowKey的高位作为散列字段,由程序循环生成,低位放时间
HBASE的使用跟业务逻辑有很强的关联性,就像本文里提到的例子使用ElasticSearch更合适。...本文主要内容是通过合理hbase行键(rowkey)设计实现快速的多条件查询,所采用的方法将所有要用于查询中的列经过一些处理后
hbase原理和设计,包括二级索引,rowkey设计,常见的坑.
HBASE调优 HBASE技术框架与存储模型 v HBASE调优 v 硬件 v 系统参数 v java v 表的设计 v 客户端 v 服务器端
非常使用的 基于geohash 找一定范围内的 最近位置java代码
2-2+HBase-RowKey+与索引设计
HBase – Hadoop Database,是一...Google运行MapReduce来处理Bigtable中的海量数据,HBase同样利用Hadoop MapReduce来处理HBase中的海量数据;Google Bigtable利用 Chubby作为协同服务,HBase利用Zookeeper作为对应。
│ Hbase表中rowkey及列簇的设计 │ Hbase表设计-微博案例的表设计 │ Hbase表设计-微博案例的业务实现 │ Hbase列簇属性的介绍 │ Hbase性能优化-GC调优 │ Hbase性能优化-内存管理 │ Hbase性能优化-flush、...