基于更新日志的移动对象索引方法

在TPR-tree上增加一个基于内存的更新日志,实现一种支持频繁更新的移动对象索引ULTPR-tree,采用分组更新方法对移动对象记录进行批量删除,从而减少ULTPR-tree索引结构的删除维护代价。理论分析和实验结果表明,ULTPR-tree的动态更新性能优于TPR-tree和HTPR-tree。     

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

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

基于Quadtree和Hash表的移动对象全时态索引

为解决大量移动对象位置频繁更新所带来的性能下降问题,提出一种基于改进的Quadtree和Hash表的QH全时态索引结构。这种新的索引结构可以支持移动对象全时态索引,在Hash表中通过存储移动对象指针来支持移动对象标识查询,并对Quadtree的叶子节点采用适时合并的方法来防范分支太深而造成的查询效率低下。实验证明,QH索引与TPR-tree相比,移动对象的更新效率更高、对象标识查询较优、范围查询性能相近。     

移动对象位置预测的索引方法

当前对移动对象位置预测查询的研究中,索引结构的查询性能成为关注的热点,而忽视其更新代价。针对现有方法中存在的更新缺陷,本文以TPR-tree为基础提出两种索引方法（ETPR-tree和BiR-tree）。实验结果表明,采用辅助索引结构的BiR-tree具有最优的查询和更新性能。     

ATPR-Tree:带有属性维的时空索引

城市计算领域里所处理的移动对象往往带有除时间、空间信息外更多的信息,而目前的移动对象索引大多只有时间、空间这两个维度,不能有效地对附带更多信息的移动对象进行管理。基于这一问题,提出了一种带有属性维度的时空索引ATPR-tree,这种索引由TPR-tree改进而来。在TPR-tree节点CBR的基础之上新加入了属性值区间(RI)的概念;根据加入的RI属性维改变了TPR-tree的节点结构和代价目标函数;根据新的代价目标函数对插入、删除以及查询算法做出相应的改变。实验中所处理的移动对象是使用GSTD随机生成的,实验把附加属性作为索引一个维度的ATPR-tree和不作为索引的一个维度的TPR-tree进行比较。实验结果表明,对于带有属性值条件的查询,把属性值作为一个维度的ATPR-tree索引可以有效地减少节点访问次数,提高查询的效率。     

频繁更新移动对象的索引方法

在时空数据库中,频繁更新会导致TPR树更新与查询性能下降。针对该问题,提出MAH—TPR索引方法,分别对预处理过程、索引结构及更新算法进行优化。在构建索引及更新操作时,通过使用空间聚类来减少节点间空间区域的交叠几率。引入基于磁盘的Hash辅助存储结构,在直接访问叶节点的基础上进一步减少磁盘I／O的操作。引入基于内存的移动对象辅助存储结构,用于存储发出频繁更新请求,以避免主索引结构节点的合并和分裂。实验结果表明,MAH—TPR索引方法的查询性能优于HTPR方法和LGU方法,更新性能优于HTPR索引方法。     

支持频繁位置更新的不确定移动对象索引策略

移动数据采集和处理技术的迅速发展给研究人员提出了新的应用需求,如何在频繁位置更新应用中索引不确定移动对象的当前及未来位置信息成为当前的研究热点之一.TPU树是针对不确定移动对象的当前及未来位置信息索引的策略,其具有较高的概率域查询效率,但是其采用的传统自顶向下更新算法,存在频繁位置更新效率低下的问题.通过在TPU树上增加一个记录不确定移动对象状态特征的更新备忘录(UM)内存结构,文中提出了一种支持频繁位置更新的不确定移动对象索引策略TPU2M树,并在此基础之上提出了一种改进的基于备忘录(MMBU/I)的更新/插入算法.代价分析和实验仿真表明,采用MMBU/I算法的TPU2M树频繁更新性能大大优于TPU树和ABx树索引,且概率查询性能与传统索引大致相当,因此具有很好的实用价值和广泛的应用前景.     

移动点对象HR索引及反向最近邻查询

在此提出了一种基于速度分布的HR树索引结构,首先在速度域中对移动对象集进行规则划分,根据速度标量大小将移动对象划分到不同的速度树中,每棵速度树中移动对象具有相近的速度;对每棵速度树中的移动对象,则利用时间间隔进行划分。HR树索引增加了两个分别建于叶节点和根节点之上的Hash辅助索引结构,并基于HR树提出了反向最近邻查询算法,具有很好的动态更新性能和并发性。实验结果与分析表明,基于HR树索引的反向最近邻查询算法具有良好的更新及查询性能,优于通用的TPR树索引。     

移动点对象HR索引及反向最近邻查询

在此提出了一种基于速度分布的HR树索引结构,首先在速度域中对移动对象集进行规则划分,根据速度标量大小将移动对象划分到不同的速度树中,每棵速度树中移动对象具有相近的速度;对每棵速度树中的移动对象,则利用时间间隔进行划分。HR树索引增加了两个分别建于叶节点和根节点之上的Hash辅助索引结构,并基于HR树提出了反向最近邻查询算法,具有很好的动态更新性能和并发性。实验结果与分析表明,基于HR树索引的反向最近邻查询算法具有良好的更新及查询性能,优于通用的TPR树索引。     

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

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

Indexing mobile objects using dual transformations

With the recent advances in wireless networks, embedded systems, and GPS technology, databases that manage the location of moving objects have received increased interest. In this paper, we present indexing techniques for moving object databases. In particular, we propose methods to index moving objects in order to efficiently answer range queries about their current and future positions. This problem appears in real-life applications such as predicting future congestion areas in a highway system or allocating more bandwidth for areas where a high concentration of mobile phones is imminent. We address the problem in external memory and present dynamic solutions, both for the one-dimensional and the two-dimensional cases. Our approach transforms the problem into a dual space that is easier to index. Important in this dynamic environment is not only query performance but also the update processing, given the large number of moving objects that issue updates. We compare the dual-transformation approach with the TPR-tree, an efficient method for indexing moving objects that is based on time-parameterized index nodes. An experimental evaluation shows that the dual-transformation approach provides comparable query performance but has much faster update processing. Moreover, the dual method does not require establishing a predefined query horizon.Received: 27 April 2003, Accepted: 11 May 2004, Published online: 14 September 2004Edited by: J. VeijalainenGeorge Kollios: Supported by NSF CAREER Award 0133825.Dimitrios Gunopulos: Supported by NSF ITR 0220148, NSF CAREER Award 9984729, NSF IIS-9907477, and NRDRP.Vassilis J. Tsotras: Supported by NSF IIS-9907477, NSF EIA-9983445 and the DoD.     

移动对象数据库预测范围聚集查询技术研究

针对预测范围聚集查询处理技术,提出了一种面向移动对象的聚集TPR树索引。聚集TPR树索引在TPR树中间节点中加入移动对象聚集信息以减少预测范围聚集查询所需要的节点访问代价。并增加了一个建于移动对象标识上的哈希辅助索引结构以支持自底向上的删除搜索算法,具有很好的动态更新性能和并发性。提出了一种EPRA查询算法,采用更精确的剪枝搜索准则,大大减少了查询所需要访问的磁盘节点,具有良好的查询性能。     

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

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

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

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

Processing moving queries over moving objects using motion-adaptive indexes

This paper describes a motion-adaptive indexing scheme for efficient evaluation of moving continual queries (MCQs) over moving objects. It uses the concept of motion-sensitive bounding boxes (MSBs) to model moving objects and moving queries. These bounding boxes automatically adapt their sizes to the dynamic motion behaviors of individual objects. Instead of indexing frequently changing object positions, we index less frequently changing object and query MSBs, where updates to the bounding boxes are needed only when objects and queries move across the boundaries of their boxes. This helps decrease the number of updates to the indexes. More importantly, we use predictive query results to optimistically precalculate query results, decreasing the number of searches on the indexes. Motion-sensitive bounding boxes are used to incrementally update the predictive query results. Furthermore, we introduce the concepts of guaranteed safe radius and optimistic safe radius to extend our motion-adaptive indexing scheme to evaluating moving continual k-nearest neighbor (kNN) queries. Our experiments show that the proposed motion-adaptive indexing scheme is efficient for the evaluation of both moving continual range queries and moving continual kNN queries.     

基于U-tree的不确定移动对象索引策略

通过在U-tree中添加时间戳和速度矢量等时空因素,提出一种基于U-tree的高效率当前及未来不确定位置信息检索的索引结构TPU-tree,可以支持多维空间中不确定移动对象的索引,并提出了一种改进的基于p-bound的MP_BBRQ(modifiedp-bound based range query)域查询处理算法,能够引入搜索区域进行预裁剪以减少查询精炼阶段所需代价偏高的积分计算.实验仿真表明,采用MP_BBRQ算法的TPU-tree概率查询性能极大地优于传统的TPR-tree索引,且更新性能与传统索引大致相当,具有良好的实用价值.