论文部分内容阅读
随着地理定位技术的快速发展,空间信息检索在许多应用程序中起着非常重要的作用,空间关键字查询也成为近几年数据库领域的研究热点,查询时同时考虑查询点与对象之间的位置相关性和文本相关性。考虑到人们的日常生活是沿着路网轨迹进行的,学者们对空间关键字查询的研究已经从欧式空间逐步扩展到路网上来了。此外,用户有时候要查询的不是当前位置周边的对象,而是与当前位置有一定距离的对象。因此,为了满足用户的这一需求,本文对路网上范围受限的空间关键字查询进行研究。首先,针对用户希望所有需求由一个对象满足的这种情况,提出路网上范围受限的top-k空间关键字查询算法。本算法返回在约束范围R内,满足所有关键字要求且距离查询位置最近的前k个对象。为了提高查询速率,算法为路网中的对象建立带倒排表的网格索引,查询时利用网格可有效锁定约束范围R,除此之外,算法还利用标签计算对象与查询点之间的最短路径距离。其次,针对用户的需求需要多个对象才能满足的情况,对路网上范围受限的集合空间关键字查询进行研究。查询过程中同样利用带倒排表网格索引和标签技术来提高效率。除此之外,由于该查询是一个NP完全问题,本文分别提出一个近似算法和一个精确算法来解决此问题,并将近似算法与精确算法查询的结果做了对比。最后,通过在真实的路网数据集上进行实验和测试,验证本文所提算法的有效性和准确性。