An Efficient Algorithm for Distributed Skyline Queries
Shuqiang Yang · Computer Engineering and Science · 2007
This paper presents a new algorithm to answer Skyline queries in distributed environments.The existing 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.