论文部分内容阅读
近年来,随着基于位置的服务(LBS)和物联网的快速发展,空间查询技术作为重要的支撑技术进而越来越重要,而空间查询中的最近邻查询及其各种变体有着广泛的应用,如范围查询、k近邻查询、skyline查询、反k近邻查询等。在这些查询中,反k近邻查询用来获取那些k最近邻里包含查询q的空间数据点,在空间决策支持、资源分配和数据挖掘方面有着广泛的应用。近几年已有较多对于查询前k个反最近邻对象的研究,其中大部分针对的都是理想欧式空间和路网空间。而在真实情况下,反k最近邻查询通常受到障碍物的影响,例如建筑物、湖泊等。针对上面提出的问题,本文对障碍空间内的反近邻查询技术进行了研究。首先,针对障碍空间中障碍物的不可见性和查询点的快照性及固定性,本文形式化定义了在障碍空间中的反k最近邻固定点查询,并针对此问题提出了一种基于障碍Voronoi图的高效的剪枝方法。实验验证了本文所提出的ORkNN算法在高效性和准确性上的优越性。其次,本文针对查询点为用户动态给定的情况下,对上面提出的问题进行改进,定义了障碍空间中的反k近邻动态点查询问题,由此提出了ORkNND算法,即使用网格索引及有效剪枝方法将动态给出的查询点定位,然后在定位后的查询点处局部构造新的障碍Voronoi图单元,最后使用上面提出的固定点查询算法的剪枝和更新策略进行障碍反k近邻查询。大量实验证明了该算法的有效性和高效性。最后,本文考虑到用户发出查询时的移动连续性,针对上面研究查询点的问题,这里提出了将查询点增至查询线段上的障碍空间的连续反k近邻查询问题。本文研究了查询点变成线段后,解决求控制点和分割点的问题,然后对结果集进行更新。实验评估了本文所提出的CORkNN算法的有效性和准确性。总之,本文从越来越接近实际应用的障碍空间中的反k近邻查询的典型特征和挑战出发,针对障碍空间中的反k近邻的关键技术展开研究,如基于障碍Voronoi图、网格的数据结构进行点查询技术,预处理技术、控制点和分割点划分技术等,从而提供高效健壮的障碍空间中反k近邻查询处理方法。本文的研究工作所使用的数据结构和剪枝更新策略将为相关课题的开展打下了坚实的基础。