一种基于R_tree的时空索引_柳建平


立即下载 咿呀哟
2024-03-26
对象 查询 时空 时间 空间 定义 索引 窗口 数据 相交
99.9 KB

概述1
时空数据库管理形状和位置这些随时间变化的对象,在
如交通监控、地籍管理以及多媒体等方面有着广泛的应用。
由于这类数据库里的数据随时间不断积累,尺寸十分庞大,
因此建立有效的索引结构来访问这些数据非常重要。不同的
应用背景导致不同的时空数据定义,本文采用以下定义:
定义 1 时空对象 由 唯一标志 是一个随时间演变o( o_id )
的空间对象,它的演变历史由元组系列 (o_id, si , t i 表 示 ,)
si 表示对象在 ti时刻的空间位置。在索引结构中 si由该对象的
空间最小外接超立方体 (x 1 , y1 ,..., x 2 ,y2 表示,,...) x1和 y1表 示
该立方体 轴和 轴上的最小值,x y x2和 y2表示在 轴和 轴上的x y
最大值。
本文中采用“退化模型
[1]
”来表示时空对象演变历史。
即演变过程中只涉及到对象的插入和删除。元组 (o_id , s i ,
[t i,tj 表示了对象的一个生命期,该生命期内对象的空间状态])
不变。如果时空数据集中某元组包含形式为 [ti 的生命,now]
期 表示该对象的状态结束时间未定 ,则此类数据集称 (now )
之为在线模式 ,否则称为离线模式(online mode) (offline
。mode)
最基本的空间查询是窗口查询
[2]
,它返回所有和查询窗
口相交的空间对象。空间查询再加上时态限制就形成了时空
查询。两类比较重要的时空查询是时间片查询和时间段查
询。这里给出定义:
定义 2 时间片查询表示为 ,返回timeslice_query(W,T)
在 时刻和窗口 相交的所有时空对象。T W
定义 3 时间段查询表示为 interval_query(W,[t 1,t2 , 返])
回在时间 t1到t2时间区间内与窗口相交过的所有时空对象。
时空索引研究在近年十分活跃 并已经针对不同类型的,
时空数据提出了一些索引算法。到目前为止,综合考虑时间
和空间因素的索引比较典型的有 种,即4 MR-trees[7]、 RT-
trees[5]、 3D R-trees[6]和HR-trees[4]。 把时间看作空3D R-trees
间的另一维,当对象在一段时间内保持静止时形成一


对象/查询/时空/时间/空间/定义/索引/窗口/数据/相交/ 对象/查询/时空/时间/空间/定义/索引/窗口/数据/相交/
-1 条回复
登录 后才能参与评论
-->