资源描述：
《概率数据流上skyline查询处理算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2期电子学报Vol.37No.22009年2月ACTAELECTRONICASINICAFeb.2009概率数据流上Skyline查询处理算法12311孙圣力,戴东波,黄震华,张齐勋,周立新(11北京大学软件与微电子学院,北京102600;21复旦大学计算机科学技术学院,上海200433;31同济大学电信学院,上海200092)摘要:概率数据流管理与分析逐步引起了研究者们的关注.Skyline查询技术是近年来数据库领域的研究热点.此前相关工作仅限于静态数据集或传统确定性数据流上的Skyline查询处理,尚无人考虑概率数据流上的Skyline计算问题,本文提出的SOPDS算法则较好地
2、解决了该问题.在采用适应性更强的网格索引的基础上,提出了概率定界、逐步求精、提前淘汰与选择补偿等启发式规则对算法从时间和空间两方面进行了系统地优化.实验表明,算法在时间与空间上具有较高的整体性能.关键词:概率数据流;Skyline;逐步求精;提前淘汰中图分类号:TP391141文献标识码:A文章编号:037222112(2009)0220285209AlgorithmonComputingSkylineoverProbabilisticDataStream12311SUNSheng2li,DAIDong2bo,HUANGZhen2hua,ZHANGQi2xun,ZHOULi2xin(
3、11SchoolofSoftwareandMicroelectronics,PekingUniversity,Beijing102600,China;21SchoolofComputerScienceandTechnology,FudanUniversity,Shanghai200433,China;31SchoolofElectronicsandInformation,TongjiUniversity,Shanghai200092,China)Abstract:Managementandanalysisofuncertain,probabilisticdatastreamhasat
4、tractedconsiderableattentionwithindatabasecommunity.Skylinequeryprocessingisanopenquestionrecently.Althoughpreviousworkhasaddressedskylinecomputationsoverstaticdataortraditionaldatastream,skylinecomputationoverprobabilisticdatastreamisstillatlarge.Weproposeanefficientalgo2rithmSOPDStohandlethis
5、issue.Basedonmoreadaptablegridindex,asetofheuristicruleslikeprobabilitybounding,progressiverefinement,pre2eliminationandselectivecompensationaredevelopedtoimprovethecomprehensiveperformanceofSOPDSfrompointofreducingbothCPUoverheadandmemoryconsumption.MassiveexperimentsdemonstratethatSOPDSisofhi
6、ghoverallperformance.Keywords:probabilisticdatastream;skyline;progressiverefinement;pre2eliminationstrategy度.评价以数据流的形式到达.在下表1中,对象ui代1引言表第i个到达系统的评价记录.现提出这样的查询:在[1]多维空间上的Skyline查询处理技术是近年来数最近到达的10个记录中找出至少以013的置信度保证据库领域的研究热点.Skyline在偏好查询、多标准决策不被其它电影支配的电影.支持以及数据挖掘与可视化等方面应用广泛.此前大量表1示例数据集[1,4,5]的工作都专注
7、于在静态数据集上计算Skyline,近Objectu1u2u3u4u5u6u7u8u9u10u11年来也出现了一些在滑动窗口中计算Skyline的研究成X01400195014801220165014301580164016201160137[2,3][15]Y01250135013801460142014401540170014001640180果.最近以来,一种被称为概率数据流的数据形e012001600140013001300150018001600
