时间：2022-12-04 12:30:01 | 来源：信息时代
时间：2022-12-04 12:30:01 来源：信息时代
移动对象索引 : 针对移动对象的一种索引技术。在移动数据库中通常管理着数量非常庞大的移动对象(如车辆、飞机、移动用户等),在查询处理时,如果逐个扫描所有的移动对象,会降低系统性能。为减少查询的空间代价、提高查询效率,必须对数据库中存储的移动对象进行索引。
1. 移动对象索引
移动对象的索引应支持:
(1)动态数据的抽象表示:动态属性数据随着时间的变化而改变。要既能表示动态数据的当前状态,又能表示它的变化历史,还能描述数据变化的未来趋势和情况,必须采用动态数据模型。而数据模型是索引工作和其他相关工作的前提。所以,从这个意义上讲,动态数据表示也可以认为是移动对象索引工作的一部分。
(2)动态可维护性: 由于数据是动态变化的,即便在原有的存储条件下已经建立了数据的抽象模型,但这种抽象可能发生变化。因此,移动对象的索引也需要动态更新或者重建。
(3)可扩展性:包括两层含义:第一,能支持尽可多的查询类型; 第二,索引的性能应该是随数据量增加而近乎线性地下降(不是非线性地下降太快)。
(4)大数据量: 通常移动对象的数据量都很大,故移动对象索引必须支持巨大的数据负载。
(5)移动对象查询:支持高效查询是建立索引最直接和最主要的目的,移动对象的索引当然也不例外。另外,移动对象的索引还应该支持尽可能多的查询类型,因为移动对象查询是多种多样的。
2.移动对象的索引方法
移动对象索引方法通常借鉴于空间数据索引技术,不同之处在于移动对象索引中必有一维是时间。空间数据索引方法中有R-树及其变形(R+-树、R*-树等)、Quad-树、X-树、LSD-树、格栅文件等,但它们都难以直接应用于移动对象索引。因为这些方法都假定查询频率远远高于更新频率,它们更多地只考虑查询效率。而对移动对象索引来说,移动对象的位置更新会引起索引结构的动态变化,故在查询负载之外还有大量的更新负载,所以移动对象索引除了要考虑查询效率外,还必须着重考虑更新代价问题。在这种情况下,针对移动数据管理,人们提出了一些新的索引技术和解决方案。
(1)在原有的空间索引中引入时间维。其主要思想就是将时间看作另一个空间维。若原有的参考空间是d维的,则现在将其视为d+1维来处理,于是传统的空间索引方法就可以应用了。如SpatioTemporal R-tree、MV3R-tree等就是这种思想的例子。但该方法存在的问题是生存期较长的对象将被表示为长矩形。
(2)在结点中加入时间因素,使每个对象都有空间和时间的范围。当移动对象的位置发生改变时,就插入新的记录。显然,维护这种索引结构的代价是很高的。
(3)分状态索引。应用传统空间索引方法来索引每个状态下的对象,也就是建立一系列对应离散时刻的树结构。
(4)空间-时间表示。移动对象的轨迹表示为空间-时间坐标系里的一条射线(一维的情况下),每条线用一个最小范围矩形(MBR)近似表示。它的问题是,MBR的范围要比它对应的轨迹大得多。因此,常常采用下面的二元时空变换方法。
(5)二元时空变换。存在很多种变换方法,共同的思想就是降维。例如,Hough-X变换就是将直线y(t)=v*t+a变为平面上的一个点(v,a)。类似的还有Hough-Y变换。这类方法的主要缺点是,当维数为d时,需要将运动分解为d个投影,因此不能很方便地解决三维空间下的移动对象问题。另外,可以利用希尔伯特曲线等空间划分技术,将高维空间降为低维空间,使更新代价减小,数据表示更简单。
3.移动对象的时空索引
移动对象索引与时空索引方法密切相关,可以分为对移动对象过去位置或者历史轨迹的索引和对现在与将来位置的索引。
在对移动对象过去位置的索引中,对象的历史轨迹是随着时间连续变化的,但我们不可能记录下所有更新的位置,因此只能以折线来近似描述移动对象过去的位置变化。移动对象历史位置信息包含空间与时间两个方面,即对应移动对象在一定时间范围内的空间位置信息。根据对空间与时间维处理方式的不同,移动对象历史位置信息索引可以分为三类: 第一类是在已有的空间索引基础上加入时间维,即将时间看作空间索引中的另外一维而不区分时间维与空间维; 第二类要区分空间维与时间维,但主要目标是将空间邻近的移动对象聚集在一起,而时间维处于次要地位。这种作法是为了支持基于轨迹的查询,目的是高效地获得同一个移动对象的全部或部分轨迹,而将时间或空间临近的移动对象聚集在一起放在次要的位置。前两类查询处理着眼于基于移动对象坐标信息的查询,即关注移动对象的位置信息,如点查询、区域查询、最邻近查询等;第三类则关注移动对象的轨迹查询,即查询拓扑或推导信息。支持结合了坐标查询与轨迹查询的混合型查询,这通常需要先以一个区域查询来得到候选的轨迹集合,然后处理候选集中的轨迹查询。
移动对象位置更新频繁,移动对象当前与未来位置索引的关键是采用有效的更新算法及预测模型,其主要目标是给定对象当前的运动向量,使得能有效地检索在未来时间满足某个空间条件的移动对象。对未来信息进行索引,根据对时间维和空间维处理方法的不同,可以分为时间-空间维方法、转换式方法和参数式方法三种。在时间-空间维方法中,时间被当作单独的一维来处理; 在转化式方法中,时间维被转化到空间维;而在参数式方法中,将时间作为对空间进行描述的参数。
在线咨询
