电子学报 ›› 2009, Vol. 37 ›› Issue (2): 285-293.

• 论文 • 上一篇    下一篇

概率数据流上Skyline查询处理算法

孙圣力1, 戴东波2, 黄震华3, 张齐勋1, 周立新1   

  1. 1. 北京大学软件与微电子学院,北京 102600;2. 复旦大学计算机科学技术学院,上海 200433;3. 同济大学电信学院,上海 200092
  • 收稿日期:2008-01-27 修回日期:2008-07-20 出版日期:2009-02-25 发布日期:2009-02-25

Algorithm on Computing Skyline over Probabilistic Data Stream

SUN Sheng-li1, DAI Dong-bo2, HUANG Zhen-hua3, ZHANG Qi-xun1, ZHOU Li-xin1   

  1. 1. School of Software and Microelectronics,Peking University,Beijing 102600,China;2. School of Computer Science and Technology,Fudan University,Shanghai 200433,China;3. School of Electronics and Information,Tongji University,Shanghai 200092,China
  • Received:2008-01-27 Revised:2008-07-20 Online:2009-02-25 Published:2009-02-25

摘要: 概率数据流管理与分析逐步引起了研究者们的关注.Skyline查询技术是近年来数据库领域的研究热点.此前相关工作仅限于静态数据集或传统确定性数据流上的Skyline查询处理,尚无人考虑概率数据流上的Skyline计算问题,本文提出的SOPDS算法则较好地解决了该问题.在采用适应性更强的网格索引的基础上,提出了概率定界、逐步求精、提前淘汰与选择补偿等启发式规则对算法从时间和空间两方面进行了系统地优化.实验表明,算法在时间与空间上具有较高的整体性能.

关键词: 概率数据流, Skyline, 逐步求精, 提前淘汰

Abstract: Management and analysis of uncertain,probabilistic data stream has attracted considerable attention within database community.Skyline query processing is an open question recently.Although previous work has addressed skyline computations over static data or traditional data stream,skyline computation over probabilistic data stream is still at large.We propose an efficient algorithm SOPDS to handle this issue.Based on more adaptable grid index,a set of heuristic rules like probability bounding,progressive refinement,pre-elimination and selective compensation are developed to improve the comprehensive performance of SOPDS from point of reducing both CPU overhead and memory consumption.Massive experiments demonstrate that SOPDS is of high overall performance.

Key words: probabilistic data stream, skyline, progressive refinement, pre-elimination strategy

中图分类号: