移动对象数据库索引研究综述

对近年来移动对象索引技术的发展进行了总结。根据移动对象索引空间的不同,将移动对象索引分为无限制空间移动对象索引以及网络空间移动对象索引,分析了过去、现在、未来移动对象索引技术的发展情况,最后对移动对象索引未来发展方向进行了讨论。     

基于TPR树的索引技术研究

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

基于TPR树的索引技术研究

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

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

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

XBR树:一种基于四叉树的空间对象移动路径索引结构

地理信息系统(Geographic Information System,GIS)重要的研究课题之一就是有效跟踪移动空间对象,这个研究方向是与当前快速发展的移动应用密切相关的,这是因为只有很好地研究移动空间对象索引技术,才能够满足用户各种空间、范围、时空等类型的查询需求.在本文中主要讨论了一种被称为(External Balaced Regular trees-XBR trees)[1,11]的移动空间对象数据库索引结构,采用XBR树索引能够有效支持区域查询,尤其是在关于移动空间对象历史移动路径查询上,能够有效提高系统效率.     

一种基于BX树的移动对象混合索引方法

为实现移动对象当前及未来位置索引,提出了一种自适应SABX树（Self-Adapt BX-tree）,考虑到移动对象在现实世界中分布密度不同的特点,利用时间划分和空间填充曲线技术计算移动对象位置信息,并引进了一个以秩的范围为标识的Hash辅助索引表,文中给出了SABX树的插入、删除、更新方法以及范围查询算法。实验表明,该索引结构的动态更新性能和查询效率优于BX树和传统的TPR树。     

基于移动对象运动模式构建的空间索引结构

由于实时跟踪移动的空间对象需要不断地查询和更新空间数据库的索引，经典R树空间索引结构的静态管理空间对象的方法并不适合移动环境，从而导致系统执行效率非常低下。根据对移动对象运动模式的分析，文中提出了一种称为ASI（Adaptive Spatial Index based on Motion Characteristic of Moving Objects）的移动空间对象索引结构，阐述了该索引结构的核心算法、构造方法、具体的数据存储方案，最后给出了该索引结构的试验分析结果。     

基于GPS车辆跟踪系统的移动对象数据库应用研究

本文结合GPS车辆实时跟踪应用系统,利用移动对象数据库技术,对移动车辆的运动空间及时间进行分割,建立了移动目标数据库的数据模型、数据结构以及索引结构,实现实时更新车辆位置信息,有效地回放移动车辆的历史行驶轨迹,预测车辆将来的运动路线。     

一种基于二层网格的移动对象B+树索引

在已有的基于空间分割的移动对象B+树索引基础上,提出一种分割空间的新方法,对空间进行二层网格分割,使空间分割很好地解决由移动对象在空间中分布不均造成的索引效率下降的问题。给出基于这种索引结构的Range查询和kNN查询算法。实验结果表明, 该索引结构的性能基本不受移动对象分布的影响。     

基于移动对象运动模式构建的空间索引结构

由于实时跟踪移动的空间对象需要不断地查询和更新空间数据库的索引,经典R树空间索引结构的静态管理空间对象的方法并不适合移动环境,从而导致系统执行效率非常低下。根据对移动对象运动模式的分析,文中提出了一种称为ASI(Adaptive Spatial Index based on Motion Characteristic of Moving Objects)的移动空间对象索引结构,阐述了该索引结构的核心算法、构造方法、具体的数据存储方案,最后给出了该索引结构的试验分析结果。     

时空数据库索引技术研究

对时空数据库中移动对象进行有效存取、查询和更新的关键技术在于索引。深入分析了时空数据库中的各种索引技术,最后讨论了移动对象索引技术研究中的问题并对未来方向进行了展望。     

一种基于固定网络的移动对象运动轨迹索引模型

实际应用中移动对象通常运动在城市固定道路上,针对此特征研究人员已提出一些相关索引模型,但都存在一定的局限性,表现为索引模型只管理对象的历史位置信息或实时位置信息以及只对窗口查询或轨迹查询进行优化.IMTFN是一种基于固定网络的移动对象运动轨迹索引模型,管理移动对象的实时位置信息和历史轨迹信息,并且有效优化窗口查询及轨迹查询操作.IMTFN由一个管理固定网络的2D R^＊-Tree、一组管理移动对象运动轨迹的1D R^＊-Tree以及记录移动对象实时位置信息的Hash结构组成.最后通过实验IMTFN分别与STR-Tree与FNR-Tree进行性能比较,证明IMTFN模型提供速度更快的查询操作.     

一种混合的时空数据库索引机制

近年来,时空数据库的应用得到迅速发展,在动态时空环境里,维持持续移动对象的位置信息是一个挑战。本文提出了一种新的索引机制,采用两种不同类型的索引结构,一种索引移动对象历史轨迹,一种能够有效地索引移动对象现在、最近、将来的位置信息,而且随着时间的推移,能够将两种索引结构内容快速过渡。在实现移动对象历史轨迹的完整或局部的有效查询的同时,又保证了移动轨迹的空间紧密性。     

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.     

移动对象索引方法研究

传统空间索引结构因无法适应大量的更新操作而不能应用于移动对象的存储和检索。本文介绍了三种主要移动时象索引方法的基本思想，即R树及其变形树、四叉树及其变形树以及网格文件及其变形算法，并进行了分析时比，在此基础上提出了混合索引结构，比已知的索引结构效率更高。     

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.     

一种构建于DSM的移动对象的全时态索引方法

移动对象索引技术是移动对象数据库这个新兴的热点领域中的关键技术之一.针对该技术处理数据的繁琐复杂特性,提出构建于DSM的移动对象索引方法 DSM_MSMON,在分布式系统中并行的管理移动对象的信息,支持更新和查询操作.DSM_MSMON统一了单机和多机的内存管理策略,解决了DSM系统中的数据定位、一致性维护、负载平衡和可扩充性等主要问题,有效地提高了移动对象索引的效率.文中给出DSM_MSMON的设计思想和模型,并分析了DSM_MSMON的关键技术和程序流程.实验结果表明,该方法要优于MSMON结构.     

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

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

Direction-aware KNN queries for moving objects in a road network

Recently more and more people focus on k-nearest neighbor (KNN) query processing over moving objects in road networks, e.g., taxi hailing and ride sharing. However, as far as we know, the existing k-nearest neighbor (KNN) queries take distance as the major criteria for nearest neighbor objects, even without taking direction into consideration. The main issue with existing methods is that moving objects change their locations and directions frequently over time, so the information updates cannot be processed in time and they run the risk of retrieving the incorrect KNN results. They may fail to meet users’ needs in certain scenarios, especially in the case of querying k-nearest neighbors for moving objects in a road network. In order to find the top k-nearest objects moving toward a query point, this paper presents a novel algorithm for direction-aware KNN (DAKNN) queries for moving objects in a road network. In this method, R-tree and simple grid are firstly used as the underlying index structure, where the R-tree is used for indexing the static road network and the simple grid is used for indexing the moving objects. Then, it introduces the notion of “azimuth” to represent the moving direction of objects in a road network, and presents a novel local network expansion method to quickly judge the direction of the moving objects. By considering whether a moving object is moving farther away from or getting closer to a query point, the object that is definitely not in the KNN result set is effectively excluded. Thus, we can reduce the communication cost, meanwhile simplify the computation of moving direction between moving objects and query point. Comprehensive experiments are conducted and the results show that our algorithm can achieve real-time and efficient queries in retrieving objects moving toward query point in a road network.