路网中考虑运动状态的连续K近邻查询算法研究

来源 :华中科技大学 | 被引量 : 0次 | 上传用户:jiangjia09
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
在数据库研究领域中,连续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查询结果。
其他文献
本文对有序二元决策图(ordered binary decision diagram,OBDD)进行了泛化,提出了一种新的知识编译语言—带蕴含文字的有序二元决策图(OBDD with impliedliterals,OBDD-L)。本文将OB
随着时代的发展,人们渴求知识愈加强烈,高校学生对图书的范围要求更广泛一些,在阅读选择上有更强的目的性与自主性,为此,作为提供阅览的地方--图书馆应以科学管理办法,加强和完善图
历史是人类灵魂的凝结。历史文化名城是历史的记录与再现,是民族最宝贵的资源。保护好历史文化名城,发展好历史文化名城,是后来人应永恒关注的课题。本文以安庆市历史文化保
目的:多发性硬化(Multiple Sclerosis,MS)是一种累及中枢神经系统(CNS)的慢性炎性脱髓鞘性疾病,其发病机制尚不明确。研究表明,氧化应激和线粒体损伤在MS的发病机制中起重要
本文应用人机工程学的研究方法和模糊数学理论,从人-机-环境系统的概念出发,提出评价建筑机械产品人机工程学质量的数学模型,为解决建筑机械在新产品设计方案择优、老产品改
城市轨道交通中乘务培训管理工作是乘务管理的基础,特别是新地铁在面对新设备、新环境的条件时,如何对新人员实施高效培训是乘务管理工作的重中之重。文章对青岛地铁乘务部近
<正> 混凝土在搅拌、运输及浇灌的各个阶段,总是与加工及运输的工作机构处于接触之中,它在这些机构的表面上残留的堆积物与日俱增。由于部份混疑土附积在工作机构的表面上,使
档案管理是党校建设与发展的重要内容之一,决定着党校的管理水平。党校的档案记载着党校的发展史、教学成果和教育工作者对党校的付出,是党校具备的宝贵财富,具有神圣不可逾越的
<正> 各种电阻应变仪是测量受力结构材料应变的专用仪器。为了保证测量结果的准确度和可靠性,电阻应变仪必须每年定期检定。考核仪器误差是否符合说明书规定的误差范围,以便
随着高等教育改革的深化,高校中家庭经济困难学生的数量不断增加,虽然国家高度重视大学生资助工作,资助力度不断增强,部分贫困生的经济困难得到了有效缓解。但是,由于高校目前的资