分布式环境下skyline计算算法的研究

《分布式环境下skyline计算算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、目录摘要︼汁什咔勺︺O0，J门︸︼人0、八︸月、月，了月1一︸、口︸‘，U口QOt了自U01AbstraCt第一章绪论1.1研究背景与现状...……1.1.1skyline的定义与性质1.1.2skyline计算的应用.…1.1.3skyline计算的现状与挑战1.2研究内容......·……1.3本文结构.......……第二章现有Skyline计算算法分析2.1集中式skyline计算算法…2.1.1适用环境与性能要求2.1.2现有主要算法j通1，.1，二1J一1盛工.s，..e.2.1.3算法比较小结2.2分布式skyhne

2、计算算法…2.2.1分布式数据库2.2.2对等网络.……2.2.3移动自组织网络…2.3其它skyhne计算算法2.4与top一左查询的关系2.5总结......··……第三章基于反馈的分布式skyline计算算法9，一石一弓，1勺白0Q0气O凡了1」O3.l问题定义...........……3.2基本算法...........……3.3基于反馈的分布式skyllne计算算法(FDS)3.3.1算法概述.......……3.3.2不恰当反馈的隐患……，.3.3.3有利反馈机制第i页3.3.4覆盖检查二2343579230673.3

3、.5算法总述二3.3.6具体实例3.4实验评估……3.4.1参数调整二3.4.2渐进性比较.3.4.3网络带宽比较3.5小结...……第四章基于Chord的skyline计算算法牛4中454:或牛气4，︶O，、勺n1人。1/︸、I护二占1︸。，nUO4.1结构化对等网络Chord.……4.2问题定义........……4.3基于Chord的Skyline计算..…4.3.1基本算法....……4.3.2数据映射方法4.3.3Chord上的Skyline计算算法4.3.4负载均衡...……4.4实验评估..…，.……4.4带宽消耗.

4、..……4.4.2节点访问量..……4.5小结第五章总结与展望参考文献致谢发表/录用论文已投稿论文第11页图目录一个Skyhne例子......……cAN网络上skyline计算的一个例子二3.1分布式skyhne计算的结构.……193.2l区间和覆盖243.324一个反馈的例子，，....……3.4覆盖检查..........……253.5计算和反馈步骤......……313.6丸的大小与带宽消耗量(反相关，l=1)343.7Z的大小与带宽消耗量(反相关，k=d)353.8渐进性比较(反相关)....……363.9渐进性比较(均

5、匀).....……373.10渐进性比较(NBA)·····……373.11渐进性比较(Color)……””383.12渐进性比较(Household)··……383.13维数与带宽消耗量....……393.14本地基数与带宽消耗量393.15服务器个数与带宽消耗量……394.1数据映射的一个例子434.2网络大小与带宽消耗量..……474.3数据库大小与带宽消耗量…，…44勺O刀C4.4节点访问量.........……第111页表目录﹃乙，一勺‘‘1.集中式skyline计算算法性能比较……ll垂直划分数据库上skyhne计算的

6、一个例子.l3今一︶﹃︶，、，j气一八U3.1常用符号.……3.2FDS算法的一个例子.3.3实验参数与值域…第iv页摘要一个多维数据库上的skyhne，是此数据库上不被其它任何数据点支配的点所组成的集合。Skyhne计算以其在多目标决策、数据挖掘、数据库可视化等方面的广阔应用获得了越来越多研究者的关注。本文以普通分布式数据库和结构化对等网络为目标，对分布式环境下的skyhne计算算法展开了深入的研究。当前，分布式数据库上的skyhne计算研究已经取得了初步进展，但已有的算法还远不能满足分布式环境下skyline计算的要求，因为它

7、们至少受限于以下三种情况中的一种:(l)假设数据是被垂直划分的;(2)仅支持满足某种特殊网络要求的水平划分的数据库;(3)专为具有较低计算能力的轻量移动设备设计。因此，本文提出了一种全新的基于反馈的分布式skyline计算算法，它以一种崭新的反馈机制为核心，采多轮计算模式，支持任意水平划分的数据库上的Skyhne计算。算法中传递的反馈信息能大量剪除非skyline的本地数据点，避免无用信息在网络中的传输，因而很大程度减少了网络带宽的消耗量。算法能快速地响应用户，并按用户规定的顺序逐渐返回计算结果，具有很好的用户可适应性和渐进性。本

8、文以在真实数据库和合成数据库上的大量实验衡量了算法的性能，证实了它是一个高效的分布式skyline计算算法。在此基础上，本文还对对等网络(PZP)上的skyline计算进行了研究。对等网络是分布式信息共享与搜索的一种重要平台，Chord作为对等网络