论文摘要
Skyline计算就是从海量的数据中找出人们最感兴趣的信息的一种方法,由于skyline查询在数据挖掘、多目标决策、数据库可视化等方面都有很重要的作用,从而吸引了众多研究学者的关注,成为近年来数据库技术领域的一项重要研究课题。而chord网络作为对等网络的代表性协议,因其良好的性能和简单灵巧的设计也受到研究者的青睐。目前,对于分布式环境下的skyline计算已经取得了初步进展,但是对对等网络环境下的skyline计算的研究还非常匮乏,基于chord网络上的skyline计算的研究还仅仅局限在静态数据集上。因此,本文对chord网络上动态数据集中的skyline计算算法展开了深入的研究。首先,本文分析了现有的集中式skyline计算算法的优缺点及其使用环境、分布式环境下和对等网络中的skyline计算算法,为下文算法的提出做了铺垫。其次,本文结合chord网络静态数据skyline计算算法、分布式环境下的skyline计算算法及滑动窗口模型的思想,首次提出了在chord网络中处理动态数据的skyline计算算法。通过数据映射的操作后,该算法可以对数据渐进的处理并把持续得到的skyline点输出给用户,由此实现了渐进性。而且该算法在每个结点上通过窗口模型都对数据点进行了影响时间的处理和过期处理,剪除了很多过期的和不可能成为skyline点的本地数据点;而且在获得全局skyline集合的算法中通过传输数据增量,大大减少了网络中结点之间的数据传输量,因此大大减小了网络带宽的消耗。通过仿真实验还证明了其负载均衡性。理论分析和实验结果均证明该算法是一种符合chord网络特点的处理动态数据的准确高效的skyline计算算法。最后,在以上基础上,本文又对chord网络上的skyline计算进行了扩展,提出了在动态数据环境下基于chord网络的约束区间的skyline计算算法。该算法主要完成在chord网络中计算某时间区间内的skyline集合。在规定的约束时间到达前,依然按照上面所提出的算法执行,在各个结点上维持一个本地skyline集合;当约束时间到达时,则无需再进行影响时间的处理和过期处理;当约束时间区间过后,该算法执行结束。该算法可以帮助用户获得在其感兴趣时间内的skyline集合,并通过仿真实验证明了该算法的正确性和可行性。