论文部分内容阅读
近年来,随着基于位置服务的发展以及智能设备的普及,空间查询技术已经深入到日常生活中。然而当今的查询技术已经不仅仅局限于我们所熟知的近邻查询。为了更贴近实际应用,移动查询、多样性敏感的查询逐渐被作为研究的内容。然而,在现有的研究当中,移动查询相关的研究只涉及近邻查询没考虑多样性,多样性相关查询只有快照查询不能很好的解决连续查询。针对上面存在的问题,本文对多样性敏感的移动k近邻查询技术进行了研究与算法上的实现。在提出移动查询算法之前我们先形式化的定义了一个多样性与相关性的打分函数,通过它可以判断一个集合的得分,得分最高的集合可以作为查询结果。随后介绍了两个多样性敏感的kk近邻查询算法。一个为准确的查询算法,另一个为二倍近似的查询算法。针对两个多样性敏感的查询算法提出了三个多样性敏感的移动查询算法。首先,基于准确的查询算法提出了准确的维护查询结果的1-DMkNN算法。本文定义了活动半径的概念,通过它来维护一个队列中结果集的排序,并从队列头部得到查询结果。在此基础上,我们又提出了结果不变区域和队列有效区域来进一步的优化查询,使得查询时间进一步得到提升。此外,由于准确算法的执行之间比较长,我们提出了一个基于多样性值的上界的剪枝算法,并通过大量的实验验证了 1-DMkNN算法的有效性与准确性。其次,基于准确的查询算法提出了近似维护查询结果的ρ-DMkNN算法。我们通过一系列的几何证明得到了移动查询的安全区域,保证了安全区域内的查询结果满足ρ倍的近似度。而且安全区域的建立只依赖于当前的查询结果。文中通过大量实验验证了ρ-DMkNN算法的有效性与准确性。最后,基于近似的查询算法提出了准确维护查询结果的2-DMkNN算法。该算法的查询结果满足2倍近似比。算法在维护查询结果的过程中使用了队列和活动半径。通过查询点的移动距离与活动半径的大小关系来调整队列中点对直线的相对顺序,并且每次查询时通过队列中保存的点对来组成查询结果。文中通过大量实验验证了2-DMkNN算法的有效性与准确性。综上,本文结合了移动查询与多样性敏感的相关查询,提出了三种维护多样性k近邻查询的算法,可以在查询点移动的过程中维护查询结果的多样性。并通过大量的实验验证了本文算法的有效性与准确性。