计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (26): 162-165.DOI: 10.3778/j.issn.1002-8331.2008.26.049

• 数据库、信号与信息处理 • 上一篇    下一篇

一种高效的分布式序敏感轮廓查询处理算法

王 刚1,邓 波1,2,曾玮琳1   

  1. 1.中国人民解放军 73141部队,福建 南安 362301
    2.总参第六十三研究所,南京 210000
  • 收稿日期:2007-11-07 修回日期:2008-03-10 出版日期:2008-09-11 发布日期:2008-09-11
  • 通讯作者: 王 刚

Efficient algorithm for distributed rank-aware skyline query processing

WANG Gang1,DENG Bo1,2,ZENG Wei-lin1   

  1. 1.The 73141 Staff of PLA,Nan’an,Fujian 362301,China
    2.The 63rd Institute of the General Headquarters,Nanjing 210000,China
  • Received:2007-11-07 Revised:2008-03-10 Online:2008-09-11 Published:2008-09-11
  • Contact: WANG Gang

摘要: 提出了一种新颖的分布环境中的序敏感轮廓查询算法(即找出不被别的对象所“支配”的且聚集值较高的对象)。现有的算法在节点数m较大时会消耗大量的网络带宽。提出了一种新的分布式序敏感轮廓查询处理算法(Distributed Rank-aware Skylining,DRS)。DRS算法在任意数据集上只需要4次交互就能完成,并且通过剪除不必要的对象来减少通讯代价。通过模拟数据验证了DRS算法的效率。实验表明,当节点数m大于4时,DRS算法性能优于现有算法的性能。

Abstract: This paper presents a novel algorithm to answer skyline queries(e.g.“find the objects which are not “dominated” by other objects” and having higher aggregation value) in distributed environments.Existing algorithms consume an excessive amount of bandwidth when the number of nodes,m,is high.A novel algorithm is proposed called Distributed Rank-aware Skylining(DRS).DRS terminates in four round-trips regardless of data input,and reduces communication cost by pruning away ineligible objects.The effectiveness of DRS is verified empirically using synthetic data sets.The experiments results show that FDSL is superior to the existing alternatives in the terms of the network traffic when the number of nodes is greater than 4.