不确定性数据管理技术研究综述(5)

p(X ,

∫

ab

Y)(z)dz.基于上述距离公式,他们改进了DB2SCAN[91]算法,提出了FDBSCAN算法[92];改进了OPTICS[93]算法,提出了FOPTICS算法,解决层次

聚类问题[94].Ngai等人提出了UK2means算法[95],基本思想与k2means类似:各数据点将被距离最近的簇吸收.为了提高计算效率,UK2means算法将数据点可能出现的区域用最小边界矩形(MBR)描述,设计剪枝策略减少运算量.文献[96]提出了针对移动对象的聚类方法,主要思路也是计算从各个对象到簇中心点的期望距离.文献[97]提出的方法采用一个函数来计算不确定的点到任意一个中心的距离的期望值,然后再运用传统的聚类方法进行计算.

上述工作均面向传统的静态数据库,无法适应高速的数据流模型.Aggarwal与Yu将CF结构扩展为ECF结构,增加了描述不确定性的组成部分,以解决数据流上的聚类问题[83].算法主要改进了新到点与簇中心点的距离与每个簇的接收半径的计算过程.

Bi等人[98]提出了一种面向不确定性数据库的分类算法,它基于支持向量机(SupportVectorMa2chine,SVM)技术.

∑p(w)×Q(w).

i

i

当数据集合较大时,通过枚举所有可能世界实例的方法并不可行.Burdick等人首先研究了在数据独立情况下的优化方法.该方法首先构造EDB(ExtendedDataBase),然后再单遍扫描EDB,快速计算查询结果[39].文献[90]则改进了计算EDB的方法,进一步提高查询效率.

数据独立的情况较易处理,而若数据之间存在约束条件时则更为复杂.典型的约束条件如“:张三和李四的籍贯都是浙江省,但是他俩来自不同地级市”,则不可能存在如下可能世界实例:{(张三,文成县),(李四,平阳县),…}①.首先在一个不精确的数据库D上生成所有可能世界实例w1,…,wn,然后运用规则,仅剩下m个有效的实例,各可能世界实

6　总　结

近年来,不确定性数据广泛出现在诸多应用领

①文成县与平阳县均属于浙江省温州市

.

关于不确定数据管理的分析与研究

12计　　算　　机　　学　　报

[2]

2009

年

域之中,例如传感器网络、RFID应用、数据集成、

LBS、Web应用等,为数据管理技术提出了如下要求.(1)丰富的数据类型,包括结构化的关系数据、半结构化数据、流数据、移动对象数据以及其他领域相关数据等.(2)广泛性,数据处理的各个环节均可能存在不确定性,包括原始数据采集、预处理与集成、存储与索引、查询分析处理等.(3)繁多的查询类别,例如关系操作、数据世系、数据挖掘、模式匹配等.(4)概率维的冲击,概率维与普通数据维不同,会极大地影响查询定义、查询处理、结果定义等关键环节.

可能世界模型是不确定性数据管理领域中最通用的数据模型.尽管存在针对不同应用的具体模型,但这些模型通常均可转化为可能世界模型,节所示.界实例,1,但.因此,可以在,然后再合并生成最终的查询结果.而事实上,由于可能世界实例的数量过于庞大,无法利用上述方法进行计算.目前,典型的不确定性解决方案大量采用排序、剪枝等启发式技术,从而大大减少计算量,快速获取查询结果.

在不确定性数据管理领域仍然存在很多工作有待完成:

(1)许多在确定性数据管理领域所遇到的问题在不确定数据管理领域也非常重要,可以将这些查询问题搬到不确定数据管理领域上,以寻求解决方案.

(2)由于概率维的存在,不确定数据管理领域存在一些特有的查询问题,需要找出这些查询并设计处理算法.例如,现有4种不确定top2k查询,包括U2Topk、U2kRanks、PT2k、Pk2Topk.

(3)寻求在新模型定义下的查询处理方法.尽管大家都使用可能世界模型,但是不同应用场景下的模型仍然有所区别.事实上,不确定性XML处理技术的提升总是伴随着不确定性XML模型定义的更新.

(4)需要针对不确定性查询设计更优秀的算法.

参考

[1]

LiJian2Zhong,LiJin2Bao,ShiSheng2Fei.Concepts,issuesandadvanceofsensornetworksanddatamanagementofsen2sornetworks.JournalofSoftware,2003,14(10):171721727(inChinese)

(李建中,李金宝,石胜飞.传感器网络及其数据管理的概

念、问题与进展.软件学报,2003,14(10):171721727)

[3]

GuYu,YuGe,ZhangTian2Cheng.RFIDcomplexeventprocessingtechniques.JournalofFrontiersofComputerSci2enceandTechnology,2007,1(3):2552267(inChinese)(谷峪,于戈,张天成.RFID复杂事件处理技术.计算机科

学与探索,2007,1(3):255)

[4]

MadhavanJ,Cohen,HalevyA,JefferyS,KoD,YuC.Web:Youcanaffordtopayas/oft33rdBiennialConferenceonIn2SystemsResearch.Asilomar,2007:3422350Fromdataprivacytolocationprivacy:Modelsandalgorithms(tutorial)//Proceedingsofthe33rdInternationalConferenceonVeryLargeDatabases.Vienna,2007:142921430[6]

SamaratiP,SweeneyL.Generalizingdatatoprovideano2nymitywhendisclosinginformation(abstract)//Proceedingsofthe17thACMSIGACT2SIGMOD2SIGARTSymposiumonPrinciplesofDatabaseSystems.Seattle,1998:188[7]

CavalloR,PittarelliM.Thetheoryofprobabilisticdatabas2es//Proceedingsofthe13thInternationalConferenceonVeryLargeDataBases.Brighton,1987:71281[8]

BarbaraD,Garcia2MolinaH,PorterD.Themanagementofprobabilisticdata.IEEETransactionsonKnowledgeandDa2taEngineering,1992,4(5):4872502[9]

FuhrN,RollekeT.Aprobabilisticrelationalalgebrafortheintegrationofinformationretrievalanddatabasesystems.ACMTransactionsonInformationSystems,1997,15(1):32266

[10]

ZimanyiE.Queryevaluationinprobabilisticdatabases.The2oreticalComputerScience,1997,171(122):1792219

[11]

LakshmananLVS,LeoneN,RossR,SubrahmanianVS.ProbView:Aflexibledatabasesystem.ACMTransactionsonDatabaseSystems,1997,22(3):4192469

[12]

AbiteboulS,KanellakisP,GrahneG.Ontherepresentationandqueryingofsetsofpossibleworlds.ACMSIGMODRe2cord,1987,16(3):34248

[13]

GreenTJ,TannenV.Modelsforincompleteandprobabilis2ticinformation.IEEEDateEngineeringBulletin,2006,29(1):17224

[14]

BabcockB,BabuS,DatarM,MotwaniR,WidomJ.Mod2elsandissuesindatastreamsystems//Proceedingsofthe21stACMSIGMOD2SIGACT2SIGARTSymposiumonPrin2ciplesofDatabaseSystems.Madison,2002:1216

[15]

JinChe2Qing,QianWei2Ning,ZhouAo2Ying.Analysisandmanagementofstreamingdata:Asurvey.JournalofSoft2ware,2004,15(8):117221181(inChinese)

文献

DeshpandeA,GuestrinC,MaddenS,HellersteinJM,HongW.Model2drivendataacquisitioninsensornetworks//Proceedingsofthe30thInternationalConferenceonVeryLargeDataBases.Toronto,2004:5882599

关于不确定数据管理的分析与研究

1期周傲英等:

不确定性数据管理技术研究综述

[30]

13

(金澈清,钱卫宁,周傲英.流数据分析与管理综述.软件学HungE,GetoorL,SubrahmanianVS.PXML:Aprobabi2listicsemistructureddatamodelandalgebra//Proceedingsofthe19thIEEEInternationalConferenceonDataEngineering.Bangalore,2003:4672478

报,2004,15(8):117221181)

[16]

R&# …… 此处隐藏：4752字，全部文档内容请下载后查看。喜欢就下载吧 ……