Distributed Skyline Retrieval with Low Bandwidth Consumption
Distributed Skyline Retrieval with Low Bandwidth Consumption
复制标题
低带宽消耗的分布式天际线检索
DOI：
10.1109/tkde.2008.142
复制
发表时间：
2009-03
影响因子：
8.9
通讯作者：
中科院分区：
文献类型：
--
作者：
我们认为天际线计算时，底层数据集是水平分区到地理上遥远的服务器连接到互联网。现有的解决方案不适合我们的问题，因为它们具有以下缺点中的至少一个：（1）仅适用于采用垂直分区或受限水平分区的分布式系统，（2）仅在每个服务器具有有限的计算和通信能力时有效，以及（3）仅针对子空间中的天际线搜索进行优化，但在全空间中效率低下。本文提出了一种基于反馈的分布式轮廓线（FDS）算法，以支持任意水平分割。FDS旨在最小化网络带宽，以通过网络传输的元组的数量来衡量。FDS的核心是一种新颖的反馈驱动机制，协调器迭代地向每个参与者发送某些反馈。参与者可以利用这些信息来修剪大量的本地数据，否则这些数据将需要发送给协调器。广泛的实验证实，FDS显着优于替代方法的有效性和进步性。
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.
登录
查看更多内容
DOI：
10.1109/icde.2007.367894
发表时间：
2007-04
期刊：
2007 IEEE 23rd International Conference on Data Engineering
影响因子：
--
作者：
Ping Wu;D. Agrawal;Ö. Eğecioğlu;A. E. Abbadi
通讯作者：
Ping Wu;D. Agrawal;Ö. Eğecioğlu;A. E. Abbadi
DOI：
10.1109/icde.2006.142
发表时间：
2006-04
期刊：
22nd International Conference on Data Engineering (ICDE'06)
影响因子：
--
作者：
Zhiyong Huang;Christian S. Jensen;Hua Lu;B. Ooi
通讯作者：
Zhiyong Huang;Christian S. Jensen;Hua Lu;B. Ooi
DOI：
10.1145/322092.322095
发表时间：
1978-10
期刊：
J. ACM
影响因子：
--
作者：
J. Bentley;H. T. Kung;M. Schkolnick;C. Thomborson
通讯作者：
J. Bentley;H. T. Kung;M. Schkolnick;C. Thomborson
DOI：
10.1109/icde.2005.137
发表时间：
2005-04
期刊：
21st International Conference on Data Engineering (ICDE'05)
影响因子：
--
作者：
Xuemin Lin;Yidong Yuan;Wei Wang-;Hongjun Lu
通讯作者：
Xuemin Lin;Yidong Yuan;Wei Wang-;Hongjun Lu
DOI：
10.1016/b978-155860869-6/50032-9
发表时间：
2002-08
期刊：
--
影响因子：
--
作者：
Donald Kossmann;Frank Ramsak;S. Rost
通讯作者：
Donald Kossmann;Frank Ramsak;S. Rost