读书笔记-HBase in Action-第三部分应用-(2)GIS系统
本章介绍用HBase存储、高效查询地理位置信息。
Geohash空间索引
考虑LBS应用中常见的两个问题:1)查找离某地近期的k个地点。2)查找某区域内地点。
假设要用HBase实现高效查找,首先要考虑的是空间局部性(Spatial Locality),即位置上相近的点得物理存储在一起。
最简单的地理位置数据由两个维度组成:经度X和纬度Y。那么相相应最简单的Rowkey也能够由X和Y组成。Rowkey的有序性决定了数据首先依照经度X排序。再依照纬度Y排序,这样的方式最大的问题是经度值相等的A地点和B地点,可能纬度上相差十万八千里。
Geohash的解决思路是将经度和纬度以同样的权重构建空间索引。详细算法例如以下图:在经度范围[-180。180],纬度范围[-90,90]内不断进行二分查找,假设值位于上半区则记标识位为1,位于下半区则记标识位为0。终于结果由经度纬度标识位交叉组成。
(注:在HBase中能够存储标识位的Base32编码串,每一个字符是5个bit位的编码结果)
观察下面数据例子。可知geohash较好地反映了空间局部性:数据依照距离远近有序排列,距离相近的点geohash值有着很多其它的同样前缀。
查找近期K个邻居
通过扫描geohash前缀能够高效解决这个问题1:查找离某地近期的k个地点。
当然,须要选择合适的位数来进行前缀匹配扫描。使用较少的位数能降低扫描次数,但可能会返回多余的数据,而使用较多的位数能可能每次扫描返回的结果优先,导致须要多次扫描。
然而,geohash值也存在一些问题,不能使用简单的前缀匹配扫描来查找邻居,例如以下图:有限长度的geohash值在地图上表示为一个矩形区域。位于中间的是dr5ruzb区域,它下方的邻居区域和它有着5位长度的同样前缀,而上方的三个区域尽管位置相邻,但仅仅有这2位长度的同样前缀。
所以,假设要查找dr5ruzb的近期k个邻居,保险起见,能够一起查找它周围8个相邻区域的近期k个邻居。然后将全部查找到的点依照距离排序再得出终于结果。伪代码例如以下:takeN查找某个区域的近期n个点
queryKNN则使用takeN查找四周8个相邻区域的近期n个点。终于再排序取值。
区域内查找
来一个区域内查找的实例:在某某广场内有多少个wifi热点?解决思路分两步:
第一步。将区域内查找转化为对一系列geohash索引的扫描。
第二步。推断扫描到的坐标点是否包括在待查找区域多边形内。
工具方面。能够使用JTS Topology Suite(http://tsusiatsoftware.net/jts/main.html),JTS实现了常见几何对象、空间拓扑数据结构和操作算法。使用JTS查找待扫描的geohash坐标详细过程例如以下:
- 依据待查找区域的各个顶点初始化多边形对象Geometry。并得出多边形对象的质心Centroid。
- 对质心Centorid坐标进行geohash编码,精度取一定位数,假设geohash编码所代表的闭包已经覆盖了待查找多边形对象Geometry,那么直接返回质心作为待扫描的坐标。假设没有覆盖,继续步骤3。
- 与前一节类似做法找到质心Centroid的四周8个相邻区域,闭包的范围扩大至包括这8个相邻区域顶点,再次推断闭包是否覆盖待查找区域。
假设覆盖,那么这9个点一起作为待扫描的坐标返回;假设还是不能覆盖。返回到步骤2。使用更短的geohash编码长度来扩大位置范围,直到覆盖待查找区域为止。
得到待扫描geohash坐标后,使用前一节近期K个邻居查找算法在HBase表中扫描出一系列附近坐标点,最后过滤掉不在待查找区域范围内的坐标点。当中,过滤步骤能够通过Filter过滤器完毕。能利用上HBase的分布式并行处理能力,降低到client的传输数据量。
相关文章
- Hive Over HBase的介绍
- 一条数据的HBase之旅,简明HBase入门教程2:数据模型
- 大数据工具篇之Hive与HBase整合完整教程
- Spring Boot 2.x :通过 spring-boot-starter-hbase 集成 HBase
- 大叔问题定位分享(49)hbase集群重启后master初始化失败
- HBase API 详细例子(封装的DAO类)
- Hbase 学习(十一)使用hive往hbase当中导入数据
- hbase 学习(十三)集群间备份原理
- Sparkstreaming读取Kafka消息再结合SparkSQL,将结果保存到HBase
- Hbase万亿级存储性能优化总结:配置项、hdfs、zookeeper、jvm参数等
- [转]缓慢但胜在稳健,HBase大势已成
- BigData:大数据开发的简介、核心知识(linux基础+Java/Python编程语言+Hadoop{HDFS、HBase、Hive}+Docker)、经典场景应用之详细攻略
- 带你了解 HBase 数据模型和 HBase 架构
- HBase源代码分析之MemStore的flush发起时机、推断条件等详情(二)
- Python编程:happybase读写HBase数据库
- 【图文详解】HBase 的数据模型与架构原理详解
- 1006-HBase操作实战(JAVA API状态)
- Hbase启动hbase shell运行命令报Class path contains multiple SLF4J bindings.错误
- HBase应用快速学习
- 淘宝在hbase中的应用和优化
- 读书笔记-HBase in Action-第三部分应用-(1)OpenTSDB
- HBase中的备份和故障恢复方法
- hbase基本概念和hbase shell经常使用命令使用方法
- 揭秘FaceBook Puma演变及发展——FaceBook公司的实时数据分析平台是建立在Hadoop 和Hive的基础之上,这个根能立稳吗?hive又是sql的Map reduce任务拆分,底层还是依赖hbase和hdfs存储