| 一种高效的分布式Skyline查询算法 |
| |
| 引用本文： | 邓波,贾焰,杨树强.一种高效的分布式Skyline查询算法[J].计算机工程与科学,2007,29(9):97-100. |
| |
| 作者姓名： | 邓波 贾焰 杨树强 |
| |
| 作者单位： | 1. 总参第六十三研究所,江苏,南京,210007;国防科技大学计算机学院,湖南,长沙,410073
2. 国防科技大学计算机学院,湖南,长沙,410073 |
| |
| 基金项目： | 国家高技术研究发展计划(863计划)
,
国家重点基础研究发展计划(973计划) |
| |
| 摘 要： | 本文提出了一种新的分布环境中的Skyline查询算法--一种新的四阶段Skyline算法FDSL。现有的算法，如Distributed Skylining算法，在节点数m较大时会消耗大量的网络带宽。FDSL算法在任意数据集上只需要四次交互就能完成，并且通过剪除不必要的对象来减少网络带宽的消耗。本文通过模拟数据验证了FDSL算法的效率。实验表明，当节点点数m大于4时，FDSL算法的性能比现有算法提高了15％～30％。
|
| 关 键 词： | FDSL分布式Skyline 固定交互次数 |
| 文章编号： | 1007-130X（2007）09-0097-04 |
| 修稿时间： | 2006-06-072006-10-12 |
An Efficient Algorithm for Distributed Skyline Queries |
| |
| DENG Bo,JIA Yan,YANG Shu-qiang.An Efficient Algorithm for Distributed Skyline Queries[J].Computer Engineering & Science,2007,29(9):97-100. |
| |
| Authors: | DENG Bo JIA Yan YANG Shu-qiang |
| |
| Affiliation: | 1.63rd Institute,Headquarters of General Staff,Nanjing 210007; 2. School of Computer Science, National University of Defense Technology, Changsha 410073,China |
| |
| Abstract: | 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. |
| |
| Keywords: | FDSL dis tribu ted Skyline fix-round- trip |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与科学》浏览原始摘要信息 |
|
点击此处可从《计算机工程与科学》下载全文 |
|
