位置不确定移动对象连续概率skyline查询的研究

论文摘要

Skyline计算的目的是寻找数据集合中属性向量不被其他任何对象支配的对象，它在多目标决策、偏好查询、数据挖掘以及数据可视化等方面有着广泛的应用。自被引入数据库领域以来，Skyline操作引起了学者广泛的关注。最初对于skyline操作的研究多是对集中式环境中的静态数据上的，但现实生活中数据往往都是处于动态环境中的。随着无线通讯系统的发展、设备小型化、车载设备等得普及产生了随时间变化的移动数据使得移动计算成为可能，随后也出现了对于移动环境下的skyline查询的研究。数据的不确定性是数据的另一个固有性质。本文将移动性与不确定性相结合，移动对象在移动过程中由于设备精确度、时间延迟等原因造成的位置的不确定性，使得移动对象间的支配关系不确定，只能采用概率的形式描述移动对象之间的支配关系。本文针对空间无约束和网络受限条件下的查询点固定，被查询对象为位置不确定移动对象时的连续概率skyline操作进行研究，主要创新性工作包括以下几个方面：1.通过对现有不确定模型的分析和对比，建立了移动对象空间无约束环境下的不确定区域模型。在确定模型的基础上给出了不确定移动对象间的支配概率以及移动对象skyline概率的表示方式。并对移动对象间距离函数对移动对象间支配概率的影响进行深入分析，基于此定义了影响移动对象间支配概率的event，通过跟踪处理这些event集合即可更新p-skyline集合。在定义了event的基础上，提出了自由移动环境下的不确定移动对象的连续概率skyline查询算法——（Event triggered Continuous Probabilistic Skyline query for uncertain movingobject, U-ECPS）。2.对网络受限（路网）环境下的位置不确定移动对象提出了适用于该环境的不确定是移动对象的线段模型，给出了移动对象间的支配关系的概率表示方式以及移动对象的skyline概率定义；通过对移动对象与查询点之间网络距离的对比定义了影响移动对象skyline概率的event，基于以上定义提出了一个路网中基于event的位置不确定移动对象的连续概率skyline查询算法（Continuous Probabilistic Skyline query for Uncertain moving object in Road network,PSUR）。3.本文提出的两个算法并不是每一时刻都遍历整个数据集合来确定p-skyline集合，而是通过追踪、处理Events动态更新p-skyline集合。从而提高了算法的效率。为了验证两种环境下各自算法的有效性进行了大量的实验对比。

论文目录

• 摘要
• Abstract
• 引言
• 1 绪论
• 1.1 研究背景与意义
• 1.2 Skyline 查询研究现状
• 1.3 本文的主题
• 1.4 本文的组织
• 2 Skyline 查询相关理论
• 2.1 Skyline 查询的基本概念
• 2.2 静态环境下的 Skyline 查询
• 2.2.1 BNL 算法
• 2.2.2 分治法（ D&C）
• 2.2.3 位图（Bitmap）算法
• 2.2.4 索引（Index）算法
• 2.2.5 最近邻算法（ NN）
• 2.2.6 分枝界限算法 （ BBS）
• 2.3 动态环境下 Skyline 查询
• 2.3.1 数据流上的 skyline 查询
• 2.3.2 移动对象的连续 skyline 查询（CSQ）
• 2.3.3 连续 skyline 计算的有效更新算法（ESC）
• 2.3.4 度量空间中的动态 skyline 查询（MSQ）
• 2.3.5 基于事件的位置不确定移动对象连续概率 Skyline 查询（U-CPSC）
• 2.3.6 基于道路网络不确定移动对象的连续概率 Skyline 查询（U-CPSQRN）
• 2.4 不确定数据集合的概率 skyline 查询
• 2.5 本章小结
• 3 空间无约束环境下的连续概率 skyline 操作
• 3.1 问题分析
• 3.2 相关定义
• 3.3 移动对象间支配关系的变化分析
• 3.4 位置不确定移动对象的连续概率 skyline 查询实现
• 3.4.1 初始化
• 3.4.2 Baseline 算法
• 3.4.3 U-ECPS 算法
• 3.4.4 U-ECPS 算法复杂度分析
• 3.5 实验与分析
• 3.5.1 移动对象数目 N 对算法的影响
• 3.5.2 移动对象不确定区域半径 R 对算法的影响
• 3.5.3 移动对象静态属性维度 d 对算法的影响
• 3.5.4 阈值 p 对算法的影响
• 3.6 本章小结
• 4 网络受限环境下位置不确定移动对象的连续概率 skyline 查询
• 4.1 问题分析
• 4.2 概率 skyline
• 4.2.1 网络距离
• 4.2.2 剪枝规则
• 4.3 网络受限条件下位置不确定移动对象的连续概率 skyline 查询实现
• 4.3.1 初始化
• 4.3.2 PSUR 算法
• 4.3.3 算法性能分析
• 4.4 实验分析
• 4.4.1 移动对象数目 N 对算法的影响
• 4.4.2 移动对象不确定线段长度 L 对算法的影响
• 4.4.3 移动对象静态属性维度 d 对算法的影响
• 4.4.4 查询时间段长度对算法的影响
• 4.4.5 阈值 p 对算法的影响
• 4.5 本章小结
• 5 结束语
• 5.1 工作总结
• 5.2 研究展望
• 参考文献
• 在学研究成果
• 致谢