前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Geohash介绍及针对具体需求的改良

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

作者头像
囚兔
发布2018-02-08 10:48:16
1.9K0
发布2018-02-08 10:48:16
举报
文章被收录于专栏:IT杂记

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

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. Geohash介绍
    • 1.1. 应用场景
      • 1.2. Geohash算法
      • 2. 针对具体需求改进
        • 2.1. 定制经纬度范围
          • 2.2. 使用long型值,更细粒度的精度控制
          • 3. 延伸
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档