地理信息检索

在工程实践中需要解决以下问题:1）检索门店附近一定范围内的活跃顾客，之后可以对顾客进行营销，比如通过push方式给顾客发送促销消息，从而达到拉新的目的 2）检索空间指定区域内，如某个商圈内或者某个商场内的顾客，进行有针对性的营销 3）判断点在哪个区域内，比如查询用户所在的商圈、所在的大学等等。这些功能作为基础服务，需要系统具备很高的性能，低时延、高吞吐。

本文主要介绍如何实现：1）检索指定坐标一定范围内的顾客 2)检索区域(如商圈、购物中心)内的顾客。

数据结构

程序=数据结构+算法，处理问题的关键点是选择合适的数据结构以及算法。空间索引是解决这类问题的利器，常用的空间索引数据结构包含:geohash、kd树、r树等。kd树（k-dimensional树的简称），主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索），利用kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量。

kd-tree

kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。kd树是二叉树，表示对k维空间的一个划分（partition）。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。

构造kd树的方法如下：构造根结点，使根结点对应于k维空间中包含所有实例点的超矩形区域；通过下面的递归方法，不断地对k维空间进行切分，生成子结点。

在超矩形区域（结点）上选择一个坐标轴和在此坐标轴上的一个切分点，确定一个超平面，这个
超平面通过选定的切分点并垂直于选定的坐标轴，(通常，依次选择坐标轴对空间切分)将当前超矩形区域切分为左右两个子区域（子结点）；这时，实例被分到两个子区域。这个过程直到子区域内没有实例时终止（终止时的结点为叶结点）。在此过程中，将实例保存在相应的结点上。

放到地图上可以化简为，只包含经度、维度的二维空间，依次按照经度纬度(竖一刀横一刀)切分空间,
假设有以下点集:

(41.9483,126.4145),(45.3228,126.4956),(34.0173,113.8261),(29.6967,113.8800),
(36.6535,117.0389),(23.1248,113.6023),(46.3041,128.9676)

构造出kd树如下

kd树构造

空间划分结果如下

空间划分

检索周边

查找(38.9483,116.4145)附近一定距离的点

1. 迅速搜索到这个点位于(36.6535,117.0389)点构成的空间。左右都可能存在符合要求的点
2. (34.0173,113.8261)的下面空间不会包含目标点，于是过滤掉，放弃搜索。
3. (41.9483,126.4145)右边的空间不会包含目标点，放弃搜索

具体过程：首先找到包含目标点的叶结点；然后从该叶结点出发，依次回退到父结点：如果父结点的另一子结点的超矩形区域与圆相交，那么在相交的区域内寻找目标点。。

点查找

过滤规则：只需计算与上一级空间点相同经度或者相同纬度下距离是否小于目标距离。这里我们采用了化简后的距离函数，参见地理空间距离计算优化

检索区域

检索某个区域内的用户，只需将圆换成矩形，先查询到矩形内的所有点，然后利判断一下点是否在区域内。

Ray casting algorithm

以用户所在位置为起点，往右边（或左边）发出一条射线，计算该射线与多边形各个边的交点，如果交点个数是奇数则在多边形内部，否则在外部。

附近用户

对附近活跃用户有如下定义:最近30分钟内在门店附近打开应用的用户。需要保留历史记录，如果一个用户29分钟前在周围出现过，但是15分钟前就离开了，那么仍然算是周围用户，也就是说要保留历史状态，用户去过哪儿都可以查到。

周边用户效果图

项目为java项目，基于spring-quartz:

@Scheduled(cron = "0 0/10 * ? * *")

每十分钟触发一次，新建一颗新的索引树，将current指向它，并判断一下，最旧的二叉树是否应该丢弃，检索附近用户化简为检索3棵kd树。

我的顾客

某些poi对应30多万设备，总体近60G空间，且还会继续增长，如何查询某poi购买过的顾客，比较困难，如果扫描到周边用户之后再发起一万次请求判断是否是新客，显然不行。

解决方案：基于lsm思想实现了一个简易的kv存储，保存(poi,购买顾客列表)，直接放在本地磁盘，将求老客转化为求交集。

周边用户分布

简单的采用了k-means进行空间聚类，一定程度上反映了用户分布情况，缺点是聚类效果不够稳定。

取得效果

检索附近用户时总量500w记录 延达到2ms以内。

关键代码

关键代码 summer