论文部分内容阅读
POI(Point of Interest)搜索(用户兴趣点搜索)就是在互联网环境中搜索含有用户感兴趣的位置信息的技术,相对互联网的其他搜索技术而言,POI搜索是本地搜索。随着位置服务技术的拓展,POI搜索将搜索延伸到日常生活中,成为网络用户出行查询的主要工具。POI搜索基于关键字和空间进行信息整合,相比传统搜索引擎增加了空间信息处理的开销。而手机搜索屏幕小、4×3键盘操作繁琐,不能照搬PC(Personal Computer)搜索模式,因此需要进一步探索手机地图搜索的应用模式。
本文从索引结构、索引过滤、查询评估及排序算法等角度出发提高POI搜索性能。同时,为了提高手机用户体验,结合手机搜索的特点及POI数据的结构性特征,提出了简拼POI搜索。本文主要研究成果如下:
1、设计了简单、高效的POI搜索引擎。相比商业POI搜索引擎,其在中文搜索基础上提供简拼搜索服务,并在指定城市搜索基础上支持指定多个类别的搜索。
2、提出了一种POI编码和索引过滤算法。该算法二分查找有序的倒排索引,按指定城市或城市与类别定位POI的范围,并完成索引过滤,时间复杂度为O(logn)+O(m)。
3、提出基于向量距离的词序相似度算法。采用向量空间模型表示简拼,将提取的公共简拼映射为位置向量,进而利用位置向量间的距离计算词序相似度。相比基于逆序数的算法,时间复杂度由O(nlogn)降为O(n),空间复杂度由O(n)降为O(l)。实验表明,该算法有效地保证了准确性,可以满足手机POI简拼搜索的应用需求,并将词序相似度的计算效率提高16.88%。
本文设计的POI搜索引擎已成功应用于通图门户(www.tongmap.cn)和上海城市手机路况查询系统中。测试及应用结果表明,它可以持续稳定的提供高效、准确的POI搜索服务,且具有负载可扩展性,成为织女星地理信息系统(VegaGIS)的基本服务构件之一。