不确定数据流上Skyline查询处理技术研究

论文摘要

随着计算机网络技术的快速发展,在金融信息、气象信息、无线传感器网络等领域产生了大量的数据流。同时,网络环境的复杂化使得数据流中的数据具有不确定的特征,研究不确定数据流处理技术是一个热点问题。Skyline查询处理技术常用于多目标决策,不确定数据流上Skyline查询具有重要的应用价值。不确定数据流的数据不确定、实时响应、单遍处理等特点对Skyline查询带来巨大挑战。本文针对不确定数据流上Skyline查询中的对象建模、结构索引、多数据流来源及多用户查询等问题,深入研究了不确定数据流上Skyline查询方法、分布式Skyline查询方法以及分布式子空间Skyline查询方法。取得的主要研究进展如下:不确定数据流上Skyline查询用于解决不确定数据流上的多目标决策问题。本文针对连续概率密度函数模型的不确定数据流上Skyline查询处理技术中Skyline概率计算、不确定对象索引结构等问题,提出了一种高效的基于高斯模型的不确定数据流上Skyline查询方法SGMU,该方法包含两个算法:动态高斯建模算法DGM和基于高斯树的Skyline查询算法GTS。DGM算法对不确定数据流滑动窗口中的数据采样并建立高斯模型,将数据流转化为不确定对象概率密度函数的参数流;GTS算法针对高斯模型的参数流建立R树索引结构,通过对R树进行剪枝以减少计算量。理论分析和模拟测试表明,与无索引结构的不确定数据流Skyline查询方法BNL（Block-Nested-Loop,简称BNL）相比,SGMU方法不仅能够对连续型不确定对象进行有效建模以辅助Skyline查询,而且能够有效地剪枝不确定数据对象,提高Skyline查询效率。分布式Skyline查询方法能够应对分布式的数据流上的Skyline查询任务。本文深入研究了已有的数据流上分布式Skyline查询中的数据集分割方案及对应数据集分割方案下的Skyline查询方法。在SGMU方法的基础上,提出了基于水平分割的连续概率密度函数建模的不确定数据流分布式Skyline查询方法SHUCpdf和基于垂直分割的连续概率密度函数建模的不确定数据流分布式Skyline查询方法SVUCpdf。两种方法均在分布式节点先获取局部Skyline结果集合,并在局部Skyline结果并集上再次进行Skyline查询,得出全局Skyline结果集合。两种方法的区别在于采取不同的数据集合分割方式和不同的Skyline概率计算方式。理论分析和模拟测试表明,与集中式的不确定数据流Skyline查询相比,SHUCpdf方法和SVUCpdf方法结构简单,能够快速返回部分数据集合的查询结果,精确连续的获取全局Skyline查询结果。子空间Skyline查询用于解决多用户Skyline查询问题。不同用户关注的数据对象属性可能不同,由此产生多个Skyline查询子空间。针对不确定数据流上的多用户Skyline查询问题,提出了基于垂直分割的连续概率密度函数建模的不确定数据流分布式子空间Skyline查询方法SSVUCpdf。SSVUCpdf方法以SVUCpdf方法为基础,通过分布式节点计算单个维度的Skyline查询结果,便于不同维度组合形成子空间;设置用户偏好空间队列保存用户偏好子空间查询结果,快速返回部分用户请求,减少高维度空间的子空间数目。理论分析与模拟测试表明,SSVUCpdf方法能够有效减少查询开销,避免子空间Skyline查询中“维度爆炸”的问题。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景和意义
• 1.2 数据流管理
• 1.2.1 数据流特点
• 1.2.2 数据流模型
• 1.2.3 不确定数据流
• 1.2.3.1 不确定数据来源
• 1.2.3.2 不确定数据建模
• 1.3 Skyline 查询
• 1.3.1 Skyline 查询分类
• 1.3.2 Skyline 查询定义
• 1.3.2.1 确定数据集上Skyline 查询
• 1.3.2.2 不确定数据集上Skyline 查询
• 1.3.3 Skyline 查询特点
• 1.4 主要研究内容
• 1.5 论文组织结构
• 第二章 相关研究
• 2.1 数据流上Skyline 查询处理技术
• 2.1.1 确定数据流上Skyline 查询处理技术
• 2.1.2 不确定数据流上Skyline 查询处理技术
• 2.2 分布式Skyline 查询处理技术
• 2.2.1 基于水平分割的分布式Skyline 查询处理技术
• 2.2.2 基于垂直分割的分布式Skyline 查询处理技术
• 2.3 子空间Skyline 查询处理技术
• 2.4 本章小结
• 第三章 不确定数据流上Skyline 查询处理技术研究
• 3.1 理论基础
• 3.2 高斯模型
• 3.2.1 对象间支配关系
• 3.2.2 对象与最小边界矩形间支配关系
• 3.2.3 最小边界矩形间的支配关系
• 3.3 基于高斯模型的不确定数据流上Skyline 查询方法
• 3.3.1 动态高斯建模算法
• 3.3.2 基于高斯树的查询算法
• 3.4 实验结果与分析
• 3.4.1 空间维度对性能的影响
• 3.4.2 对象个数对性能的影响
• 3.4.3 概率阈值对性能的影响
• 3.5 本章小结
• 第四章 不确定数据流上分布式Skyline 查询处理技术研究
• 4.1 理论基础
• 4.2 不确定数据流上分布式Skyline 查询方法
• 4.2.1 基于水平分割的连续概率密度函数建模的不确定数据流上分布式Skyline 查询方法
• 4.2.1.1 分布式节点Skyline 查询处理分析
• 4.2.1.2 主节点Skyline 查询处理分析
• 4.2.1.3 SHUCpdf 方法描述
• 4.2.2 基于垂直分割的连续概率密度函数建模的不确定数据流上分布式Skyline 查询方法
• 4.2.2.1 Skyline 查询处理分析
• 4.2.2.2 SVUCpdf 方法描述
• 4.3 实验结果与分析
• 4.3.1 SGMU 方法与 SHUCpdf 方法对比
• 4.3.2 SHUCpdf 方法与SVUCpdf 方法对比
• 4.4 本章小结
• 第五章 不确定数据流上子空间Skyline 查询处理技术研究
• 5.1 理论基础
• 5.2 基于垂直分割的不确定数据流分布式子空间Skyline 查询方法
• 5.2.1 用户偏好子空间维护算法
• 5.2.2 子空间Skyline 计算方法
• 5.3 实验结果与分析
• 5.4 本章小结
• 第六章 结束语
• 6.1 工作总结
• 6.2 研究展望
• 致谢
• 参考文献
• 作者在学期间取得的学术成果
• 作者在学期间参加的科研项目