论文部分内容阅读
随着移动定位技术的发展以及便携式设备的普及,基于位置的地理信息服务(Location-Based Services)变得越来越受欢迎,空间文本查询能同时兼顾用户的位置信息和文本描述,相比于传统的空间查询更能满足用户的需要。典型的应用场景就是用户使用手机,在某个地理引擎中,提出自己的查询请求(用户当前的位置信息和文本描述信息),系统会查询到距离用户较近并且文本描述尽可能相似的k个空间文本对象。在这个问题上,已有大量的研究工作,但都主要针对于单个查询点(单源点)的空间文本Top-k查询问题(SSLkT),不能处理多个查询点的查询情形。基于上述问题,本文提出多源点空间文本Top-k查询(MSLkT),能够综合考虑多个查询点的空间位置信息和文本描述信息,从而给出总体最优的k个空间文本对象。本文的研究核心,主要是围绕着不同的空间距离度量(欧氏距离,道路网距离)来展开工作。 在欧式空间上,首先提出了阈值算法(TA),该算法先对每个查询点执行普通的空间文本Top-k查询,然后把每个查询点的结果合并,根据总体相似分值选出相似度最高的k个空间文本对象。然后,针对阈值算法会重复遍历索引结构的缺点,提出了更高效的MBR算法(MBRA)。该算法把所有的查询点视作一个的整体,统一执行空间关键字查询,同时利用最佳优先遍历思想(BF),进行高效的查询剪枝,减少对索引结构的访问。在道路网上,为了加快对道路网节点的访问速度,本文首先介绍道路网的组织与存储结构,然后介绍了道路网上针对单查询点的算法SSTopK,该算法基于Dijkstra的查询思想,由近及远一步步寻找距离查询点最近的空间文本对象,接着基于该算法提出了针对多查询点的MSTopK算法并对其进行了优化。最后,在两个不同的数据集上对本文所提出的算法进行实验评估,验证了本文所提出的算法的有效性。