改进的概率数据流上Skyline查询算法  

An Improved Algorithm on Skyline Query over Probabilistic Data Stream

作　　者：杨艳艳[1] 赵雷[1] 杨季文[1] 

机构地区：[1]苏州大学计算机科学与技术学院,江苏苏州215006

出　　处：《苏州大学学报（工科版）》2012年第2期16-21,共6页Journal of Soochow University Engineering Science Edition (Bimonthly)

基　　金：国家自然科学基金资助项目(编号61073061)

摘　　要：SOPDS是一种概率数据流上的skyline查询算法,它主要采用网格索引结构,使用概率定界、逐步求精、提前淘汰和选择补偿等启发式规则从时间和空间两个方面进行系统的优化。通过对对象间支配关系的进一步分析,在SOPDS算法的基础上,增加有效的过滤策略和对象身份判定规则,实现了改进的算法(ISOPDS)。实验表明,ISOPDS算法能有效地减少查询响应时间。SOPDS is a kind of skyline query algorithm over probabilistic data stream. Based on grid index, a set of heuristic rules like probability bounds, progressive refinement, pre-elimination and selective compensation are devel- oped to improve the comprehensive performance of SOPDS on both CPU overhead and memory consumption. Through the analysis of the dominance relationship between uncertain objects, more effective filtering strategy and object iden- tity decision rule are added to SOPDS. And SOPDS is improved to a novel algorithm, ISOPDS. The experimental results show that ISOPDS could reduce the response time of skyline query effectively.

关 键 词：概率数据流 不确定数据 SKYLINE 连续查询 

分 类 号：TM753[电气工程—电力系统及自动化]