RISQ:一种高效处理概率数据流上Skyline查询的算法  

RISQ:AN EFFICIENT ALGORITHM FOR SKYLINE QUERYP ROCESSING ON PROBABILISTIC DATA STREAM

作　　者：欧阳树生 李金玖[2] 覃明贵[1,2] 朱扬勇[2] 

机构地区：[1]上海宝信软件有限公司,上海201203 [2]复旦大学计算机科学技术学院,上海200433

出　　处：《计算机应用与软件》2009年第12期167-169,173,共4页Computer Applications and Software

摘　　要：多维空间的Skyline分析在多标准决策领域有着广泛的应用。以往的工作仅关注确定数据集或数据流上的Skyline处理,而概率数据流上的Skyline查询未被研究过。基于"可能世界"的语义,提出了一种以R#树为索引的高效处理概率数据流上Sky-line查询的算法RISQ(R#-tree indexed Skyline query)。通过预淘汰机制和最小化概率补偿等策略来提高算法的性能。Multidimensional Skyline analysis is widely applied in multi-criteria decision-making area. Previous works of Skyline computation have been addressed on dataset or data stream only, but Skyline query on probabilistic data stream is at large. Based on ＂possible world＂ semantics, an effective R# tree indexed algorithm for Skyline query （RISQ） on probabilistic data stream is proposed to handle this issue. A set of pruning mechanism like pre-elimination and minimised probabilistic compensation strategy are developed to improve the overall performance of the algorithm.

关 键 词：概率数据流 SKYLINE 可能世界 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] U469.11[自动化与计算机技术—计算机科学与技术]