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

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

谷歌微软等科技巨头数据科学面试107道真题:你能答出多少?

选自Learndatasci 机器之心编译 参与:李泽南 来自 Glassdoor 的最新数据可以告诉我们各大科技公司最近在招聘面试时最喜欢向候选人提什么问题。...

30470
来自专栏智能算法

主宰这个世界的10大算法

出自linux中文社区 链接:https://linux.cn/article-3125-1.html 什么是算法? 简而言之,任何定义明确的计算步骤都可称为算...

38380

自然语言处理指南(第1部分)

自然语言处理(NLP)包含一系列技术,用以实现诸多不同的目标。下表中列出了解决某些特定问题对应的技术。

28980
来自专栏机器学习算法与Python学习

搞算法的我们,不知道这些算法怎么行

分享 动一动手指,分享给向我们一样需要的人 这是一篇有趣的文章,George Dvorsky试图解释算法之于当今世界的重要性,以及哪些算法对人类文明最为重要,如...

31980
来自专栏AI科技大本营的专栏

AI 技术讲座精选:数学不好,也可以学习人工智能(七)——自然语言处理的奇妙神奇之处

机器都能做到吗? 我现在是任由自动化左右吗? 未来AI会让作家失业吗? 请阅读本文。 编译 | AI100 在本系列的第五部分中发现了卷积神经网络...

37490
来自专栏华章科技

烧脑:谷歌微软等巨头107道数据科学面试题,你能答出多少?

来自 Glassdoor 的最新数据可以告诉我们各大科技公司最近在招聘面试时最喜欢向候选人提什么问题。首先有一个令人惋惜的结论:根据统计,几乎所有的公司都有着自...

13010
来自专栏数据小魔方

条形图组(辅助序列法)

今天跟大家分享的图表是条形图组(辅助序列法)! ▽▼▽ 这个图表曾在之前的条件格式条形组图中介绍过。不过使用的工具不同,之前那个使用条件格式做成的,今天教大家使...

39190
来自专栏PPV课数据科学社区

【黑科技】数据分析师的秘密-QQ聊天记录分析(三)

? 上两篇分析了群的活跃状况,成员活跃状况,以及一些文本的分析,包括词云,聊天关键字, 实体识别,情感分析等等,这篇只围绕一个问题来,那就是提取谈话内容的问题...

35450
来自专栏BestSDK

主宰我们生活的10大算法,经久不衰

什么是算法? 简而言之,任何定义明确的计算步骤都可称为算法,接受一个或一组值为输入,输出一个或一组值。(来源:homas H. Cormen, Chales E...

30530
来自专栏数据魔术师

干货|迭代局部搜索算法(Iterated local search)探幽(附C++代码及注释)

83270

扫码关注云+社区

领取腾讯云代金券