LBS应用的兴趣点与名称搜索应用的兴趣点与名称搜索
摘要:目前LBS应用已在智能手机中占据了主导地位,但LBS技术覆盖范围太广,很少有能深入描述LBS技术的资料。
所以作者在《程序员》杂志开辟专栏来描述LBS核心技术,本文为该专栏的第五篇。
目前LBS应用已在智能手机中占据了主导地位,但LBS技术覆盖范围太广,很少有能深入描述LBS技术的资料。所以作
者在《程序员》杂志开辟专栏来描述LBS核心技术,本文为该专栏的第五篇。
我们知道,美团与大众点评的涉及30亿美金的重量级合并是非常的吸引眼球的。在这一场合并中,美团主要看重的是
大众点评的门店POI(Point of Interest,用户感兴趣的点的统称)数据。大众点评拥有1700万门店POI数据,比美团
POI数据多2倍。在美团的800万POI数据中,有团购交易的商户接近150万左右,POI到交易的转化率很高。而大众点
评的POI的转化率虽然没有美团高,但也是美团眼中的香饽饽。成了这场合并的重要筹码。
既然POI这么重要,那么,POI如何设计?又如何用于检索呢?
POI系统的设计
大众点评当年得到POI的方法是很笨的,是派人去“扫街”来采集POI,即:外业人员到商铺门口去采集,并利用GPS确
定位置,内业人员将外业采集得到的数据更新到地理数据库。这种方法和高德/四维图新等图商的POI采集方法是相同
的。
在采集POI完成后,下一步是设计POI系统。POI系统设计的核心就是加快POI数据的检索。为了实现POI的快速检索,
可以对POI系统建立精细设计的存储及获取的架构,也可以对数据进行线性排序,也可以建立空间索引(参见本系列第
一期《LBS数据的空间索引方法》(《程序员》10月B刊))。
【POI系统的存储及获取】
POI的名称由于可以重复,所以为了减少存储的容量,提高检索的速度,可以对所有的名称进行统一存储。这样,可以
许多的POI对应一个名称,就减小了POI名称的存储容量。
与名称相同,由于POI的图标也可以重复,所以为了减少存储的容量,提高检索的速度,可以对所有的图标进行统一存
储。一幅地图数据存储不到100个图标就满了,而POI只需要有一个对图标的引用即可。
POI除了一般信息外,就是其深度信息了。一般信息就是商铺的名称或者电话等常见信息。深度信息如:店铺的评价、
店铺的营业时间,或者地图中需要更新的数据(如从网络得到的POI数据)等。可以想象,未来的地图数据必然是互动
的地图,也必然是联网的地图。所以,未来的地图数据中有可能很大一部分是互动的深度数据,比如从其他网站(淘
宝、天猫)得到的深度信息。这一点实际上百度和高德等已经在实施,百度的很多数据是靠爬虫从网页中爬来的。高
德的很多POI的数据也是从淘宝/天猫得到的。
【线性排序】
如果把所有的几何类型归结为:点、线、面数据。那么,POI显然属于点类型。
点的设计可以非常简单,比如:可以只考虑做一个有经纬度的点到地图上就可以,也可以进行更精细的设计,除了建
立更好的空间索引来检索外,也可以对点进行排序,以便能更快速地对点进行检索。
对点进行排序的方法主要有两种:希尔伯特曲线排序和Z排序。这两种排序方法都可以用来对POI进行排序,从而缩短
名称搜索所需的时间。
希尔伯特曲线排序
希尔伯特曲线是一种能填充满一个平面正方形的分形曲线(空间填充曲线),由数学牛人大卫·希尔伯特在1891年提
出。
由于它能填满平面,它的豪斯多夫维(Hausdorff-Becikovich Dimesion,目前主流的拓扑维度的度量)是2。
希尔伯特曲线本质上显现了一种排序,这种排序的L系统记法如下。
变量:L、R
常数:F、+、?
规则为:
L → + RF? LFL? FR+
R → LF+RFR+FL
其中,F表示向前;?表示右转90°;+表示左转90°。
排序的步骤如图1所示。