检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

tpr-树性能优化研究

计算机工程与设计 2008年第20期29卷 5360-5363页

作者：金泽锋薛安荣江苏大学计算机科学与通信工程学院江苏镇江212013

为了降低tpr-树的时间复杂度、提高查询效率，提出结点分裂的改进算法及基于距离的结构调整策略。改进算法把TPBR（time-pararneterized bounding rectangle）在某时间段内的周长定积分作为代价函数，并在投影定积分值最大的轴上进行结... 详细信息

为了降低tpr-树的时间复杂度、提高查询效率，提出结点分裂的改进算法及基于距离的结构调整策略。改进算法把TPBR（time-pararneterized bounding rectangle）在某时间段内的周长定积分作为代价函数，并在投影定积分值最大的轴上进行结点分裂，做到了同时兼顾移动对象的空间属性与速度属性。在结构调整策略中通过删除结点中移动距离超过阈值的记录，从而使TPBRs的扩张速度变慢，在一定程度上抑制了TPBRs之间的重叠。实验结果表明，与原tpr-树结点分裂算法相比，改进后的结点分裂算法的运行时间降低了5～8倍，查询性能至少提高了50％，而且，在此基础上应用基于距离的结构调整策略使查询性能进一步提高约10％。

关键词：时空数据库预测索引 tpr-树 TPBR 查询性能

在线全文

学校读者我要写书评

暂无评论

tpr-树在基于位置服务系统中的应用研究

TPR-树在基于位置服务系统中的应用研究

作者：金泽锋江苏大学

学位级别：硕士

时空数据库技术是计算机科学的新兴领域。面对着海量的数据,如何在给定的空间及时间范围内实现对移动对象快速有效地查询,是实现定位服务、智能交通、数字化战争等诸多应用中迫切需要解决的问题。时空索引技术是解决上述问题的关键技术... 详细信息

时空数据库技术是计算机科学的新兴领域。面对着海量的数据,如何在给定的空间及时间范围内实现对移动对象快速有效地查询,是实现定位服务、智能交通、数字化战争等诸多应用中迫切需要解决的问题。时空索引技术是解决上述问题的关键技术。 tpr-树是一种可以对移动对象当前位置及未来位置进行有效索引的时空索引技术。tpr-树用TPBR(Time-Parameterized Bounding Rectangle)来近似表示对象,其基本算法和R-树类似。tpr-树不但支持对移动对象将来位置的预测查询,而且数据存储量和数据更新频率都相对较低。但tpr-树并没有得到广泛的应用,主要是因为其存在以下不足:对移动对象预测查询的精确度不高:TPBR之间的重叠随着时间的推移而越发严重,从而影响tpr-树的查询性能:算法的时间花费较高,不利于系统作出快速的响应。本文对tpr-树的性能优化进行了研究。首先介绍了时空索引技术研究方面的成果。接着,根据tpr-树的特性,设计一种可以实现实时查询以及预测查询的基于位置服务系统。然后分别从四个方面对tpr-树进行研究以及改进:(1)通过引入记录的生命期,过期记录(expired entries)不再被真正删除,只是简单记载过期的时刻,从而使tpr-树可以应答对移动对象历史信息的查询;(2)对tpr-树所索引的数据对象进行扩展,使得tpr-树可以管理更为一般的数据对象;(3)提出一种同时考虑移动对象的空间属性和速度属性的结点分裂算法,算法在投影定积分值最大的轴上进行分裂,并把某段时间内子结点周长的定积分作为代价函数,不但降低了算法的计算时间,而且使用此算法所建立的tpr-树的查询速度也得到了一定的提高;(4)一种可以限制TPBR之间无限重叠的基于距离的结构调整策略,该算法通过强制重插在某个方向上的移动距离超过阈值的移动对象所对应的记录,从而达到调整tpr-树整体结构的目的。实验表明,与原tpr-树结点分裂算法相比,改进后的结点分裂算法的计算时间降低了5～8倍,查询速度至少提高了50%:而且,在此基础上应用基于距离的结构调整策略使查询速度进一步提高约10%。

关键词：时空数据库索引空间位置预测查询 R-树 tpr-树基于位置服务

时空数据库中基于tpr～*树索引的更新策略研究

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

时空数据库中基于TPR～*树索引的更新策略研究

作者：刘兴集浙江大学

学位级别：硕士

时空数据库技术是计算机科学的新兴领域。在这个领域内,各种索引技术得到广泛研究和应用。随着基于定位服务数量和需要定位的移动设备数量的大量增加,在单位更新时间内索引要处理成百上千的更新操作。许多现代预测时空存取技术大多... 详细信息

时空数据库技术是计算机科学的新兴领域。在这个领域内,各种索引技术得到广泛研究和应用。随着基于定位服务数量和需要定位的移动设备数量的大量增加,在单位更新时间内索引要处理成百上千的更新操作。许多现代预测时空存取技术大多从Guttman提出的R树索引发展过来。虽然R树索引在商业中得到广泛应用和发展,但是它在频繁更新中低下的性能却引来了很多数据库索引技术的研究者的批评。本论文首先介绍了时空数据库技术概况和索引研究方面的成果。着重分析了两个最主要的基于R树的预测索引——tpr*树和tpr*树,介绍了它们基本索引操作方法及其在更新过程中的性能。这两个索引结构的插入、删除操作在执行过程中需要对索引结构进行多次代价颇高的遍历操作,这就导致了在频繁更新中较差的性能表现。基于此,本文提出了增强型自底向上更新tpr索引机制。本文研究和发展了Lee等人提出的自底向上更新机制,将其应用于tpr*树,提高了I/O及CPU效率。新的算法加入了四个辅助结构用来保存必要的信息以减少不必要的树遍历操作,解决了频繁更新中的性能瓶颈问题。实验测试表明了增强型自底向上tpr*树的更新在每次更新中的操作的磁盘存取次数比自顶向下的更新机制要减少三成以上,CPU时间也减少近20%。本文研究的主要创新点概括如下: ⅰ) 提出了使用四个辅助结构的增强型更新tpr*树索引机制,在频繁更新中的性能表现很好。 ⅱ) 使用自顶向下和自底向上的混合更新机制,在频繁更新中的性能提高中具有决定性的作用。 ⅲ) 使用了动态节点紧缩的机制。

关键词：时空数据库预测索引 tpr*树 tpr*树自顶向下自底向上 I/O CPU时间

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于缓存的tpr*树索引方法的研究

基于缓存的TPR树索引方法的研究

作者：曹亮燕山大学

学位级别：硕士

随着无线通信与GPS等空间定位技术的飞速发展,基于位置服务的移动对象数据库技术已远远不能满足用户日益增长的应用需求。现有的基于磁盘的移动对象索引技术主要包括对移动对象历史信息的索引和对移动对象当前及未来信息的索引。针对移... 详细信息

随着无线通信与GPS等空间定位技术的飞速发展,基于位置服务的移动对象数据库技术已远远不能满足用户日益增长的应用需求。现有的基于磁盘的移动对象索引技术主要包括对移动对象历史信息的索引和对移动对象当前及未来信息的索引。针对移动对象当前位置查询和未来位置预测的索引技术得到了国内外诸多研究者的广泛关注。本文在对国内外研究现状进行综合分析的基础上,进一步对支持当前及未来位置查询的索引技术进行了深入研究。首先,本文分析了M. L. Lee等人提出的自底向上的更新方法和廖巍等人提出的Htpr-tree索引结构。针对索引方法的更新局部性问题,结合已有的索引技术,提出了一种基于更新日志的移动对象索引结构ULtpr-tree。在移动对象连续更新变化范围增大的情况下,它不仅保证了查询性能,而且有效地提高了索引结构的动态更新性能。其次,在频繁更新情况下,位置的变化将引起大量更新的问题。本文通过在tpr-tree索引结构上增加基于磁盘的输入缓冲区和基于内存的输出缓冲区,提出了一种改进的移动对象索引结构Btpr-tree。它不但能够有效地支持tpr-tree索引结构的查询操作,而且有效地解决了在移动对象数据量大的情况下索引结构更新吞吐量低的问题。最后,通过实验测试,对上文提出的移动对象索引结构与现有的索引结构进行了分析比较。验证了ULtpr-tree和Btpr-tree索引结构在频繁更新环境下的有效性和实用性。

关键词：移动对象移动对象索引 tpr*树更新日志缓冲区吞吐量

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于tpr*树的索引技术研究

电脑知识与技术 2005年第36期 142-142页

作者：向科峰郑晓莉西南科技大学计算机学院西南科技大学制造科学与工程学院

分析了移动对象位置的索引技术,介绍了可以有效的索引移动对象的当前和未来位置的索引结构——tpr*树(time-parameterized R tree),并对其进行改进,改善了其查询性能。

关键词：移动对象时空索引 tpr*树

时空数据库中基于tpr-树的反向最近邻查询

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

哈尔滨理工大学学报 2007年第3期12卷 87-90页

作者：于海彦郝忠孝哈尔滨理工大学计算机科学与技术学院黑龙江哈尔滨150080

为研究动态环境下解决反向最近邻查询的算法,采用tpr-树索引结构给出了解决动态环境下的最近邻查询算法,并提出反向最近邻查询算法.该算法可有效解决平面上连续移动点的反向最近邻查询.

关键词：时空数据库反向最近邻查询最近邻查询 tpr-树

在线全文

学校读者我要写书评

暂无评论

基于双树双索引结构的移动查询方法

北京理工大学学报 2008年第11期28卷 993-997页

作者：梁野龚雪晶慈林林苏斐北京理工大学计算机科学与技术学院北京100081 中国石油信息技术服务中心北京100724

为实现对有限范围内海量移动对象的有效索引,构建通用的移动查询解决方案,针对移动对象在道路网格中的运动特点,提出了预测实时运动速度的速度积累模型和预测未来聚集位置的基于双树双索引结构的移动对象查询方法.双树双索引结构利用网... 详细信息

为实现对有限范围内海量移动对象的有效索引,构建通用的移动查询解决方案,针对移动对象在道路网格中的运动特点,提出了预测实时运动速度的速度积累模型和预测未来聚集位置的基于双树双索引结构的移动对象查询方法.双树双索引结构利用网格划分思想构建空间分割树,实现对现有GG tpr-tree查询结构的拓展,并结合GG tpr-tree索引及建立于内存中的Hash索引以满足各种类型的移动查询请求.仿真实验表明,在回答受限范围内海量移动对象的确定性查询和统计性查询时,与传统方法相比,双树双索引结构在查询结果准确率方面有明显的改善.

关键词：移动查询网格 GG tpr*树空间分割树双树双索引

在线全文

学校读者我要写书评

暂无评论

面向移动对象的高效预测范围聚集查询方法

计算机研究与发展 2007年第6期44卷 1015-1021页

作者：廖巍景宁钟志农陈宏盛国防科学技术大学电子科学与工程学院长沙410073

预测范围聚集查询是移动对象数据库中重要的查询类型之一.提出了一种PRA树高效预测范围聚集查询索引,对速度域进行规则划分,根据速度矢量大小将移动对象映射到不同的速度桶中,针对每个速度桶,提出了一种聚集tpr*树索引,通过在tpr*树中间... 详细信息

预测范围聚集查询是移动对象数据库中重要的查询类型之一.提出了一种PRA树高效预测范围聚集查询索引,对速度域进行规则划分,根据速度矢量大小将移动对象映射到不同的速度桶中,针对每个速度桶,提出了一种聚集tpr*树索引,通过在tpr*树中间节点中加入聚集信息以减少预测范围聚集查询所需要的节点访问代价.PRA树索引增加了一个建于叶节点之上的Hash辅助索引结构,并采用自底向上的删除搜索算法,具有很好的动态性能和并发性.提出了一种增强预测范围聚集查询EPRA算法,采用更精确的剪枝搜索准则,减少了查询所需要访问的节点代价.实验结果与分析表明,基于PRA树索引的EPRA查询算法具有良好的查询性能,优于通用的tpr*树索引.

关键词：预测范围聚集查询 PRA树 tpr*树 EPRA算法

在线全文

学校读者我要写书评

暂无评论

可伸缩的增量连续k近邻查询处理

软件学报 2007年第2期18卷 268-278页

作者：廖巍熊伟王钧景宁钟志农国防科学技术大学电子科学与工程学院湖南长沙410073

针对基于tpr*树(time-parameterized R-tree)索引的大量并发CKNN(continuous k-nearest neighbor)查询处理,提出了一种可伸缩的增量连续k近邻查询处理(scalable processing of incremental continuous k-nearest neighbor queries,简称SI-CNN)框架,通过引入搜索区域进行预裁剪以减少查询更新所需要的tpr*树节点访问代价,并引入了增量结果表以保存候选对象,批量地更新查询结果集,具有良好的可伸缩性.基于SI-CNN框架提出了一种增量更新的SI-CNN查询处理算法,能够基于上次查询结果增量的更新查询,支持查询集合中加入或删除查询和移动对象数据集的插入、删除等动态更新操作.实验结果与分析表明,基于SI-CNN框架的SI-CNN算法可以很好地支持大量并发的CKNN查询处理,具有良好的实用价值.

关键词：连续k近邻查询 tpr*树 SI—CNN框架 SI—CNN算法增量处理