Geohash介绍及针对具体需求的改良

原创
2016/07/03 23:02
阅读数 9.5K

1. Geohash介绍

1.1. 应用场景

  • POI(Point of Interest):某个地图点周围的美食娱乐等的搜索;
  • 热点分析:统计某个地图区域的热度;
  • 其他,暂时没想到。

1.2. Geohash算法

    地图上一般是使用经度和纬度两个维度来唯一的确定一个点,而geohash采用经纬度二维值转为一维的值。

    优点:

  • 只需要对一个字段进行索引,提高性能、降低复杂度
  • 可转成可排序,可比较的字符串,满足灵活的需求

    具体详细的介绍参考 维基百科: https://en.wikipedia.org/wiki/Geohash

2. 针对具体需求改进

2.1. 定制经纬度范围

    标准的geohash算法的经度范围是(-180,180),纬度范围为(-90,90),这个范围是适用于全球的地理位置的。但是我们目前的应用数据点仅局限于国内,所以可以将范围缩小。

  • 减少计算的次数提高性能
  • 降低geohash有效值的位数
  • 自定义经纬度范围可选定一个趋于正方形的范围,当计算结果为一个圆形区域,这样能更好的和圆契合。

    可选定经纬度范围, 经度(70, 140),纬度(15, 60)。

2.2. 使用long型值,更细粒度的精度控制

    首先说明下,标准的geohash值,是采用base32编码的字符串作为值,每一字符代表5个bit位。也就是精度多一位字符就多出了5个bit位。先看下维基百科提供的一组数据:

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.7 ±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

    这里的geohash length代表的是标准geohash算法中的字符长度,可以看出当geohash的长度为8时,误差(km error)为19米,当长度为7时,误差为76米,当长度为6时,误差为610米,可以看出随着geohash位数的减少误差增加倍数在4倍左右和8倍左右交替。 这里的误差其实只是个大概的数量级,代表的是geohash对应的矩形区域的对角线长度的二分之一。

    我的需求对应区域的大小控制需要更精确,我希望我通过缩短geohash一位不至于导致区域增大过快,所以我这里采用geohash的二进制转成64位long型值作为geohash值。高位为有效位,低位补0。并记录下long值得有效位是多少。比如,根据具体需求,可以截取前2n(0<n<32)bit位作为geohash的long值的有效位,区域的精度也基本控制在2倍左右的增长。可以达到更细粒度的精度控制。

    改良后的数据:

geohash有效位2n(0<n<32) lat bits lng bits lat error lng error km error
32(n=16) 16     16     ±0.00137 ±0.00275 ±0.304
34(n=17) 17 17 ±0.00069 ±0.00137 ±0.152
36(n=18) 18 18 ±0.00034 ±0.00069 ±0.076
38(n=19) 19 19 ±0.00017 ±0.00034 ±0.038
40(n=20) 20 20 ±0.000085 ±0.00017 ±0.019

误差(km error)是随着n的减小成2倍增长,相比标准geohash算法的4倍,8倍增长要缓和很多,从而可以更细粒度的控制精度。

 

3. 延伸

    虽然geohash是用于地图领域,但是其核心思想是对区域范围通过二分法逼近的方式将二维空间数据降维成一维数据,这种思想也可以扩展到一切二维空间计算的场景的,不过暂时没有想到具体的应用。

展开阅读全文
打赏
2
4 收藏
分享
加载中
您好,请问km error 是怎么计算的?
2019/12/06 10:41
回复
举报
想跟您请教一下:geohash字符串长度对应的km误差是怎么计算得出的?您在文章中提到这个km error是矩形对角线长度的一半,但根据我的计算,在geohash length为1时,矩形对角线长度的均值为5844km,一半是2922km。这与表中给出的2500km相差还是比较多,针对这一困惑,希望能得到您的回复。谢谢!
2019/07/04 11:47
回复
举报
囚兔博主

引用来自“timewanderlu”的评论

恩,非常感谢。 文中的-- 所以我这里采用geohash的二进制转成64位long型值作为geohash值。高位为有效位,低位补0。并记录下long值得有效位是多少。 这句话不是很懂,能给个例子吗 😊
比如我的geohash二进制为8bit 10010110,转成64bit long型值为四个字节,二进制表示为:10010110 00000000 00000000 00000000 00000000 00000000 00000000 00000000,高位的8bit为有效bit,低位全部补0,在构造geohash数据结构的时候要有两个属性:其一是一个long型数值,其二是有效bit的数量(取值范围0~64)
2017/07/11 09:09
回复
举报
恩,非常感谢。 文中的-- 所以我这里采用geohash的二进制转成64位long型值作为geohash值。高位为有效位,低位补0。并记录下long值得有效位是多少。 这句话不是很懂,能给个例子吗 😊
2017/07/10 09:01
回复
举报
囚兔博主

引用来自“timewanderlu”的评论

你好,请问有相关的实现代码吗?
文中提到的改良相关的代码不方便分享出来,但是也是基于开源项目https://github.com/kungfoo/geohash-java进行了修改,改动不大,你可以看看。
2017/07/07 08:59
回复
举报
你好,请问有相关的实现代码吗?
2017/07/06 18:39
回复
举报
更多评论
打赏
6 评论
4 收藏
2
分享
返回顶部
顶部