分布式环境下Skyline计算算法研究

论文摘要

一个多维数据库上的skyline,是此数据库上不被其它任何数据点支配的点所组成的集合。skyline计算以其在多目标决策、数据挖掘、数据库可视化等方面的广阔应用获得了越来越多研究者的关注。本文以普通分布式数据库和结构化对等网络为目标,对分布式环境下的skyline计算算法展开了深入的研究。当前,分布式数据库上的skyline计算研究已经取得了初步进展,但已有的算法还远不能满足分布式环境下skyline计算的要求,因为它们至少受限于以下三种情况中的一种:(1)假设数据是被垂直划分的;(2)仅支持满足某种特殊网络要求的水平划分的数据库;(3)专为具有较低计算能力的轻量移动设备设计。因此,本文提出了一种全新的基于反馈的分布式skyline计算算法,它以一种崭新的反馈机制为核心,采多轮计算模式,支持任意水平划分的数据库上的skyline计算。算法中传递的反馈信息能大量剪除非skyline的本地数据点,避免无用信息在网络中的传输,因而很大程度减少了网络带宽的消耗量。算法能快速地响应用户,并按用户规定的顺序逐渐返回计算结果,具有很好的用户可适应性和渐进性。本文以在真实数据库和合成数据库上的大量实验衡量了算法的性能,证实了它是一个高效的分布式skyline计算算法。在此基础上,本文还对对等网络(P2P)上的skyline计算进行了研究。对等网络是分布式信息共享与搜索的一种重要平台,Chord作为对等网络的代表性协议以其简单灵巧的设计和良好的性能备受关注。已有的对等网络上的skyline计算算法或是专为子空间的skyline计算而设计,或是针对某种特殊的对等网络协议,不能应用于其它协议上。本文提出了一种新的基于Chord的skyline计算算法,它将多维数据映射为一维标识符,在沿Chord环传递信息的过程中,剪除大量非skyline的本地数据点,渐进地处理数据并输出skyline。该算法减小了网络带宽的消耗量和需要访问的节点的个数,具有很好的渐进性和可扩展性。理论分析和实验结果均证明这是一种符合对等网络特点的准确高效的skyline计算算法。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景与现状
• 1.1.1 Skyline的定义与性质
• 1.1.2 Skyline计算的应用
• 1.1.3 Skyline计算的现状与挑战
• 1.2 研究内容
• 1.3 本文结构
• 第二章 现有Skyline计算算法分析
• 2.1 集中式skyline计算算法
• 2.1.1 适用环境与性能要求
• 2.1.2 现有主要算法
• 2.1.3 算法比较小结
• 2.2 分布式skyline计算算法
• 2.2.1 分布式数据库
• 2.2.2 对等网络
• 2.2.3 移动自组织网络
• 2.3 其它skyline计算算法
• 2.4 与top-k查询的关系
• 2.5 总结
• 第三章 基于反馈的分布式skyline计算算法
• 3.1 问题定义
• 3.2 基本算法
• 3.3 基于反馈的分布式skyline计算算法（FDS）
• 3.3.1 算法概述
• 3.3.2 不恰当反馈的隐患
• 3.3.3 有利反馈机制
• 3.3.4 覆盖检查
• 3.3.5 算法总述
• 3.3.6 具体实例
• 3.4 实验评估
• 3.4.1 参数调整
• 3.4.2 渐进性比较
• 3.4.3 网络带宽比较
• 3.5 小结
• 第四章 基于Chord的skyline计算算法
• 4.1 结构化对等网络Chord
• 4.2 问题定义
• 4.3 基于Chord的Skyline计算
• 4.3.1 基本算法
• 4.3.2 数据映射方法
• 4.3.3 Chord上的Skyline计算算法
• 4.3.4 负载均衡
• 4.4 实验评估
• 4.4.1 带宽消耗
• 4.4.2 节点访问量
• 4.5 小结
• 第五章 总结与展望
• 参考文献
• 致谢
• 发表/录用论文
• 已投稿论文