基于3D^+-TPR-tree的点目标全时段移动索引设计

在经典3D R-tree基础上提出新的3D+R-tree索引,通过改变待索引数据项的结构并重新设计查询处理算法,减少包容矩形死区,提高查询效率;为了满足全时段查询要求,设计一种称为3D+-TPR-tree的联合索引结构,并对其中TPR-tree的参数包容矩形的调整算法进行优化。通过测试,证明3D+R-tree的查询效率明显高于普通3D R-tree;此外,测试结果也表明经过优化的参数包容矩形的调整算法也部分提升了TPR-tree的查询性能。

移动对象预测聚集范围查询方法

为了更好地实现预测范围聚集查询,提出了aTPRA-tree。TPR-tree随着时间的推移,性能不断恶化。aTPRA-tree是基于TPR-tree,它考虑了移动对象的方向角度进行构造,减小了结点面积和结点重叠面积,并且在索引结点中增加了聚集信息。实验结果表明,在更新和预测范围聚集查询性能方面,aTPRA-tree性能优于TPR-tree。

一种有效的时空连接算法

对空间数据库中静态数据集与动态数据集的连接问题进行了研究,提出了一种时空连接算法。该算法使用广度优先顺序对R-tree和TPR-tree进行同步遍历,在连接计算时,使用一种收紧MBR的剪枝策略对TPR-tree的节点进行剪枝,直到两棵树的叶子节点,最后计算R-tree每个叶子节点的最近邻。通过实验表明,算法有效解决了为静态数据集中的所有对象在动态数据集中查找到某个未来时间的最近邻的问题。

基于时空连续性的运动对象最近邻居查询

时空数据库中的运动对象最近邻居查询是NNQueries中的新问题,基于TPR-TREE索引结构的TPNNQueries算法能较好地处理对象的时态特性,但会多次查询同一对象。本文利用运动对象的时空连续性对TPNNQueries算法进行改进,通过一次查询TPR-TREE索引获取所有候选NN对象与查询对象的距离变化曲线,进而得到NN对象集,减少了查询及时空运算的次数。本文最后给出了实验分析。

时空数据库中多个最近邻对象的查询算法

在时空数据库中,最近邻查询用于对某个查询对象,在被查询对象中找出离它最近的一个或多个对象。该文在TPR树这一时空索引的基础上,提出了一种高效的最近邻查询算法,能够支持移动对象的多个最近邻对象的查询,并在性能上也有所提高。

基于速度分布的移动对象混合索引方法

TPR*树是目前广泛使用的移动对象当前及未来位置预测索引技术,但是其频繁更新及查询性能随着时间变化而急遽下降.文中提出了一种基于速度分布的移动对象混合索引HVTPR树,综合考虑移动对象在速度域和空间域中的分布,首先在速度域中对移动对象集进行规则划分,根据速度矢量大小将移动对象映射到不同的速度桶,每个速度桶中移动对象具有相近的速度矢量;对每个速度桶中的移动对象,则利用TPR树进行索引.HVTPR树索引增加了一个建于移动对象标识上的Hash辅助索引结构,并采用增强的自底向上更新(EBUU)算法以提高其频繁更新性能,具有很好的动态更新性能和并发性.实验表明,采用EBUU算法的HVTPR树索引动态更新及查询性能优于TPR*树等通用索引技术.

移动对象索引技术研究进展

在位置服务、交通控制等移动计算领域,移动对象索引技术广泛应用于对移动终端的空间位置进行存储和检索。本文深入分析了移动对象历史轨迹、当前位置和未来位置预测等各种索引技术,并根据索引空间及结构的不同对现有移动对象索引方法进行了详细的分类比较与讨论,对移动对象索引技术研究方向进行了展望。

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

针对基于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查询处理,具有良好的实用价值.

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

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

对象关系数据库中的时空索引机制研究

时空数据库是近年来地理信息科学与数据库技术领域研究和应用的热点,其中时空数据模型和时空数据索引技术是时空数据库的关键。为了提高时空数据库查询处理的效率,在基于时间片的连续快照模型基础上,改进了PP-TPR树索引。该索引技术不仅可以处理普通的空间查询(点查询和范围查询),在时间维度上还可以支持单纯时间维度的查询、历史状态查询、预期状态查询以及时空一体化的复杂查询。在实例研究中,采用对象关系数据库PostgreSQL作为时空数据类型和时空数据索引的实现平台,初步验证了上述时空索引技术的有效性和实用性。

球面上最近邻空间关系处理方法

根据球面上数据对象点的特征和空间数据库查询的需要,给出2种处理球面上最近邻查询的方法,即利用欧氏空间内的空间数据索引结构方法和球面投影于平面方法。在动态密集数据集和动态稀松数据集2种典型情况下分别对该2种方法处理最近邻查询的能力进行分析,结果表明,该2种方法能有效处理球面上具有不同性质特征的空间数据对象点的近邻查询问题。

基于扩展时空距离度量的连续k近邻查询方法

针对基于TPR树索引的连续k近邻查询,引入了一种新的时空距离度量最小最大距离函数作为TPR树索引搜索时节点剪枝上界。提出了一种采用最优优先策略的基于扩展时空距离度量的连续k近邻查询STM-CNN算法,利用最小距离函数进行TPR树索引节点搜索时访问排序,并使用最小最大距离函数对TPR树索引进行剪枝界定。

时空数据集的连接处理和优化方法研究

由于空间连接运算是空间数据库中最复杂、最耗时的基本操作,因此其处理效率在很大程度上决定了空间数据库的整体性能。目前空间连接算法基本上都是针对静态数据集的,而对于有动态数据集参与的空间连接问题研究还比较少。主要研究了静态数据集和动态数据集的空间连接问题,用R-tree和TPR-tree结构分别索引静态数据集和动态数据集。在连接中通过已经查找过的点,调整动态树MBR使筛选范围缩小,提高连接效率。

移动对象的连续最近邻查询算法

介绍了一种索引结构———TPR树和静态环境中基本的最近邻查询算法,并提出了影响时间这一概念,将其运用到最近邻查询算法中,可以完成移动对象的连续最近邻查询。

一种高效的船舶动态数据索引方法

随着船舶自动识别系统(Automatic Identification System,AIS)岸基通信网络的建立,可获得的船舶动态数据大幅增加。AIS数据具有数据量大和位置更新延迟的特点,容易造成检索耗时较多和误检索的问题。为解决以上问题,基于TPR*-tree建立船舶动态数据索引结构,解决船位和航速在索引结构中的存储问题,使用改进的闵可夫斯基和(Transformed Minkowski Sum,TMS)方法实现船舶动态数据的距离检索。为获取最优的检索效率,检索试验使用真实的AIS数据来确定各主要索引参数的最佳取值,并与已有算法在插入时间、检索时间和检索精度等3个方面进行了比较,通过比较结果可知,该索引方法能快速地对船舶动态数据进行插入和检索,且索引结果准确。

TPR^＊树索引构建及其动态维护方法

提出一种新的TPR*树索引构建方法,在根节点层利用速度矢量对移动对象集进行划分,根据速度矢量的大小将移动对象聚集到不同子节点中,并逐层构建TPR*树。在根节点层用溢出桶存储插入的移动对象记录,同时对TPR*树索引进行批量插入更新,以减少其插入更新维护的代价。实验结果表明,该方法是可行的。

移动对象的动态反向k最近邻研究

反向最近邻查询是空间数据库中最重要的算法之一。传统的反向最近邻查询方法主要是针对静态对象的查询,随着无线通讯和定位技术的快速发展,移动对象发出的查询请求成为新的研究热点。该文将TPR-tree作为算法的索引结构,并提出了基于矩形框的对角线的修剪策略,将半平面修剪策略进行改进,给出了移动对象的动态反向k最近邻的查询方案。

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

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

基于网格分组移动对象的索引方法

针对目前使用广泛的移动对象索引技术对受限范围内的海量数据索引管理问题.引入了网格技术实现移动对象的分组管理,提出了基于网格分组的移动对象GG TPR树索引方法.该方法利用网格分组的方式,将位置与运动行为接近的移动对象进行整体维护和批量管理,从而减少索引维护的中间环节,提高移动对象的索引效率.模拟实验结果表明,利用GG TPR树索引受限范围内的海量数据较已有的移动对象索引方法性能更优.

移动对象数据库中的索引机制

无线通信技术和定位技术以其显著的实用性和先进性成为近年来的热门研究课题 ,同时各种应用中对移动对象的定位和跟踪能力的要求也越来越高。在 R*树的基础上提出一种多维空间索引结构 TPR树 ,以实现对活动在 (或可能活动在 )某区域内的移动对象的快速查询。分析和解决了 TPR树在查询、插入、删除和适时更新等处理中存在的问题。