在工程实践中需要解决以下问题: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树如下
空间划分结果如下
检索周边
查找(38.9483,116.4145)附近一定距离的点
- 迅速搜索到这个点位于(36.6535,117.0389)点构成的空间。左右都可能存在符合要求的点
- (34.0173,113.8261)的下面空间不会包含目标点,于是过滤掉,放弃搜索。
- (41.9483,126.4145)右边的空间不会包含目标点,放弃搜索
具体过程:首先找到包含目标点的叶结点;然后从该叶结点出发,依次回退到父结点:如果父结点的另一子结点的超矩形区域与圆相交,那么在相交的区域内寻找目标点。。
过滤规则:只需计算与上一级空间点相同经度或者相同纬度下距离是否小于目标距离。这里我们采用了化简后的距离函数,参见地理空间距离计算优化
检索区域
检索某个区域内的用户,只需将圆换成矩形,先查询到矩形内的所有点,然后利判断一下点是否在区域内。
以用户所在位置为起点,往右边(或左边)发出一条射线,计算该射线与多边形各个边的交点,如果交点个数是奇数则在多边形内部,否则在外部。
附近用户
对附近活跃用户有如下定义:最近30分钟内在门店附近打开应用的用户。需要保留历史记录,如果一个用户29分钟前在周围出现过,但是15分钟前就离开了,那么仍然算是周围用户,也就是说要保留历史状态,用户去过哪儿都可以查到。
项目为java项目,基于spring-quartz:
"0 0/10 * ? * *")
(cron =
每十分钟触发一次,新建一颗新的索引树,将current指向它,并判断一下,最旧的二叉树是否应该丢弃,检索附近用户化简为检索3棵kd树。
我的顾客
某些poi对应30多万设备,总体近60G空间,且还会继续增长,如何查询某poi购买过的顾客,比较困难,如果扫描到周边用户之后再发起一万次请求判断是否是新客,显然不行。
解决方案:基于lsm思想实现了一个简易的kv存储,保存(poi,购买顾客列表),直接放在本地磁盘,将求老客转化为求交集。
周边用户分布
简单的采用了k-means进行空间聚类,一定程度上反映了用户分布情况,缺点是聚类效果不够稳定。
取得效果
检索附近用户时总量500w记录 延达到2ms以内。
关键代码
关键代码 summer
相关推荐
随着地理信息数据获取技术日渐完善,地理信息数据在遥感领域应用的不断深入,人们对海量地理...论文分析并探讨了Vue在地理信息检索系统应用的可行性及实现方法,并证明了Vue的优势可在地理信息检索系统得到有效的利用。
温州平阳县测绘地理信息检索云服务平台构思与试验分析.pdf
电信设备-基于用户视野的地理信息检索和导航系统.zip
针对当前定量化的地理信息检索模型无法有效处理自然语义导致检索结果不理想的问题,以语义匹配为原则,以定性表达为基础,以推理方法为手段,提出基于定性空间推理的定性地理信息检索的方法及其形式化模型,实现Web...
#资源达人分享计划#
同时向地理信息消费者(信息最终用户)提供多媒体地理信息检索服务、地理信息导航服务(分类分级导航、人工索引检索式导航、自动索引检索式导航)。 该系统的核心包括全省信息查询(含地理风貌、环境气候、名胜古迹...
基于ElasticSearch全文检索的农业地理信息大数据平台设计与实现
该方法不确定文档的地理范围,而是分别计算文档中出现的每个地名与查询范围的相关性,以减小文档中不相关地名对检索结果的影响。实验表明,基于文档地名感知的方法的检索效果优于确定最小边界矩形的方法和基于tf-idf...
XZ-Ordering_A_Space-Filling Curve.pdf XZ-Ordering是一种空间填充曲线,...* 地理信息检索 * 数据挖掘和数据分析 XZ-Ordering曲线是一种高效的空间填充曲线方法,具有广阔的应用前景,能够满足空间信息系统的需求。
浙江大学地理信息系统教材 一、绪论.doc 二、地理空间的表达.doc 三、空间数据的转换.doc 四、空间数据的处理.doc 五、空间分析功能&地图信息的检索与查询.doc 六、地理信息系统的开发和应用.doc 七、地理信息系统...
电信设备-基于MIML的OGC地理信息服务语义检索方法.zip
1.1 地理信息系统的基本概念 地理信息系统(GIS)是在计算机软硬件支持下,以采集、存贮、管理、检索、分析和描述空间物体的地理分布数据及与之相关的属性,并回答用户问题等为主要任务的技术系统。 1.2 地理信息...
网络游戏-融合地理信息与视觉信息的网络新闻检索系统及方法.zip
信息系统的种类包括管理信息系统、地理信息系统、指挥信息系统、决策支持系统、办公信息系统、科学信息系统、信息检索系统、医学信息系统、银行信息系统、民航订票系统等。 信息系统的发展趋势包括: 1. 系统集成...
电信设备-地理对象信息检索方法与装置.zip
本资源为地理信息系统试题含答案,涵盖了地理信息系统的多个方面,包括数据库模型、空间数据模型、MapGIS操作、矢量数据结构、栅格数据模型、等高线生成等知识点。 知识点一:数据库模型 * 层次数据库模型、网络...
基于ElasticSearch全文检索的农业地理信息大数据平台设计与实现.pdf
地理信息系统的功能包括数据输入、存贮和编辑、操作运算、数据查询和检索、应用分析、图形显示和结果输出、数据更新等。地理信息系统的应用包括统计与量算、规划与治理、预测与监测、辅助决策等。 地理信息系统的...
《福州之窗》城市多媒体地理信息系统采用北京超图地理信息技术有限公司的全组件式GIS 软件SuperMap Objects 作为开发平台,充分利用组件式地理信息系统的灵活性、可扩展性和易开发性...