论文部分内容阅读
在数据库研究领域中,连续K近邻查询处理技术是受很多学者关注的一个问题,它在实际生活中有很多应用,比如交通调度控制、数字战场、个人位置服务等系统都要对移动用户的相关位置或轨迹信息进行管理,然而在这些应用中管理连续K近邻查询服务的空间数据和空间对象的访问等都被限制在空间网络中,比如在路网中。而一些存在的查询处理方法对于动态查询处理问题是无法解决和直接使用的,需要研究适合动态环境下的连续K近邻查询处理技术。因此,路网中移动对象连续K近邻查询处理也是实际应用的迫切要求,研究如何提供各种高效的路网移动对象查询处理技术是具有一定的研究价值和实际应用价值。在现有的移动对象数据库索引和查询处理技术等方面的最新成果基础上,从移动对象运动轨迹和模式分析入手,对空间索引技术、动态环境下不确定性对象处理技术以及K近邻查询处理方法进行了深入研究,针对在连续K近邻查询处理技术中存在的问题,提出解决方案,进一步提出了路网中移动对象的连续K近邻查询处理技术和不确定性对象的索引方法,以解决实际位置服务查询应用系统中的关键技术问题。具体的工作和创新点包括如下:由于数据对象在路网中频繁而任意移动,对象位置的频繁更新使得准确和有效地处理连续K近邻查询是很复杂的。为了解决这个问题,本文根据移动对象和查询点之间的相对移动状态,提出了一个移动状态(Moving State of Object,MSO)模型,表示出移动对象与查询点的移动状态。在这个模型的帮助下,提出了一个新的候选对象处理(Object Candidate Processing,OCP)算法,用剪枝阶段和精炼阶段可以极大减少重复查询代价,并通过模拟实验进行了证明。在一些应用中(比如:当我在行走时找到接下来5分钟内离我最近的出租车),它是不需要获得准确的结果集。对于这些应用,介绍了一个新颖的技术,基于移动状态的近邻连续K近邻查询处理(Moving state based ApproximateCKNN,MACKNN),首次描述了一个不定对象的移动状态(MSUO)模型,通过移动对象和查询点的速度区间提出一个移动度方法来决定对象与查询点之间的移动状态。在MSUO模型的帮助下,提出的MACKNN技术由两个阶段组成,它们是剪枝和精炼阶段,剪枝阶段用来通过计算在给定时间区间内移动对象与查询点q之间的距离去剪掉不合格的对象。精炼阶段是设计来确定时间子区间,在这个子区间内查询结果是一定的。实验结果显示就运行时间和准确度而言,我们的方法更优于CKNN和IMA算法,并保持一定的准确程度。为了处理实际应用中不定速度的移动对象查询处理,研究了在所给时间区间内路网中不定速度的移动对象上处理CKNN查询的问题,提出了一个距离区间模型(DIM)来计算在一个时间点上以不定速度和方向运动的一个移动对象的距离区间,它主要包括一个移动对象与查询点之间的最小和最大距离。同时为了有效处理移动对象信息更新,提出了一种有效的移动对象索引方法,称为TPRuv-树,在DIM计算方法和TPRuv-树的帮助下,提出了一个PVKNN算法有效地处理CKNN查询。PVKNN算法的剪枝阶段用来剪掉那些在所给时间区间内不可能是查询结果的对象,然后设计了一个蒸馏阶段,确定所给时间区间的划分时间子区间,在这个子区间内不合格的候选对象被蒸馏掉,同时移动对象与查询点之间的最小和最大的距离也能用一个时间的线性函数来表示。最后,描述了一个可能度排序阶段,用可能度为每一个时间子区间确定KNN查询结果。