一种渐进的分布式Skyline查询算法

摘要

Skyline查询被引入到数据库后，作为一个多目标决策、数据挖掘、数据库可视化等方面的重要工具，逐渐成为了一个研究热点。目前对于集中式Skyline查询的研究已经比较成熟，但分布式环境下的Skyline查询研究还较少，主要问题在于(1)假设数据是垂直划分的;(2)基于特定的网络拓扑结构;(3)网络通信代价的优化较少;(4)需要等到算法执行完才能输出结果响应用户。
　　通过对目前已有的集中式Skyline算法和分布式Skyline算法的研究，并针对已有缺点，本文提出了一种在数据水平划分下的渐进的分布式Skyline查询算法，适用于任意互联的网络结构。该方法包括预处理阶段和迭代阶段，在预处理阶段所有参与者在本地根据用户兴趣函数计算本地Skyline集合并统计所有点支配其它点的个数，协调者维护一个全局支配点集合。在迭代阶段的每一轮中，参与者根据全局支配点集更新本地支配点集，并对本地数据进行剪枝;协调者根据参与者发送的局部Skyline集合并按用户兴趣函数值输出全局Skyline给用户，再根据参与者发送的支配其它点数集合更新全局支配点集，计算完毕时通过比对全局支配点数和预处理阶段上传支配点数验证算法是否正确。该算法通过迭代保证了渐进性，即每次迭代均有全局Skyline输出给用户;通过用户兴趣函数保证了友好性，即可根据用户的兴趣决定全局Skyline输出顺序;通过比对支配点数可验证算法执行过程中是否出现网络错误。在独立、正相关和反相关数据集上的大量对比实验表明，该算法与分布式BNL和FDS算法相比能有效减少网络开销，提高计算效率，并渐进地返回最终结果。