面向空间兴趣区域的路线查询

摘要

广泛的位置感知应用产生了大量的空间文本数据,其中既包含位置信息,也包含空间文本属性.为了利用这些丰富的信息来描述用户对路线的偏好,提出了面向空间兴趣区域的路线查询(region of interests oriented route query, ROIR).给定空间关键字集合及路线长度约束,ROIR检索满足长度约束和最高收益的由空间兴趣区域组成的路线.与传统的空间关键字路线查询相比,ROIR的对象由空间兴趣点扩展为兴趣区域,增加了用户的选择空间,使得查询结果的适用性更好.针对多种类型的海量空间兴趣点(point of interests, POI)及相关文本信息,设计了2层数据组织模型,模型中集成了POI对象的空间位置、关键字及POI对象间的转移关系.基于2层数据组织模型,提出了综合空间对象位置、转移图以及关键字3类信息的索引结构,同时预计算了关键字的收益统计值,并以签名方式存储在转移结点上.设计了ROIR路线查询精确算法.ROIR是一个NP难问题,为了有效地实现ROIR提出了近似率为1/ε的近似算法.利用真实数据集进行了详细的实验分析,评估了所提出算法的有效性.