高效处理分布式数据流上skyline持续查询算法.pdf

文档介绍：ISSN 1000-9825, CODEN RUXUEW E-mail: ******@iscas.
Journal of Software, , , July 2009, −1853
doi: . Tel/Fax: [phone]
© by Institute of Software, the Chinese Academy of Sciences. All rights reserved.

∗
高效处理分布式数据流上 skyline 持续查询算法
孙圣力+, 李金玖, 朱扬勇
(复旦大学计算机与信息技术系,上海 200433)
Efficient Processing of Continuous Skyline Query over Distributed Data Streams
SUN Sheng-Li+, LI Jin-Jiu, ZHU Yang-Yong
(Department puting and Information Technology, Fudan University, Shanghai 200433, China)
+ Corresponding author: E-mail: ******@fudan.
Sun SL, Li JJ, Zhu YY. Efficient processing of continuous skyline query over distributed data streams.
Journal of Software, 2009,20(7):1839−1853. /1000-9825/
Abstract: To reduce system delay and munication load, this paper proposes an efficient algorithm
BOCS (based on the change of skyline) which is out of share-nothing strategy. BOCS is to solve this issue through
progressive refinement by two steps. This paper provides analytical results and they show that BOCS is optimal in
terms of munication overhead among all algorithms which are out of share-nothing strategy. Theoretical
analysis and extensive experiments demonstrate that these methods are efficient, stable and scalable.
Key words: distributed data stream; skyline; continuous query; communication optimal
摘要: 基于非共享策略,围绕着降低系统反应延迟与通信负荷的目标,提出了一种分两阶段渐进求解的分布式
算法 BOCS(based on the change of skyline),并对算法的关键实现环节,如协调站点与远程站点间的通信、skyline 增
量的计算等进行了系统优化,,在所有基于非
共享策略的算法中,BOCS ,所提出的算法高效、稳定且具有良好的可扩
展性.
关键词: 分布式数据流;skyline;持续查询;通信最优
中图法分类号: TP311 文献标识码: A
分布式数据流广泛存在于环境监测、交通监控、
,skyline 查询[1]近来引起了研
[2]:存在某股票数据库,
浏览该数据库,试图从最近 3 查询
为这类应用提供了一个可行的解决途径,,用户只需
考虑属于 skyline 集合的那些对象,