文档介绍：国防科学技术大学
硕士学位论文
不确定数据流上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 查询用于解决多用户 Skyline 查询问题。不同用户关注的数据
对象属性可能不同,由此产生多个 Skyline 查询子空间。针对不确定数据流上的多
第 i 页
国防科学技术大学研究生院硕士学位论文
用户 Skyline 查询问题,提出了基于垂直分割的连续概率密度函数建模的不确定数
据流分布式子空间 Skyline 查询方法 SSVUCpdf。SSVUCpdf 方法以 SVUCpdf 方法
为基础,通过分布式节点计算单个维度的 Skyline 查询结果,便于不同维度组合形
成子空间;设置用户偏好空间队列保存用户偏好子空间查询结果,快速返回部分
用户请求,减少高维度空间的子空间数目。理论分析与模拟测试表明,SSVUCpdf
方法能够有效减少查询开销,避免子空间 Skyline 查询中“维度爆炸”的问题。

关键词:不确定数据流,Skyline 查询,高斯模型,分布式 Skyline 查询,子
空间 Skyline 查询
第 ii 页
国防科学技术大学研究生院硕士学位论文
Abstract
With the rapid development work technology, a large number of
data streams are generated in the field of financial informati