一种高效的分布式Skyline查询算法

An Efficient Algorithm for Distributed Skyline Queries

本文提出了一种新的分布环境中的Skyline查询算法——一种新的四阶段Skyline算法FDSL。现有的算法,如Distributed Skylining算法,在节点数m较大时会消耗大量的网络带宽。FDSL算法在任意数据集上只需要四次交互就能完成,并且通过剪除不必要的对象来减少网络带宽的消耗。本文通过模拟数据验证了FDSL算法的效率。实验表明,当节点数m大于4时,FDSL算法的性能比现有算法提高了15%～30%。

This paper presents a new algorithm to answer Skyline queries in distributed environments. The exusting algorithms, such as the Distributed Skylining Algorithm, consume an excessive amount of bandwidth when the number of nodes,m, is high. We propose a novel algorithm called Four-phase Distributed Skylining （FDSL）. FDSL terminates in four round-trips regardless of data input, and reduces the consumption by pruning away ineligible objects. We verify the effectiveness of FDSL empirically using synthetic data sets. We show that, for most data sets, FDSL reduces the overall communication cost by about 15%-30% compared with the existing algorithms when the number of nodes,m, is greater than 4.