时空索引管理(数据库)

时间：2022-11-10 10:30:01 | 来源：信息时代

时间：2022-11-10 10:30:01 来源：信息时代

    时空索引管理 : 时空数据库管理系统的一个重要功能,目的是使时空数据库管理系统能对大量的时空数据进行快速的查询和处理。传统的关系数据库管理系统的索引机制主要支持对数值型、字符串等数据的索引与快速存取,已不能满足时空数据库的查询需求。
时空数据库管理系统需要管理大量的带有长期时间信息的空间数据,为了对这些数据进行有效存取,对时空索引机制的研究显得尤为重要。但空间、时间索引技术的研究成果并不能直接应用于时空数据,因为空间索引可以支持对点、任意形状的区域及光栅数据进行查询操作,但没有考虑到时空应用中的时间特性; 而针对时间信息的存取方法只对有效时间和事务时间进行索引,没有考虑到时空对象的空间属性。
1. 时空索引方法
时空索引的索引结构直接与查询类型和时空对象本身有关,在空间索引方法和时态索引方法的基础上,已经提出了一些时空索引方法,主要如下:
(1)时间维作为一个空间维度:将时间看成是时空对象另一维度的空间信息,则可直接使用传统的空间索引方法(如R-树、四叉树)处理d+1维的空间信息(d是参考空间的维度)。3DR-树将二维参考空间中的最小边界矩形(MBR)转换成三维空间的最小边界矩形(MBR的高度对应于对象的生命期),以表示位置及范围均不随时间发生变化的时空对象,并使用R-树索引结构存储时空数据。图1给出了时空对象实例及其对应的3DR-树。

图1 用R-树结构存储三维的MBRs

3DR-树实现较容易,可有效地支持时间片查询,缺点是没有考虑到时间维的特有属性。对生命期长或位置变化大的对象,该方法会导致3DR-树中结点MBRs的大量重叠,降低查询效率。
(2)综合考虑时空对象的时间与空间信息: 以MR-树和RT-树为代表的索引方法是将时间和空间信息一起存储到R-树结点中,无论是叶结点还是非叶结点中的实体,都以<S,T,P>格式存储,其中S表示空间信息(MBRs),T是时间信息(时间间隔),P为指向子树或具体对象的指针。这里T=(t_i,t_j),i≤j,t_j表示当前时间戳,t_j+1是下一个时间戳(t_j≤t_j+1)。如果时空对象在时间戳t_j到t_j+1期间空间位置不变,则实体的空间信息S保持不变,而时间信息由T更新为T′(T′=(t_i,t_j+1));一旦时空对象的空间位置发生变化,原实体保持不变,产生新的实体<S′,T,P′>,插入到索引树中,其中S′是对象新的空间位置,T=(t_j+1,t_j+1)。该结构较适用于对象移动较少的时空数据库。
(3)基于部分持久和重叠技术的方法:部分持久结构(partially persistent structure)将二维空间存取方法(如R-树、四叉树或k-d-树结构)转换为部分持久的结构,它在“逻辑”上存储过去的时空状态S(t),并只对当前时空状态数据更新。对时空状态S(t)的历史查询,可直接对时空状态在时间戳t的部分持久结构操作(可看成是对暂态R-树的操作)。该方法避免了3DR-树中长生命期对象引起的结点MBRs重叠问题,可有效地支持时间戳和时间间隔查询。重叠(overlapping)技术是用二维空间索引为每个时间戳建立一棵对应的暂态树(如暂态R-树),并假设相邻时间戳的暂态树区别不大,存在许多共同路径(路径上结点内空间对象没有随时间变化)。为了节省磁盘空间,相邻时间戳的暂态树间可共享这些路径,而那些包含空间对象变化的结点及路径可更新后复制到后续暂态树中。图2(a)、(b)分别对应时间戳t₀和t₁的暂态R-树,如果在时间戳t₁结点3数据更新(假设是结点3中一个空间对象被删除),则时间戳t₁的暂态R-树与t₀时的区别仅是创建了新的结点3a和到达结点3a的新路径,其余结点和路径均与t₀时相同,可共享,两棵暂态R-树有重叠部分,见图2(c)。
(4)移动点过去轨迹的方法:对连续移动点过去轨迹的索引一般可转化为离散情况下的索引问题。例如,在平面上作直线运动的点对象,其运动轨迹可看成是若干线段的集合。对象的移动变化意味着在原来轨迹的末端插入新的线段。如果将每条线段都当作是一个空间对象(如点或区域对象)处理,则连续点的移动变化相当于在数据库中插入和删除线段对象,可对离散情况下的时空索引进行扩展,如STR-树、TB-树。

图2 暂态R-树及重叠树

(5)支持移动点未来位置查询的方法:连续情况下移动点的运动轨迹可用时间函数(如p_i(t))表示,根据p_i(t)及已知的某一时间戳移动点的位置来预测其未来位置。
创建索引的一种简单方法是假设点对象在d-维(d=1,2,3)空间移动,这些点未来的移动轨迹可当作d+1-维空间的线对象进行索引。例如可将一维空间中点的移动轨迹看成是(x,t)空间中的线,可使用PMR-四叉树(PMR-quadtree)作为索引结构。具体方法是将时间维划分为若干个相等的时间间隔ΔT,对每个ΔT重建新的PMR-树索引,并允许在ΔT内插入、删除和更新操作。这种索引结构的缺点是在树中存在冗余数据(如一条线段通常会存储在几个结点中),且需要大量的存储空间和频繁的数据更新。
另一种方法是在二元空间(dual space)中建立索引,其主要思想源于几何算法中的二元转换: 将初始空间(primal space)中的线(移动点的轨迹)转换为二元空间中的点,如图3所示。在二元空间中,基于k-d-树的存取方法优于R-树。
2. 时空索引分类
时空索引可作如下分类:
(1)按处理的数据类型分类:主要的时空数据类型为移动点和移动区域。有些索引只处理点数据或移动点的轨迹,支持轨迹查询; 处理区域数据的索引方法既能处理点数据又能处理非点数据,因为点对象可看成是大小为零的区域对象,如3DR-树、RT-树、HR-树、PPR-树及MV3R-树等。

(a) 初始空间中移动点的轨迹

(b) 转换后的二次元空间(Hough-X转换)

图3 二元空间转换

(2)按数据加载的方式分类: 在时空数据库中,对过去时间戳的空间数据插入或更新均是无意义的(无论是静态载入还是动态插入)。因此,时空索引可分为静态、按时间顺序(chronological)和动态的三种类型。静态类型和按时间顺序类型均不允许对过去时间戳的数据插入或更新,前者是以批处理方式载入数据(如3DR-树),后者按时间戳的递增顺序动态插入数据(RT-树、HR-树、PPR-树等); 动态类型允许动态插入数据,且可对过去时间戳的数据插入或更新。
(3)按数据集的更新情况分类:时空索引可按数据集的更新情况分为增长的、变化的和完全动态的三类。增长类型是指对象静止不动,而时间是动态递增的;变化类型是时间为静态的,而对象是移动的; 支持时间动态变化情况下的移动对象称为完全动态类型(full-dynamic),目前研究的索引结构大多是支持时间动态变化的。
(4)按时空对象的近似表示分类:部分索引结构(如3DR-树)采用R-树中用MBR表示空间对象的方法来表示时空对象。由于时空对象独有的移动特性,这种表示方法会导致大量的无效空间和MBR的重叠,并不能很好地支持时空查询,对此提出了一些时空对象近似表示方法。
(5)按是否支持特定的时空查询分类:时空索引除了要支持选择、连接和最近邻居查询外,还应支持时间查询和复杂的时空查询,如时间片查询、轨迹查询以及历史查询等。RT-树索引结构仅支持基本的时空查询,HR-树、PPR-树支持对时间戳的查询,3DR-树和MV3R-树可同时支持时间戳、时间间隔的查询; STR-树、TB-树以及TPR-树可支持对移动点的轨迹查询。
(6)按支持的时间维度分类:时空数据库应至少包含一维时间信息,时空索引可分为支持有效时间、事务时间和双时间的索引机制。
(7)按离散/连续的情况分类: 目前大多数的索引结构均是基于离散情况(如3DR-树、HR-树、RT-树以及PPR-树等),可以查询时空对象过去及当前的状态。对连续时空变化情况下,可根据时空对象位置或范围随时间变化的函数来建立索引,不仅可以查询时空对象过去和当前的位置和范围,还可根据时空对象当前的信息推测出它在将来某个时间戳的行为。