《时空数据库的索引机制及查询策略研究》由会员分享，可在线阅读，更多相关《时空数据库的索引机制及查询策略研究（134页珍藏版）》请在金锄头文库上搜索。
1、华中科技大学 博士学位论文 时空数据库的索引机制及查询策略研究 姓名：潘鹏 申请学位级别：博士 专业：计算机软件与理论 指导教师：卢炎生 20071106 摘 要 动态空间数据的索引和查询是时空数据库系统研究的重要内容，在交通管理、智 能导航、土地规划、移动通信等领域有重要的应用价值，是数据库领域近年来研究 和发展的方向之一。由于空间信息的多维特性和时间维的特殊性，传统数据库中的 索引机制及查询算法不再适用，现有时空索引机制多在空间索引的基础上演变而来， 形成了以 R 树家族索引为主的时空索引系列，以此为基础，空间数据的窗口、最近 邻、最近对等查询也演变为具有时间片、时间区间和针对未来时刻等时
2、间限制的时 空查询。然而，随着移动用户的日趋增多，对动态空间数据集的频繁更新、多重查 询、连续性查询等问题越来越受人关注，这对时空索引机制和查询算法提出了新的 挑战。针对动态的数据集和查询集合，对现有时空索引和查询算法做进一步的优化， 可以使时空数据库的发展更加适应未来的需求。 现有的 R 树系列时空索引较注重结构的精巧设计和查询性能的优化，通过复杂 的插入算法获得理想的查询性能，忽略甚至增加了索引的维护开销。根据 R 树的结 构与对象分布相关，而后者在动态数据集中往往相对稳定的特点，采取了基于栅格 划分的 R 树更新缓存与批处理机制，依据栅格选取代表对象分布情况的 R 树种子节 点，提出了针
3、对种子节点的简单合并与利用种子记录的分组插入两种更新算法，在 遵循 R 树节点分布原则的前提下降低了维护开销，且保证了查询的效率。 运动轨迹索引需要同时处理更新和历史数据的存取， 由于对轨迹线段有连续存储 的需求，不宜使用融合了多版本分裂与 R 树思想的时空历史索引，而现有的轨迹索 引在考虑连续性的同时却一定程度上弱化了空间查询性能，且未考虑更新的开销。 为此提出了基于位置变化的轨迹索引机制，通过定义轨迹单元，在对轨迹进行合理 划分的同时优化了索引的维护开销。实验表明，轨迹单元索引机制在有效支持时间 片和时间区间查询的同时减少了索引的节点数，降低了维护的开销。 TPR 树是用于未来时空预测查询
4、的 R 树变种，现有的 TPNN 算法以 TPR 树为基 础，反复利用对时间参数的最近邻计算来求得结果，且对多次出现的候选对象重复 II 华 中 科 技 大 学 博 士 学 位 论 文 查询，影响了查询的效率。鉴于此，提出了基于距离函数的预测查询算法，通过一 次遍历 TPR 树生成候选对象的距离函数中间结果，利用距离函数的排序与分析得出 带时间参数的查询结果。以一定的缓存资源避免了对索引的多次遍历和候选对象的 重复访问，减少了查询的 I/O 代价。 动态空间数据环境下，查询点的坐标也可能持续改变，多重连续性查询策略需要 在针对时空索引的时间片或时间区间查询算法的基础上加以改进。现有方法中 SE
5、A-CNN 最具代表性，通过动态维护查询的影响和搜索区域、建立查询索引机制等 手段降低了系统 I/O 开销，但对中间结果的利用和动态查询的优化上却未深入讨论。 为此提出了对象和结果的双缓存机制，减少静态查询重新初始化次数，进一步缩小 动态查询搜索区域，实现了对象访问和查询结果的双重共享。实验表明该机制在对 象分布相对稳定的情况下有最佳效果，能有效降低系统在较长时间内的 I/O 开销。 基于上述充分利用中间结果的思想，进一步对组最近邻连续性查询进行优化，通 过定义查询的外包容影响区域、栅格影响区域和扩展外包容影响区域，在不显著增 加查询的初始化计算开销的前提下合理的增加初始化结果列表的长度，在减
6、少查询 重新初始化次数的同时控制了初始化的成本。 现有的以 R 树为基础的利用节点间 MinMinDist 距离的最近对连接查询算法在参 与连接的两个数据集空间重叠较大时优先级队列过长，导致节点重复访问，性能下 降。对此问题提出了将最近对查询转换为基于滑动窗口子查询的基本策略，通过定 义窗口安全区域、异常区域、安全排列模式减少了对象的重复访问，将连接运算的 I/O 开销转化为一系列窗口查询的开销，控制了重叠情况下的查询开销。 关键词：关键词：时空数据库，时空索引，运动轨迹，空间最近邻，时空预测查询，时空 连续性查询 III 华 中 科 技 大 学 博 士 学 位 论 文 Abstract Th
7、e researching of indexing and querying moving spatial objects is very important in spatio-temporal database, and valuable in applications of traffic control, navigating, land planning and mobile communication, it is a new issue in database researching domain. Since spatial data is multi-dimensional,
8、 while time dimension is for some extent different with spatial dimension, traditional methods of index and query are not applicable in such domain. Most of previous spatio-temporal indexes come from spatial indexes, which are called indexes of the R-tree family. With these indexes, the window-query
9、, nearest neighbor-query, closest pair-query and other spatial queries evolve into queries with temporal constrains such as time slice, time interval and future time. Now, with the development of mobile applications, the issues of frequent updates on moving spatial object dataset, multiple spatio-te
10、mporal queries and continuous spatial queries become remarkable, which challenge previous methods of spatio-temporal index and query. To make the spatio-temporal database more applicable, it is necessary to solve these issues. Previous spatio-temporal indexes of the R-tree family focus on the refine
11、ment of structure and query performance, try to achieve low query cost with complex inserting algorithms, while the cost of updating is for some extent neglected. Basing on the fact that R-trees nodes distribution is relevant with the distribution of spatial objects, which is relatively stable in mo
12、ving object dataset, we introduce a batch-processing method with caches of operations and grid-partitioning of data space for R-tree updating. Seed nodes representing the distribution of objects are chosen by grid cells, a merging algorithm with seed nodes and grouping algorithm with seed records ar
13、e designed for batch-processing. This method reduces the I/O cost of R-tree updating without violating the rules of R-tree node constructing, so, the query performance is not affected. An index structure for trajectories needs to deal with updating of objects current IV 华 中 科 技 大 学 博 士 学 位 论 文 posit
14、ion and preserve their historical spatial information, since the trajectory may need to be preserved continuously, early spatio-temporal indexes using version-splitting method do not suit for it. Previous trajectory indexes increase the trajectories continuity while weaken the performance of spatial
15、 queries, and they also neglect the cost of updating. To solve these problems, a new trajectory indexing method is promoted, which mainly consider the moving distance of objects. By defining the trajectory unit, the index partitions trajectories reasonably, and the cost of maintenance is reduced. Th
16、e experiment results show that such trajectory index using trajectory unit can support window query with time slice and interval constrains effectively, it reduces the number of index nodes, and optimizes the updating with a bottom-up inserting method. The TPR-tree is a variant of R-tree for spatio-temporal prediction queries, and is used in the TPNN algorithm, which outperforms earlier nearest neighbor predictive algorithms. T
