论文部分内容阅读
随着数据爆炸式的增长,如何从海量数据筛选出人们感兴趣的信息,成为当今数据库领域的一个重要课题。Skyline计算通过维度间支配关系的定义,提供了满足上述需求的查询方法。在多标准决策,数据挖掘与可视化,用户偏好查询等众多方面,Skyline查询起到重要的作用,吸引了众多研究学者的关注。近年来学者们提出了众多单机环境下集中式Skyline计算方法。 然而,近年来数据的暴增使得单机的Skyline计算遇到瓶颈,本文在Master-Worker结构基础上,结合Kd树和Z曲线模型,实现了一个通用的分布式Skyline查询方法。 本文总结了目前集中式的Skyline算法,探讨了各个算法的优缺点和使用场景;分析了分布式Skyline查询基于对等网络的实现方法,针对对等网络中的几点不足,提出了基于Master-Worker结构的分布式Skyline查询方法。 在Master节点的设计与实现中,从数据分配方法出发,总结了几种一维的分配方法。结合Skyline的查询场景,本文提出根据Skyline的查询维度分配输入集,并结合kd树模型实现了Master节点的分配算法。 在Worker节点的设计与实现中,本文探讨了Z曲线适合Skyline查询的几点因素,并结合Z曲线模型实现了Worker节点的并行Skyline算法。 针对上述的算法,本文进行了大量的实验。从数据的维度、分布与大小三个维度构造多种数据集,通过实验证明了算法的效率。