Yhzhtk's Blog

(热爱技术,高效Code)     归档  标签  源码  关于 


Lucene 如何通过GeoHash 查询距离

2014-02-13    geohash 


之前用Lucene做过位置距离查询的项目,其中Lucene搜索定位距离的原理就是GeoHash,关于GeoHash的介绍看这里GeoHash 介绍,这篇文章要说的是如何根据GeoHash查询距离。

以下面以这幅图来看,图片将经度为0作为X轴的原点,纬度为0作为Y轴的原点,图中为了问题简单化,仅化了3层,实际中3层是不够的。

假设坐标轴正方向表示1,负方向表示0。那么按照GeoHash方法划分区域,则A到J的GeoHash分别为:

位置点 GeoHash经度值 GeoHash纬度值 GeoHash值(经度+维度)
A 1 0 0 1 0 0 11 00 00
B 1 0 0 0 1 1 10 01 01
C 0 1 1 0 1 1 00 11 11
D 0 1 1 1 0 0 01 10 10
E 1 1 0 1 1 0 11 11 00
F 1 1 1 1 1 1 11 11 11
G 1 1 1 1 1 1 11 11 11
H 1 1 1 0 1 1 01 11 11
I 0 1 0 0 1 0 00 11 00
J 0 0 0 1 1 1 01 01 01

情况1:

  我们看E、F两个点,其中前两层都是11,仅第三层不一致,E、F离得很近。

情况2:

  我们看E、I两个点,第二、三层匹配,仅第一层不一致,E、I却离得很远。同理B、J也一样。

推测结果:

  那么我们可以这样认为,GeoHash匹配距离时,必须从前往后,直到第一个不能匹配为止,匹配的层数越多越相近。

情况3:

  拿着结果1,我们看F、G两个点,三层完全匹配,是不是F、G的距离要比E、F的距离近呢?不是,E、F距离更近。

情况4:

  加速A、B、C、D无限靠近原点,那么A、B、C、D应该离得非常近,但是我们看GeoHash,A、B、C、D并不是按照从前往后匹配的。

分析结果

  GeoHash并不是通过从前往后匹配来判断距离的,推测结果是错误的,那是通过什么呢?下面是我的猜测,具体实现思路还需要看看Lucene的源码。

A、B、C、D四个点,如果按字符串从前往后匹配,那么匹配程度非常低,但是如果把Hash当成一个二进制数,100表示4,而011表示3,通过数的差的绝对值,我们发现,无论是经度还是维度,A、B、C、D之间的差的绝对值都不会大于一。因为A、B、C、D无限靠近原点,即使有Geo划分有无限层,A的维度是1 0 0 0 0 0...(无限0),B的维度是0 1 1 1 1 1...(无限1),那么他们的绝对值仍然不会大于1。同样的,ABCD任意两点的经纬度差绝对值不会大于1。由于都是整数,除了0之外,最小差绝对值就是1。

由此我们可以推论:判断两个点的距离,是通过GeoHash的经纬度Hash分别按照二进制取差,绝对值越小,则距离越近。

至于经度和维度的合并的距离,由于经纬度是完全垂直的,就可以根据平方和(勾股定理)来定了。

如何判断F、G要比E、F远,应该就没有办法,因为这儿划分的层次太少,当划分层次多的时候,经纬度绝对值差E、F自然会比F、G小。所以,分层的大小直接影响到距离的精度。

以上都是自己分析的,不知是否正确,如有错误,欢迎批评指正。





Load Disqus comments, wait a moment..

分类标签

jekyll3   编码1   windows1   bootstrap1   git3   删除1   命令3   python11   ide1   学习笔记3   实例分析1   mp3-tag1   github1   gravatar1   goagent1   翻墙1   C#4   找茬工具1   微博自动评论1   电脑监控1   备份1   云搜索1   wxPython1   py2exe1   yaml1   Eric1   PyQt1   Django1   设计模式5   翻译4   单例1   工厂1   抽象工厂1   生成器1   原型1   适配器1   桥接1   组合1   装饰1   外观1   享元1   代理1   MVC1   观察者1   状态1   策略1   模板1   访问者1   职责链1   解释器1   迭代器1   中介者1   备忘录1   js1   resize bar1   geohash1   口琴1   rpm安装gitlab1   CentOs1   WordPress1   数据库1   读脏数据1   丢失的修改1   不可重复读1   幻影读1   1   隔离1   思维导图1   事务1   笔记迁移1   note1   issue1  

最新博文

最新评论

Feed订阅


©2013 首页   关于     View me on GitHub Powered by Jekyll & Bootstrap 知识共享许可协议