论文部分内容阅读
GPS设备的迅速普及以及基于位置服务的快速发展,产生了大量带有文本信息的空间对象。面向集合的空间关键字查询(Collective Spatial Keyword Querying,CoSKQ)作为空间关键字查询的变种,成为了当前研究热点之一。本文提出并定义了一种新的面向集合的反向空间关键字查询(Reverse Collective Spatial Keyword Querying,RCoSKQ),在这种查询中,对于任意一个结果集中的用户,与其他同样覆盖查询关键字集的空间对象集相比,查询点集与该用户的空间相似性最高。但在RCoSKQ查询过程中,面临两个问题,第一,覆盖查询关键字集的空间对象集很多,需要高效的方法过滤掉不合格的对象集;第二,需要快速的方法从用户集中筛选合格用户。本文主要工作如下:本文首先提出了一种基于区域剪枝的查询算法。首先获取所有的集合关键字集,对于每个集合关键字集,分别以每个查询点为中心对空间进行划分。然后,对每个分区的空间进行剪枝,并生成分区影响集。最后,使用分区影响集筛选合格用户。取所有查询点的合格用户的交集,将所有集合关键字集的合格用户合并。其次,在基于区域剪枝算法的基础上,提出了一种基于半空间剪枝的查询算法。首先获取所有的集合关键字集,对于每个集合关键字集,计算集合影响区域;然后,利川集合影响区域筛选合格用户,返回该区域内的用户;最后,合并所有集合关键字集的合格用户。最后,本文使用两个真实的数据集和几个合成的数据集,设计合理的对比实验,研究不同参数对算法在响应时间和I/O cost方面的影响。实验结果表明,基于区域剪枝的查询算法能够有效地解决RCoSKQ问题,而基于半空间剪枝的查询算法更加高效。