Jamzy Wang

life is a struggle,be willing to do,be happy to bear~~~

附近地点搜寻方案实现

2015-02-03 10:20

原创声明:本作品采用知识共享署名-非商业性使用 3.0 版本许可协议进行许可,欢迎转载,演绎,但是必须保留本文的署名(包含链接),且不得用于商业目的。

附近地点搜索,顾名思义,就是搜索用户附近有哪些地点。本文将讨论附近地点查询常见解决方案并提出一种基于redis集群的实现方案。

此处输入图片的描述

假设数据库中有每个商家的经纬度信息:

1
2
3
4
5
6
7
8
9
10
[12.4920147, 41.9175913]
[12.4844774, 41.9184129]
[12.4889198, 41.9091036]
[12.4900356, 41.9075961]
[12.4878678, 41.9056434]
...
[12.4892558, 41.9039325]
[12.4970978, 41.8973968]
[12.5016059, 41.9031011]
[12.4895595, 41.9025333]

现在给定用户的二维坐标(经度,维度),计算该坐标和数据库中的每个商户的坐标的距离,然后选出距离最近的。

最直接的方法自然是计算用户坐标和数据库中每个商户的坐标之间的距离,然后选出距离最小的。计算两个坐标的距离可以参考球面上任意两点之间的距离计算公式,常见的有:

1
2
1) Great-circle distance
2) Haversine formula

wikipedia推荐使用Haversine公式,理由是Great-circle distance公式用到了大量余弦函数, 而两点间距离很短时(比如地球表面上相距几百米的两点),余弦函数会有较大的舍入误差。而Haversine公式采用了正弦函数,即使距离很小,也能保持足够的有效数字。但用C++库中的正弦、余弦公式计算时,两个公式的区别不大。

很显然,当单表数据量很大时,上述方案会非常耗时(经测试,单表数据达到10万时,上述方案耗时就达到10s以上),不适合在线处理。下面介绍一种改进方法。

附近地点搜索条件是 距离,而数据库中一般只保存地点的 经纬度,因此无法直接查询,必须逐一将经纬度坐标转换为距离。那么有没有办法将搜索条件从距离变为经纬度呢?如果有的话,就可以利用数据库中经纬度上的索引,提高查询效率。利用圆形的外接矩形代表实际搜索区间就是一种不错的方法。

此处输入图片的描述

比如查询坐标(12.4920147, 41.9175913)附近300米内有什么商家?那么可以先计算出这个给定坐标附近300米这个范围的坐标范围。虽然它是个圆,但我们可以先求出该圆的外接正方形,然后拿正方形的经纬度范围去搜索数据库。 这样,根据当前点坐标,我们可以得出搜索范围为

1
2
3
4
left-top    : (lat + dlat, lng - dlng)
right-top   : (lat + dlat, lng + dlng)
left-bottom : (lat - dlat, lng - dlng)
right-bottom: (lat - dlat, lng + dlng)

通过这种方式搜索条件就由距离转换成了经纬度,然后我们可以利用这个经纬度在数据库中直接查询:

1
select shop_id from place where lat > lat1 AND lat < lat2 AND lng > lng1 AND lng < lng2;

为了提高查询速度,需要在lat和在lat和lng列上建立 联合索引

1
create index lat_lng_index on place(lat,lng)

显然,这样查询到的地点是正方形范围内的地点,一些结果与当前点的距离可能会超出给定的距离。一般的应用场景下数据库查询结果可以直接返回给用户,如果要求严格,可以遍历结果并计算与当前点之间的距离,并过滤掉不符合要求的结果。

这样做有一个显著特点:速度慢。慢的原因有两个, 第一是范围比较的索引利用率并不高

第二是SQL语句极其不稳定(不同的当前位置会产生完全不同的SQL查询),很难缓存。 那能不能从数据库存储的经纬度上下点功夫呢?而Geohash算法就是这样干的。通过字符串匹配来实现附近区域的查找。

GeoHash

GeoHash是一种对经纬度进行编码的实现,利用GeoHash可以将二维的坐标编码成一维的数据,这个一维数据是一个可以排序,可以比较的字符串编码。

GeoHash编码

基本思想:通过对二维空间划分区间,以经度和维度二分法逐步逼近给定点,得到方格区间的同时得到两组0 1串(经度和维度各一组),然后将二组串按位交叉合并(经度先),得到一串二进制数,将二进制数每连读五位分组,映射到32个可打印字符(base32编码),即得到geohash编码串。

其算法的过程如下:

二进制编码地球纬度区间是[-90,90], 如某纬度是39.92324,可以通过下面算法对39.92324进行逼近编码:

1)区间[-90,90]二分为[-90,0),[0,90]左右区间,如果某个坐标的维度属于[-90,0)则标记为0,否则标记为1。39.92324属于右区间[0,90]标记为1;

2)接着将区间[0,90]进行二分为 [0,45),[45,90]两部分,如果某个坐标的维度属于 [0,45)则标记为0,否则标记为1。39.92324属于左区间 [0,45)标记为0;

此处输入图片的描述

3)递归执行上述过程,如果给定的纬度(39.92324)属于左区间,则记录0,如果属于右区间则记录1。

整个过程的划分如下:

此处输入图片的描述

在上述过程中39.92324总是属于某个区间[a,b]中。随着迭代区间[a,b]越来越小,越来越逼近39.92324;这样随着算法的进行会产生一个序列1011 1000 1100 0111 1001,序列的长度跟给定的区间划分次数有关。

同理,地球经度区间是[-180,180],对经度116.3906进行编码的过程也类似:

执行一次划分:

此处输入图片的描述

执行三次划分:

此处输入图片的描述

整个过程的划分:

此处输入图片的描述

经过上述对经度和维度的划分可以得到纬度产生的编码为 1011 1000 1100 0111 1001,经度产生的编码为 1101 0010 1100 0100 0100。接下来将经度和维度交叉组合在一起,偶数位放经度,奇数位放纬度得到新串:11100 11101 00100 01111 00000 01101 01011 00001。通常情况下,纬度编码会比经度编码短一位或是长度相同,原因是经度范围是360°,而纬度编码是180°。合并后的编码可以理解为地球上的一个点,实际上代表的是一个范围,编码长度越长,代表的范围越小。

为了表示方便,上述二进制串通常用 base32 编码进行编码。base32编码用0-9、b-z(去掉a, i, l, o)这32个字符进行编码,5个二进制串用一个字符编码。

1
2
3
4
十进制    0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15
base32   0   1   2   3   4   5   6   7   8   9   b   c   d   e   f   g
十进制    16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31
base32   h   j   k   m   n   p   q   r   s   t   u   v   w   x   y   z

(39.92324, 116.3906)经过base32编码后为 wx4g0ec1

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

GeoHash特性

1)GeoHash将二维的经纬度转换成字符串,每一个字符串代表了某一矩形区域。也就是说,这个矩形区域内所有的点(经纬度坐标)都共享相同的GeoHash字符串,这样既可以保护隐私(只表示大概区域位置而不是具体的点),又比较容易做缓存(因为同一个区域发送的请求是一样的,方便数据库做缓存)

enter image description here

2)GeoHash字符串越长,表示的范围越精确。当GeoHash base32编码长度为8时,精度在19米左右,而当编码长度为9时,精度在2米左右,编码长度需要根据实际应用场景进行选择。具体的字符串长度和经度的关系如下:

此处输入图片的描述

3)编码的前缀可以表示更大的区域。例如zx4t0ec1,它的前缀zx4t0ec表示包含编码zx4t0ec1在内的更大范围。 两个GeoHash字符串,如果前缀匹配越长表示距离相近。

4)GeoHash有一个特点,相近的坐标的GeoHash值有 很大几率 非常接近,从属于同一个GeoHash编码区域,分割边界两侧的点除外。

此处输入图片的描述

分割边界附近的点虽然距离相近但是GeoHash值会相差很大,那么如何解决这种特殊场景呢?同时搜索当前格子周围的8个格子,即可解决这个问题

enter image description here

以geohash的python库为例,相关的geohash操作如下:

1
2
3
4
5
>>> import geohash
>>> geohash.encode(39.92324, 116.3906, 5)  # 编码,5表示编码长度
'wx4g0'
>>> geohash.expand('wx4g0') # wx4g0格子及周围8个格子的编码
['wx4ep', 'wx4g1', 'wx4er', 'wx4g2', 'wx4g3', 'wx4dz', 'wx4fb', 'wx4fc', 'wx4g0']

基于GeoHash的查询方案

通常GeoHash应用场景需要满足一下需求:

1
2
3
1.频繁的更新和读取
2.可按距离排序(支持分页)
3.支持多条件筛选(一个经纬度数据还包含其他属性,比如社交系统的性别、年龄)

sphinx和mongodb支持geo索引可以直接使用,性能本人没有测试过,不做评价。mysql方案中,在纬度和经度入库时,可以在数据库中新加一字段geohash,记录此点的geohash值。查找附近区域时,可以利用 在mysql中的like关键字进行模糊查询,如 like ‘wm3yr3%’;且此结果可缓存;在小区域内,不会因为改变经纬度,而重新数据库查询。这种方案不直接支持按照距离排序(可以对like查询结果做排序),支持多条件筛选,当mysql单表数据量超过100万时,like模糊查询的性能会很差,通常需要好几秒,可以考虑分表或者分库的方法提升查询性能。

基于GeoHash的redis集群方案

根据GeoHash的前缀长度建立一些列的set。假设商户信息格式为(Geohash,id,label),现有一条记录GeoHash = “abcdefghij”,id = “10001”,label = “huoguo”,那么这个商户id将被存储到如下set中(set键值:“set:GeohashValue”,“set:GeoHashValue:labelValue”)中:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
键值                     value
set:kbcdefghyj          (10001)
set:kbcdefghy           (10001)
set:kbcdefgh            (10001)
set:kbcdefg             (10001)
set:kbcdef              (10001)
set:kbcde               (10001)
set:kbcd                (10001)
set:kbcdefghyj:huoguo   (10001)
set:kbcdefghy:huoguo    (10001)
set:kbcdefgh:huoguo     (10001)
set:kbcdefg:huoguo      (10001)
set:kbcdef:huoguo       (10001)
set:kbcde:huoguo        (10001)
set:kbcd:huoguo         (10001)

在查询时,可以设置一个阈值,比如查询最近的50个符合条件的商家,那么可以分级查找,先查找最长前缀匹配的(比如匹配10位GeoHash值),如果查询结果不足50个,则继续查找匹配9位前缀的GeoHash值,一直继续下去,直到满足查询条件50或者达到匹配极限(比如匹配4位)。匹配4位GeoHash串精度差为20km,匹配5位GeoHash串精度差为2.4km。具体GeoHash串的取值长度取决于具体应用场景。比如查询GeoHash串为“kbcdefgmny”,则先查询“set:kbcdefgmny”,再查询“set:kbcdefgmn”,再查询“set:kbcdefgm”,直到查询结果数量满足条件。可以同时查询周围8个格子以解决边界问题。如果查询附近的“火锅店”则可以这样查询:先查询“set:kbcdefgmny:huoguo”,再查询先查询“set:kbcdefgmn:huoguo”,…。由于redis是一种内存数据库,因此查询效率极高。

附近商家查询的示例代码(查询结果由近到远):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class DBNearShop {
    public static function searchNearShop($location) {//$location is Geohash,is a string
        $redis = DBConnect::getRedisServer();
        $currentLength =  SetKeyConfigure::LONGEST_KEY_LENGTH;
        //从最长匹配到最短匹配依次查找set中元素的个数,如果有达到搜索条件的则停止,不然搜索到最短匹配为止。
        $currentSetSize = 0;
        for( ; $currentLength >= SetKeyConfigure::SHORTEST_KEY_LENGTH; $currentLength-- ) {
            $key = substr($location,0,$currentLength);
            $currentSetSize = $currentSetSize + $redis->sCard($key);
            if($currentSetSize >= SetKeyConfigure::RESULT_SIZE) {
                break;
            }
        }
        $result = array();
        for($length = SetKeyConfigure::LONGEST_KEY_LENGTH; $length >= $currentLength; $length-- ) {
            if ($length == SetKeyConfigure::LONGEST_KEY_LENGTH) {
                $key = substr($location,0, $length);
                $res = $redis->sMembers($key);
                foreach($res as $shopId) {
                    $result [] = $shopId;
                }
            }
            else {
                $key_1 = substr($location,0,$length-1);
                $key_2 = substr($location,0, $length);
                $res = $redis->sDiff($key_1, $key_2);
                foreach($res as $shopId) {
                    $result [] = $shopId;
                }
            }
        }
        return $result;
    }
}

带筛选条件的附近商家(查询结果由近到远):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class DBConditionShop {
    public static function searchConditionShop($location,$condition) {
        $redis = DBConnect::getRedisServer();
        $currentLength =  SetKeyConfigure::LONGEST_KEY_LENGTH;
        //从最长匹配到最短匹配依次查找set中元素的个数,如果有达到搜索条件的则停止,不然搜索到最短匹配为止。
        $currentSetSize = 0;
        for( ; $currentLength >= SetKeyConfigure::SHORTEST_KEY_LENGTH; $currentLength-- ) {
            $key = substr($location,0,$currentLength) .$condition;
            $currentSetSize = $currentSetSize +  $redis->sCard($key);
            if($currentSetSize >= SetKeyConfigure::RESULT_SIZE) {
                break;
            }
        }
        $result = array();
        for($length = SetKeyConfigure::LONGEST_KEY_LENGTH; $length >= $currentLength; $length-- ) {
            if ($length == SetKeyConfigure::LONGEST_KEY_LENGTH) {
                $key = substr($location,0, $length) .$condition;
                $res = $redis->sMembers($key);
                foreach($res as $shopId) {
                    $result [] = $shopId;
                }
            }
            else {
                $key_1 = substr($location,0,$length-1) .$condition;
                $key_2 = substr($location,0, $length) .$condition;
                $res = $redis->sDiff($key_1, $key_2);
                foreach($res as $shopId) {
                    $result [] = $shopId;
                }
            }
        }
        return $result;
    }
}

Ref

Comments