复杂空间环境下的新型空间查询处理技术研究

摘要

随着空间定位和移动通信等技术的发展，以及人们对空间信息日益强烈的需求，空间数据管理技术在近些年来获得了极大的关注。查询处理技术是空间数据管理领域最常见的和最重要的应用。例如，司机会查找离自己最近的餐馆信息，以及自己油箱内的油能够到达的加油站等。目前，已有一些研究对多种空间查询提出解决方案，包括高效的索引技术以及高效的查询策略等，这些解决方案都限定在比较单一的空间环境中。然而，真实世界中空间环境复杂多样，例如，空间中存在障碍物，地面上存在路径限制对象的运动等。已有的技术往往没有充分考虑复杂空间环境的特点，无法准确、高效地在这样复杂的空间中处理空间查询。因此，亟需针对不同的空间环境定义一些新的空间模型，并且设计新的距离度量机制，进而对空间查询有针对性地设计新型查询技术。
　　本文对已有空间环境和已有的查询处理技术进行了分析和综述。在此基础上，本文深入研究了几种复杂空间环境，并且基于这些空间环境针对几种查询设计了新型的高效查询策略。本文的贡献主要包括以下几个方面:
　　针对半限制空间内移动对象逻辑轨迹近邻对查询，本文提出了高效的解决技术。半限制空间是从室内等有限制空间环境中抽象出来的一种新的空间环境，该环境将空间划分为多个离散的区域，无需考虑对象在同一区域内的距离，不同区域之间通过物理路径连接。半限制空间内的轨迹是一条位置标号的序列，每个点代表一个逻辑区域。不同逻辑区域之间的距离预先由系统给定，反映两区域之间的实际连通距离。本文针对半限制空间内逻辑轨迹近邻对查询展开深入研究。为了提高基本方法的解决效率，本文提出基于轨迹共现度的过滤策略和基于长度偏移比的过滤策略，避免了对两两轨迹对的比较，从而提高了查询效率。
　　针对路网空间内无线广播模式中的k近邻，反最近邻和范围查询，本文提出了基于高效索引技术的查询处理方法。无线广播模式中，服务器不停地向外广播数据，客户端根据需要接收数据，客户端无法向上传递数据。在无线广播模式中执行空间查询想要达到的效果是从发起查询时刻到得到结果时刻的处理延迟较小，以及客户端接收数据的活跃时间较少。本文的处理机制将路网空间划分为多个小的区域，然后对每个区域预计算该区域到空间中每个区域距离的上下限，在此基础上对这些区域建立索引。由于该索引中包含一些预计算的信息，因此通过接收索引，用户可以迅速判定自己所需要的数据块。并且，通过合理地组织索引，能够使得需要接收的数据包数量尽可能地少，从而达到活跃时间和处理延迟的平衡。在此索引基础上，针对路网上的k近邻查询，反最近邻查询和范围查询，分别设计了高效的查询处理方法。
　　针对障碍空间内概率可见k近邻查询，本文提出了高效的剪枝和验证方法。在障碍空间内，对象之间的距离以可见距离衡量。由于测量设备误差、网络传输延迟等因素，对象的位置往往是不确定的，对这类位置不确定对象以概率限定矩形和概率密度函数建模。针对这种不确定对象的可见k近邻查询，提出了一种剪枝-求精的处理框架。根据空间对象属性，设计了k-界限剪枝，可见质心剪枝以及不可见对象剪枝方法，将不可能成为结果的对象剪掉，获取一个较小的候选集。然后，对候选集合进行求精，通过采样方法以及高效的基于上下限的增量求精方法，得到最终结果集。
　　针对障碍空间内移动可见k近邻查询，本文提出了剪枝-求精的高效处理机制。其中，查询点和查询对象都在不规律运动。本文提出一个新颖的处理机制，对每个对象（包括查询对象）都赋予一个安全区域，在T时间内保证所有对象都在其安全区域内，每隔T时间需要更新全部对象的位置。在此基础上采用剪枝-求精的查询框架。首先利用安全区域的空间特性，提出了基于安全区域的空间距离的剪枝方法。然后，通过对不可见对象计算不可见时间段，进一步过滤候选集。此外，通过将查询对象的移动方向考虑入内，提出一种方法能够计算出较大的不可见时间段，从而增加了对象被过滤的时间，减少了候选对象的数目。在此基础上，对候选对象探测实际位置，并执行精化算法，得到最终结果。
　　总之，本文从多种复杂空间环境的典型特征和挑战出发，针对多种空间查询的关键技术展开研究，提出高效的查询方法及框架。本文的研究为在复杂空间模型下空间查询的执行，提供了有力的支持。

目录

声明

摘要

第一章 绪论

1．1 空间数据管理技术

1．1．1 空间数据库

1．1．2 空间数据索引技术

1．1．3 面向空间数据的查询处理技术

1．1．4 无线数据传输技术

1．2 复杂空间环境

1．2．1 半限制空间

1．2．2 路网空间

1．2．3 障碍空间

1．3 本文的研究内容和结构

1．3．1 研究内容

1．3．2 组织结构

第二章 半限制空间内的移动对象轨迹近邻对查询

2．1 研究背景

2．2 相关工作

2．2．1 空间环境介绍

2．2．2 轨迹近邻对查询处理技术

2．2．3 RFID数据管理技术

2．3 预备知识

2．3．1 半限制空间

2．3．2 逻辑轨迹

2．3．3 已有距离度量分析

2．3．4 路径编辑距离

2．4 轨迹近邻对查询处理

2．4．1 基本查询方法

2．4．2 轨迹近邻对查询框架

2．4．3 基于路径共现度的过滤

2．4．4 基于轨迹长度偏移比的过滤

2．5 实验结果

2．5．1 实验设置

2．5．2 实验结果

2．6 本章小结

第三章 基于无线广播模式的路网空间内空间查询

3．1 研究背景

3．2 相关工作

3．2．1 无线广播模式介绍

3．2．2 无线广播模式下的空间查询处理技术

3．2．3 路网上的空间查询处理技术

3．3 ISW索引

3．3．1 ISW索引结构

3．3．2 上下界的计算

3．3．3 理论分析

3．4 k近邻查询处理技术

3．4．1 空间剪枝

3．4．2 查询处理

3．5 范围查询处理技术

3．6 反最近邻查询处理技术

3．7 实验分析

3．7．1 k近邻查询评估

3．7．2 范围查询评估

3．7．3 反最近邻查询评估

3．8 本章小结

第四章 障碍空间内概率可见k近邻查询

4．1 研究背景

4．1．1 障碍空间

4．1．2 不确定对象模型

4．1．3 可见距离

4．2 相关工作

4．2．1 可见查询处理技术

4．2．2 障碍查询处理技术

4．2．3 概率查询处理技术

4．3 预备知识

4．3．1 概率可见k近邻查询定义

4．3．2 基本查询方法

4．3．3 查询框架

4．4 概率可见k近邻剪枝技术

4．4．1 k-界限剪枝方法

4．4．2 基于可见质心的剪枝方法

4．4．3 不可见对象的剪枝方法

4．5 概率可见忽近邻查询求精

4．5．1 基于采样的概率求精

4．5．2 基于概率上下限的求精

4．6 实验评价

4．7 本章小结

第五章 障碍空间内连续可见k近邻查询

5．1 研究背景

5．2 相关工作

5．2．1 连续空间查询处理技术

5．2．2 基于移动对象的连续k近邻查询处理技术

5．3 预备知识

5．3．1 问题定义

5．3．2 查询处理框架

5．4 剪枝方法

5．4．1 基于安全区域的剪枝方法

5．4．2 基于不可见时间段的剪枝方法

5．4．3 移动方向感知的不可见时间段剪枝方法

5．5 理论分析

5．5．1 通信代价分析

5．5．2 计算代价分析

5．6 实验评价

5．6．1 实验设置

5．6．2 选择合理的T值

5．6．3 不同方法性能比较

5．7 本章小结

第六章 结论

6．1 本文的主要贡献与结论

6．2 未来工作的展望

参考文献

致谢

攻读博士学位期间的研究成果

参加科研课题情况

个人简历