焦俊楠，刘茂莲，王科，杨宗林
（中国联合网络通信有限公司山东省分公司，济南 250000）
摘 要
通信行业数据分析时经常需要将带有经纬度的海量地理化数据点与固定大小的栅格区域进行关联，即根据数据点的经纬度、与固定栅格的经纬度范围进行匹配，实现地理化信息数据点的栅格化，进行信号强度、信号质量的栅格化分析，从而实现对指定区域的无线信号环境进行评估。使用关系型数据库、通过对数据点的经纬度与栅格边框比较、能够完成经纬度数据点与栅格的匹配关联，但效率较低。geohash算法在解决这类问题时能大幅提高经纬度点与栅格的匹配效率。
关键词：geohash；关系型数据库；通信；栅格化
一、引言
通信行业进行无线信号评估时，由于采样点数据量庞大、往往需要将含有经纬度的数据点、与固定大小的经纬度栅格进行匹配，实现海量地理化数据点的栅格化，进而对一个栅格内的数据点进行数据分析，实现对某地理化栅格的无线信号评估。在进行经纬度数据点、与划分的经纬度栅格进行匹配时，如采用关系型数据库，最直观的匹配方案是，第一步，根据数据点的经度，与每个栅格定义的经度范围上下限，找出符合范围的所有栅格集合A；第二步，根据数据点的纬度、在栅格集合A中，找出符合纬度范围的唯一栅格。因每个数据点的匹配需要检索所有栅格的四个范围（经度上限、经度下限、纬度上限、纬度下限），实际生产中，当面对百万数量级别数据点、与十万数量级的数据栅格匹配的问题时，因计算繁杂、仅仅匹配工作就消耗大量时间，严重影响栅格评估分析的时效性。通过探索比较，发现将geohash算法应用于此类地理化数据匹配问题，能显著提高检索效率、加快匹配效率，在本实验环境中、匹配效率提升在100倍以上。
二、Geohash算法及应用
2.1 Geohash算法
GeoHash本质上是空间索引的一种方式，其基本原理是将地球理解为一个二维平面，将平面递归分解成更小的子块，每个子块在一定经纬度范围内拥有相同的编码。以GeoHash方式建立空间索引，可以提高对空间poi数据进行经纬度检索的效率。本例中，我们将数据点、栅格中心点的坐标，均求出满足要求的geohash，通过geohash设置索引完成数据点、数据栅格中心点的快速匹配，并将栅格中心点更新到数据点记录中，完成数据点与栅格的关联工作。
2.2 Geohash算法实践
2.2.1 测试环境
硬件使用联想 昭阳 K43c-80 笔记本电脑一台（CPU 英特尔 Core i5-8250U @ 1.60GHz 四核，内存三星 DDR4 2400MH-8 GB，硬盘为西数 WDC WD5000LPLX-24ZNTT0 500 GB ）。
软件环境，操作系统为Windows 10（Windows 10 专业版 64位Version 1607 / DirectX 12），数据库使用的是支持空间计算的Mysql5.7（Server version: 5.7.21-log MySQL Community Server GPL）。
数据库表结构，共两张原始表，表1为数据点表，名称t_user，每条记录为一个经纬度数据点，包含该数据点的经度、纬度、数据点唯一id；表2为栅格表，名称t_grid，每条记录为一个栅格，包含该栅格的中心点经度、纬度、栅格唯一id。
2.2.2实施步骤
1)栅格表t_grid新增字段pc（代表栅格中心点），类型point；
新增字段gehash，类型varchar(255)。
对pc字段初始化。执行结果如下
#生成中心点
mysql> update t_grid set pc=ST_GeomFromText(concat('point(',longitude,' ',
latitude,')'));
Query OK, 302909 rows affected (35.34 sec)
Rows matched: 302909 Changed: 302909 Warnings: 0
对gehash字段初始化。执行结果如下
#为栅格中心点生成geohash
mysql> update t_grid set gehash=st_geohash(pc,6);
Query OK, 302909 rows affected (22.82 sec)
Rows matched: 302909 Changed: 302909 Warnings: 0
设置pc、gehash字段非空，设为索引。
2)数据点表t_user新增puser字段（代表数据点所在位置），类型point；
新增grid字段（最终栅格中心点更新到这里），类型point；
新增ugeohash字段（用户位置的geohash），类型varchar(255)。
Puser字段初始化。
执行结果如下
#user表，根据经纬度，生成point字段puser
mysql> update t_user set puser=ST_GeomFromText(concat('point(',l
ongitude,' ',latitude,')'));
Query OK, 2394267 rows affected (3 min 59.41 sec)
Rows matched: 2394267 Changed: 2394267 Warnings: 0
ugeohash字段初始化
#为数据点生成geohash
mysql> update t_user set ugeohash=st_geohash(puser,6);
Query OK, 2394267 rows affected (2 min 51.09 sec)
Rows matched: 2394267 Changed: 2394267 Warnings: 0
设置puser、ugeohash非空，设为索引。
3)执行命令，第一，根据t_user表的ugeohash找出栅格表相同geohash的栅格来，根据geohash的原理，初始化geohash字段时我们设置了geohash为6位（查表知±610米），也就是说，我们取出了数据点位置半径610米以内的栅格了。第二，计算数据点位置，到以上栅格中心点的距离，并按距离排序、取第1个，这个栅格就是距离数据点最近的栅格了。第三，把这个中心点更新到t_user表的grid字段，匹配完成。
#测试1行
mysql> update t_user set grid=(select pc from t_grid where gehash=ugeohash order by ST_Distance(pc,puser) asc limit 1) where id=2;
Query OK, 1 row affected (0.01 sec)
Rows matched: 1 Changed: 1 Warnings: 0
#1万行
mysql> update t_user set grid=(select pc from t_grid where gehash=ugeohash order by ST_Distance(pc,puser) asc limit 1) where id>9999 an
d id<20001;
Query OK, 9993 rows affected (16.22 sec)
Rows matched: 10001 Changed: 9993 Warnings: 0
#8万行
mysql> update t_user set grid=(select pc from t_grid where gehash=ugeohash order by ST_Distance(pc,puser) asc limit 1) where id>20000 a
nd id<100000;
Query OK, 79916 rows affected (2 min 6.07 sec)
Rows matched: 79999 Changed: 79916 Warnings: 0
#229万行
mysql> update t_user set grid=(select pc from t_grid where gehash=ugeohash order by ST_Distance(pc,puser) asc limit 1) where id>99999;
Query OK, 2291559 rows affected (1 hour 6 min 35.27 sec)
Rows matched: 2294268 Changed: 2291559 Warnings: 0
三、结论
1) MySQL5.7的空间操作增加了geohash函数。对于从海量数据中快速检索出附近的点，geohash是个很好的方案。
#方法1.为1个用户，从30万栅格中，搜索最近的1个栅格匹配进去
mysql> update t_user set grid=(select pc from t_grid order by ST_Distance(t_user.puser,t_grid.pc) asc limit 1)
where t_user.id=1;
Query OK, 0 rows affected (3.49 sec)
Rows matched: 1 Changed: 0 Warnings: 0
以上操作是，不利用geohash，单纯从t_user表中取一个位置点，然后用这个位置点跟30万个栅格中心点分别计算距离，然后找出最近的栅格。这时，1条记录耗时3.49秒，要完成所有220万条记录需要115天，在实际生产中就不可行了，跟利用geohash先缩小距离算法的0.02秒相比差了150余倍。
2) 本次问题只涉及到了mysql的空间距离计算，还有很多强大的功能（判别两个图案是否相交、重合、两点的球面距离等）
3) mysql语句优化。Explain等工具分析语句执行实际使用的索引。
四、参考文献
[1]Oracle Corporation.Spatial Function Reference[DB/OL].https://dev.mysql.com/doc/refman/5.7/en/spatial-function-reference.html, 2021-03-01
[2] Fox A , Eichelberger C , Hughes J , et al. Spatio-temporal indexing in non-relational distributed databases[C]// IEEE International Conference on Big Data. IEEE, 2013.
[3] Zoran Balki?, Damir ?o?tari?, Horvat G . GeoHash and UUID Identifier for Multi-Agent Systems[M]// Agent and Multi-Agent Systems. Technologies and Applications. Springer Berlin Heidelberg, 2012.
[4] Moussalli R , Srivatsa M , Asaad S . Fast and Flexible Conversion of Geohash Codes to and from Latitude/Longitude Coordinates[J]. 2015:179-186.
[5] 金安, 程承旗, 宋树华,等. 基于Geohash的面数据区域查询[J]. 地理与地理信息科学, 2013.
[6] Van L H , Takasu A . An Efficient Distributed Index for Geospatial Databases[C]// International Conference on Database & Expert Systems Applications. Springer International Publishing, 2015.