基于Solr的空间搜索(1)

标签: 未分类 | 发表时间:2013-01-09 11:19 | 作者:hongzhen
出处:http://rdc.taobao.com/team/jm

在Solr中基于空间地址查询主要围绕2个概念实现:

Cartesian Tiers 笛卡尔层

Cartesian Tiers是通过将一个平面地图的根据设定的层次数,将每层的分解成若干个网格,如下图所示:


 每层以2的评方递增,所以第一层为4个网格,第二层为16 个,所以整个地图的经纬度将在每层的网格中体现:

笛卡尔层在Lucene中对空间地理位置查询最大的用处在查找周边地址的时候有效的减少查询量,即将查询量可以控制在分层后最小的网格中的若干docId。那么如何构建这样的索引结构呢,其实很简单,只需要对应笛卡尔层的层数来构建域即可。也即是tiers0->field_0,tiers1->field_1,tiers2-field_2,……,tiers19->field_19。(一般20层即可)。每个对应笛卡尔层次的域将根据当前这条记录的经纬度通过笛卡尔算法计算出归属于当前层的网格,然后将gridId(网格唯一标示)以term的方式存入索引。这样每条记录关于笛卡尔0-19的域将都会有一个gridId对应起来。但是查询的时候一般是需要查周边的地址,那么可能周边的范围超过一个网格的范围,那么实际操作过程是根据经纬度和一个距离确定出需要涉及查询的从19-0(从高往低查,留给读者思考)若干层对应的若干网格的数据(关于代码实现在后面的文章内容阐述)。那么一个经纬度周边地址的查询只需要如下图圆圈内的数据:

所以通过这样的数据过滤,将极大的减少计算量。

GeoHash算法

在Lucene索引中将经纬度的二维坐标通过geohash,变成一个一维的字符串base32的坐标,例如,经纬度对应一个base32的坐标为DRT2Y,那这个base32的字符串什么意思呢?其实编码中每个字符都是代表一个区域,并且前面的字符是后面字符的父区域,即R是D区域内的子区域,T又为D区域的子区域,大家可以从如下图片获得base32的层级关系(以下图片均来自互联网):

进入D区域,则看到又分为若干区域,而R为其子区域:

继续进入R区域,可以继续看到有子区域T区域:

而2Y也是基于以上的关系类推,所以一个base32的编码是标示一个区域,而编码过程中会根据经纬度的精度来确定这个区域大小。从上面的解释大家肯定会想到编码的前缀是表示更大的区域。例如wx4g0ec1,它的前缀wx4g0e表示包含编码wx4g0ec1在内的更大区域。所以根据这个特点,利用模糊查询是可以达到一种附近地点的查询。

Geohash算法实现其实非常简单,网上有很多例子,在这里借用下这些例子再加上比较详细的说明。基本算法流程是基于多轮的收敛,以达到满足精度要求为止。具体流程以(39.92324 纬度, 116.3906 经度)为例,首先将纬度的范围(-90, 90)平分成两个区间(-90, 0)、(0, 90),如果目标纬度位在(-90,0),则编码为0,在(0,90)则编码为1。由于上面的例子中维度39.92324是属于(0, 90),所以第一轮获得的编码位取1。接下来再将(0, 90)分成 (0, 45), (45, 90)两个区间,而39.92324位于(0, 45),所以编码为0。以此类推,直到精度符合要求为止,如下图所示:

所以通过16轮的计算后得到经度39.92324的编码为:1011 1000 1100 0111 1001

经度也用同样的算法,对(-180, 180)多轮的依次细分计算:

得到经度116.3906的编码为1101 0010 1100 0100 0100

经纬度的编码都计算完毕后,接下来就需要合并经纬度的编码,规则是以经度开始,依次每次取一位合并成5位的新编码,如上图红色字标示顺序所示:

完成合并编码后就需要将该编码和base32编码表对应起来,做法是每5位为一个十进制数,以11100为例,它的十进制数是28,所以对应的base32编码表示W,如下图所示:

其他的五位编码依次从表中找到对应位置后,(39.92324 纬度, 116.3906 经度)的base32编码为:wx4g0ec1

解码算法与编码算法相反,先进行base32解码,然后分离出经纬度,最后根据二进制编码对经纬度范围进行细分即可,这里不再赘述。不过由于geohash表示的是区间,编码越长越精确,但不可能解码出完全一致的地址

而关于Solr+Lucene使用Cartesian Tiers 笛卡尔层和GeoHash的构建索引和查询的细节介绍将在新的Blog中阐述。

基于Solr的空间搜索(2)

基于Solr的空间搜索(3)

相关 [solr 空间 搜索] 推荐:

基于Solr的空间搜索(3)

- - 淘宝网综合业务平台团队博客
接上文,本文将继续介绍基于Solr的地理位置搜索的第二种实现方案. 从基于Solr的地理位置搜索(2)文章中可以看到完全基于GeoHash的查询过滤,将完全遍历整个docment文档,从效率上来看并不太合适,所以结合笛卡尔层后,能有效缩减少过滤范围,从性能上能很大程度的提高.       int tier = START_TIER;//开始构建索引的层数.

基于Solr的空间搜索(2)

- - 淘宝网综合业务平台团队博客
本文将继续围绕Solr+Lucene使用Cartesian Tiers 笛卡尔层和GeoHash的构建索引和查询的细节进行介绍. 在Solr中其实支持很多默认距离函数,但是基于坐标构建索引和查询的主要会基于2种方案:. 而这块的源码实现都在lucene-spatial.jar中可以找到. 接下来我将根据这2种方案展开关于构建索引和查询细节进行阐述,都是代码分析,感兴趣的看官可以继续往下看.

基于Solr的空间搜索(1)

- - 淘宝网综合业务平台团队博客
在Solr中基于空间地址查询主要围绕2个概念实现:. Cartesian Tiers 笛卡尔层. Cartesian Tiers是通过将一个平面地图的根据设定的层次数,将每层的分解成若干个网格,如下图所示:.  每层以2的评方递增,所以第一层为4个网格,第二层为16 个,所以整个地图的经纬度将在每层的网格中体现:.

Solr平台化搜索实战必知场景

- - 淘宝网综合业务平台团队博客
这个page是个人汇总了maillist、自己在搜索平台化、通用化过程中遇到的种种需求,为了避开必要的“敬业竞争禁止等”,特地从外网搜罗并汇总代表性的需求. 构成基于solr搜索“策略”参考、搜索应用查询的方案参考,但是,性能问题特别是高级用法,在大数据量时,务必压测,做到心里有底. 这里面给出的方法绝大部分基于solr接口、配置.

Solr SpellCheck 应用

- - 开源软件 - ITeye博客
通过对各类型的SpellCheck组件学习,完成项目拼写检查功能. 本文使用基于拼写词典的实现方式,solr版本为5.3.0. SpellCheck 简述. 拼写检查是对用户错误输入,响应正确的检查建议. 比如输入:周杰轮,响应:你是不是想找 周杰伦. Solr的拼写检查大致可分为两类,基于词典与基于Solr索引.

Solr DocValues详解

- - 企业架构 - ITeye博客
什么是docValues. docValues是一种记录doc字段值的一种形式,在例如在结果排序和统计Facet查询时,需要通过docid取字段值的场景下是非常高效的. 为什么要使用docValues. 这种形式比老版本中利用fieldCache来实现正排查找更加高效,更加节省内存. 倒排索引将字段内存切分成一个term列表,每个term都对应着一个docid列表,这样一种结构使得查询能够非常快速,因为term对应的docid是现成就有的.

solr的使用

- - Web前端 - ITeye博客
solr的原理不和大家一一讲述,主要讲solr在使用过程中的注意事项.  首先是安装solr,安装步骤省略. (不要说我懒,安装步骤导出都是. 成功之后 需要在solr里面建立一个针对你的业务的服务,我想建立一个叫做discuz的服务. 然后你在你的solr目录 :solr-5.5.3/server/solr/  下看见了discuz   ,这是你刚刚创建的,针对某一业务的整个搜索配置都是在这个目录下配置的.

Solr调优参考

- - 淘宝网通用产品团队博客
共整理三部分,第一部分Solr常规处理,第二部分针对性性处理,前者比较通用,后者有局限性. 务必根据具体应用特性,具体调节参数,对比性能. 具体应用需要全面去把控,各个因素一起起作用. 第一部分. E文连接 http://wiki.apache.org/solr/SolrPerformanceFactors.

Solr之缓存篇

- - 淘宝网综合业务平台团队博客
Solr在Lucene之上开发了很多Cache功能,从目前提供的Cache类型有:. 而每种Cache针对具体的查询请求进行对应的Cache. 本文将从几个方面来阐述上述几种Cache在Solr的运用,具体如下:. (1)Cache的生命周期. (2)Cache的使用场景. (3)Cache的配置介绍.

Solr主从备份

- - 研发管理 - ITeye博客
SOLR复制模式,是一种在分布式环境下用于同步主从服务器的一种实现方式,因之前提到的基于rsync的SOLR不同方式部署成本过高,被SOLR1.4版本所替换,取而代之的就是基于HTTP协议的索引文件传输机制,该方式部署简单,只需配置一个文件即可. 以下讲解具体操作步骤: . 步骤分主服务器和从服务器,允许有多个从服务器,即从服务器的配置一样.