论文摘要
随着GPS定位、无线技术和计算机技术的迅猛发展,越来越多的移动对象被实时存储在数据库中,而传统数据库都是以优化静态数据查询为目标,这促使以管理表示频繁更新移动对象的时空数据为目标的移动对象数据库的产生。由于传统数据库技术都无法支持对时空数据的有效管理,因此,需要对移动对象数据库的相关技术进行研究。本文主要从两个方面研究了移动对象数据库中时空数据管理的关键技术问题。一是时空数据索引技术。在这方面,本文主要探讨和研究了公路网络环境下时空数据的索引技术;二是轨迹数据（历史时空数据）的异常点检测算法。在这方面,本文主要研究了由具有较长路径的轨迹组成的轨迹数据的异常点检测算法。在索引技术方面,本文针对更新操作在公路网络环境下的新特点,提出了一种支持频繁更新的时空数据索引结构GTR-Tree（Group Updateand Time Parameter R-Tree）。该索引结构先对公路网路的边建立R-Tree索引,然后再对移动对象进行索引,移动对象在边上的位置用x坐标或y坐标表示,并引入时间函数以避免匀速运动的更新。这样,在公路网络环境下,按照更新前后移动对象所处边的不同,把更新操作分成跨边更新（更新后移动对象位于不同的公路）、匀速更新（更新前后对象不仅处在同一条公路,而且对象还处在匀速运动）和非匀速更新（更新前后对象处在同一公路,但不是匀速运动）三类:那么针对不同的更新类型执行不同的更新过程,如匀速更新可以直接被省略。同时,在R-Tree的叶子结点附上内存缓冲以缓存新插入数据项,仅当该缓冲区满时,将最大分组的缓冲数据项刷新到对应的磁盘空间以共享磁盘I/O,而删除信息则有一个常驻内存的过期对象表维护,直到该某条边所在存储区域被访问时才删除里面的过期数据项。过期对象表的存在使得GTR-Tree的CPU性能很低,为了解决这个问题,本文对GTR-Tree进行改进,提出了一种新的索引结构MGTR-Tree,该索引结构将更新操作分成两个子操作:插入子操作向索引结构插入一个新数据插入的数据项,而删除子操作则是向索引结构插入一个删除旧数据的子操作。通过这个方式,MGTR-Tree的数据结构可以删除过期对象表,从而保证了算法在CPU代价的高效性。此外,GTR-Tree和MGTR-Tree组更新技术都要借助于内存空间作为缓冲才能实现,因此,本文还提出了另一种在公路网络环境下实现组更新技术的索引结构DGTR-Tree。该索引结构以磁盘介质为缓冲区实现组更新技术,它不需要任何内存空间作依托,从而提高了组更新技术的适用性。该索引结构在R-Tree的每个结点附上一个缓冲区,属于某个结点的数据项先缓存在该结点对应的缓冲区中,仅当该缓冲区满时,才将该缓冲区内的数据项刷新到对应的子结点中,从而实现访问共享。在轨迹数据异常点检测方面,一方面,本文针对当前异常轨迹检测算法只比较轨迹形状的不足,详细分析了轨迹数据与图像数据的不同以及轨迹数据中隐含的一些固有特征,提出了一种新的衡量轨迹片段相似度的度量方法,该度量方法采用基于平移的最小Hausdorff距离的思想,结合轨迹数据本身的固有特征,从轨迹片段的形状和其蕴含的局部运动模式（移动速度和移动方向）两个角度进行轨迹片段相似度的比较:并在此基础上,定义了相近基本轨迹单元对（一个轨迹片段中的点属于另一个轨迹片段对应点的邻域内）、异常轨迹的概念;并提出了一种基于R-Tree的异常轨迹检测算法,该算法首先对所有轨迹点建立一个R-Tree索引,然后利用R-Tree搜索出每个轨迹点的对应的邻域点子集,再利用两条轨迹间的点距离特征矩阵（两条轨迹中每两个点组合为元素组成的矩阵）快速找出所有相近的基本轨迹单元对,从而提高算法的搜索性能。另一方面,随着用户需求的提高,不仅轨迹数据在变大,而且组成轨迹的点数目也在不断变多（轨迹时间跨度变大和精度提高都会增加点数）。针对越来越长的轨迹,以一条轨迹为单位的检测结构（轨迹是否为异常轨迹）已经不能满足一些特定用户的需要。本文提出了一种以轨迹点为目标的轨迹数据异常点检测算法,该算法给每个轨迹点赋予一个表示其局部异常程度的值,即局部异常度（Local Outlier Degree,简称LOD）。这里的“局部”包含两层含义:一、轨迹间的比较是以轨迹片段为基础进行比较;二、轨迹片段仅与其一定邻域内的轨迹片段进行比较。轨迹点的局部异常度是基于固定长度的轨迹片段为基础,通过该点在轨迹片段中的异常程度。本文对提出的各种算法不仅都作了详细的性能分析,而且使用实际数据集或综合数据集对算法进行了详细实验。索引结构方面使用的实验数据集是使用Oldenbourg实际公路网络数据和基于网络的数据生成器生成的综合数据,而对于轨迹数据异常点检测方面,实验数据集是来自美国unisys网站提供的全球飓风历年轨迹数据集（包括大西洋,东太平洋和西太平洋的飓风数据集）中的经纬度数据。并和相应领域的主流方法做了实验对比,并对相关参数的变化作了详细实验。经实验和性能分析都表明:本文提出的算法与相关算法相比具有很好的性能和处理能力。