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

Algorithm on Computing Skyline over Probabilistic Data Stream

作　　者：孙圣力[1] 戴东波[2] 黄震华[3] 张齐勋[1] 周立新[1] 

机构地区：[1]北京大学软件与微电子学院,北京102600 [2]复旦大学计算机科学技术学院,上海200433 [3]同济大学电信学院,上海200092

出　　处：《电子学报》2009年第2期285-293,共9页Acta Electronica Sinica

基　　金：国家973重点基础研究发展规划(No.2005CB321905)

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

关 键 词：概率数据流 SKYLINE 逐步求精 提前淘汰 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]