IEEE Transactions on Knowledge and Data Engineering · 2009 · 67 citations · 34 references
ComputingComputer ScienceComputer SystemsDatabasesDistributed SystemsInformation RetrievalData PartitioningDistributed AlgorithmsDistributed ComputingDistributed Data ProcessingQuery ProcessingSpatial PartitioningBandwidthBandwidth ManagementDistributed Data PartitioningFeedbackHorizontal PartitioningPartition OptimizationPartitioningVertical Partitioning
We consider skyline computation when the underlying data set is horizontally partitioned onto geographically distant servers that are connected to the Internet. The existing solutions are not suitable for our problem, because they have at least one of the following drawbacks: (1) applicable only to distributed systems adopting vertical partitioning or restricted horizontal partitioning, (2) effective only when each server has limited computing and communication abilities, and (3) optimized only for skyline search in subspaces but inefficient in the full space. This paper proposes an algorithm, called feedback-based distributed skyline (FDS), to support arbitrary horizontal partitioning. FDS aims at minimizing the network bandwidth, measured in the number of tuples transmitted over the network. The core of FDS is a novel feedback-driven mechanism, where the coordinator iteratively transmits certain feedback to each participant. Participants can leverage such information to prune a large amount of local data, which otherwise would need to be sent to the coordinator. Extensive experimentation confirms that FDS significantly outperforms alternative approaches in both effectiveness and progressiveness.
34
A scalable content-addressable network
Sylvia Ratnasamy, Paul Francis, Mark Handley et al. · 2001 · 6.4K citations · Full text
S. Borzsony, Donald Kossmann, Konrad Stocker · 2002 · 2.2K citations
A scalable content-addressable network
Sylvia Ratnasamy, Paul Francis, Mark Handley et al. · ACM SIGCOMM Computer Communication Review · 2001 · 1.8K citations
Optimal aggregation algorithms for middleware
Ronald Fagin, Amnon Lotem, Moni Naor · Journal of Computer and System Sciences · 2003 · 941 citations
On Finding the Maxima of a Set of Vectors
H. T. Kung, Fabrizio Luccio, F. P. Preparata · Journal of the ACM · 1975 · 913 citations · Full text