文档介绍：国防科学技术大学
硕士学位论文
不确定数据流上Skyline查询处理技术研究
姓名:祁亚斐
申请学位级别:硕士
专业:计算机科学与技术
指导教师:王意洁
2010-11
国防科学技术大学研究生院硕士学位论文

摘要
随着计算机网络技术的快速发展,在金融信息、气象信息、无线传感器网络
等领域产生了大量的数据流。同时,网络环境的复杂化使得数据流中的数据具有
不确定的特征,研究不确定数据流处理技术是一个热点问题。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