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

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

第32卷　第1期2009

年1月

计　　算　　机　　学　　报

CHINESEJOURNALOFCOMPUTERS

Vol.32No.1

Jan.2009

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

周傲英　金澈清　王国仁　李建中

1)

3)

1)1)2)3)

(华东师范大学软件学院上海市高可信计算重点实验室　上海　200062)

2)(东北大学信息科学与工程学院　沈阳　110004)

(哈尔滨工业大学计算机科学与技术学院　哈尔滨　150001)

摘　要　随着数据采集和处理技术的进步,人们对数据的不确定性的认识也逐步深入.、军事、物流、金

融、电信等领域的具体应用中,数据的不确定性普遍存在.,它们可以以关系型数据、半结构化数据、流数据或移动对象数据等形式出现.目前,研究者已经提出了多种针对不确定数据的数据模型..可能世界模型从一,1.尽管可以首先分别为各个实例计算查询结果,,但由于可能世界实例的数量远大于不确定性数据库的规模,,、剪枝等启发式技术设计新型算法,以提高效率.,综述了数据模型、数据预处理与集成、存储与索引、.

关键词　;可能世界模型;数据集成;世系;不确定数据流中图法分类号TP393　　　DOI号:10.3724/SP.J.1016.2009.00001

ASurveyontheManagementofUncertainData

ZHOUAo2Ying1　JINChe2Qing1　WANGGuo2Ren2　LIJian2Zhong3

1)

2)3)

))))

(ShanghaiKeyLaboratoryofTrustworthyComputing,SoftwareEngineeringInstitute,EastChinaNormalUniversity,Shanghai

(SchoolofInformationScienceandEngineering,NortheasternUniversity,Shenyang　110004)(SchoolofComputerScienceandTechnology,HarbinInstituteofTechnology,Harbin　150001)

200062)

Abstract　Theimportanceofthedatauncertaintywasstudieddeeplywiththerapiddevelopmentindatagatheringandprocessinginvariousfields,inclusiveofeconomy,military,logistic,fi2nanceandtelecommunication,etc.Uncertaindatahasmanydifferentstyles,suchasrelationaldata,semistructureddata,streamingdata,andmovingobjects.Accordingtoscenariosanddatacharacteristics,tensofdatamodelshavebeendeveloped,stemmingfromthecorepossibleworldmodelthatcontainsahugenumberofthepossibleworldinstanceswiththesumofprobabilitiesequalto1.However,thenumberofthepossibleworldinstancesisfargreaterthanthevolumeoftheuncertaindatabase,makingitinfeasibletocombinemedialresultsgeneratedfromallofpossi2bleworldinstancesforthefinalqueryresults.Thus,someheuristictechniques,suchasorde2ring,pruning,mustbeusedtoreducethecomputationcostforthehighefficiency.Thispaperin2troducestheconcepts,characteristicsandchallengesinuncertaindatamanagement,proposestheadvanceoftheresearchonuncertaindatamanagement,includingdatamodel,preprocessing,in2tegrating,storage,indexing,andqueryprocessing.

Keywords　uncertaindata;possibleworldmodel;dataintegration;lineage;uncertainstream

收稿日期:2008209205.本课题得到国家自然科学基金(60803020)、上海市重点学科建设项目(B412)资助.周傲英,男,1965年生,教授,博士生导师,主要研究兴趣为数据管理与信息系统,包括:Web数据管理、中文Web基础设施、Web搜索与挖掘、数据流与数据挖掘、复杂事件处理与实时商务智能、不确定数据管理及其应用、数据密集的计算、分布存储与计算、对等计算及其数据管理、Web服务计算等.金澈清(通信作者),男,1977年生,博士,副教授,主要研究方向为数据流管理、不确定性数据管理技术等.E2mail:cqjin@.王国仁,男,1966年生,教授,博士生导师,主要研究领域为XML数据管理、生物信息学、分布与并行数据库、多媒体索引技术、并行计算等.李建中,男,1950年生,教授,博士生导师,主要研究领域为数据库、并行计算等.

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

2计　　算　　机　　学　　报2009

年

1　引　言

近四十年来,传统的确定性数据(deterministic

data)管理技术得到了极大的发展,造就了一个数百亿的数据库产业.数据库技术和系统已经成为信息化社会基础设施建设的重要支撑.在传统数据库的应用中,数据的存在性和精确性均确定无疑.近年来,随着技术的进步和人们对数据采集和处理技术理解的不断深入,不确定性数据(uncertaindata)得到了广泛的重视.在许多现实的应用中,例如经济、军事、物流、金融、电信等领域,数据的不确定性普遍存在,不确定性数据扮演着关键角色.理技术却无法有效管理不确定性数据,术的兴趣.

.可能是原,也可能是为了满足特殊应用目的或是在处理缺失值、数据集成过程中而产生的.

(1)原始数据不准确.这是产生不确定性数据最直接的因素.首先,物理仪器所采集的数据的准确度受仪器的精度制约.其次,在网络传输(特别是无线网络传输)过程中,数据的准确性受到带宽、传输延时、能量等因素影响.还有,在传感器网络应用[122]与RFID应用[3]等场合,周围环境也会影响原始数据的准确度.

(2)使用粗粒度数据集合.很明显,从粗粒度数据集合转换到细粒度数据集合的过程会引入不确定性.例如,假设某人口分布数据库以乡为基础单位记录全国的人口数量,而某应用却要求查询以村为基础单位的人口数量,查询结果就存在不确定性.

(3)满足特殊应用目的.出于隐私保护等特殊

目的,某些应用无法获取原始的精确数据,而仅能够得到变换之后的不精确数据.

(4)处理缺失值.缺失值产生的原因很多,装备故障、无法获取信息、与其他字段不一致、历史原因等都可能产生缺失值.一种典型的处理方法是插值,插值之后的数据可看作服从特定概率分布.另外,也可以删除所有含缺失值的记录,但这个操作也在一定程度上变动了原始数据的分布特征.

(5)数据集成.不同数据源的数据信息可能是不一致的,.例如,[4].

,还可能同时存在多种不确定.,基于位置的服务(Location2BasedService,LBS)[5]是移动计算领域的核心问题,在军事、通信、交通、服务业等方面有着广泛的应用.LBS应用获取各移动对象的位置,为用户提供定制服务,该过程存在若干不确定性.首先,受技术手段(例如GPS技术)限制,移动对象的位置信息存在一定误差.其次,移动对象可能暂时不在服务区,导致LBS应用采集的数据存在缺失值情况.最后,某些查询要求保护用户的隐私信息,必须采用“位置隐私”等方式处理查询[6].

实际上,针对不确定性数据的研究工作已经有几十年历史了.从20世纪80年代末开始,针对概率数据库(probabilisticdatabase)的研究工作就从未间断过[7211].这类研究工作将不确定性引入到关系数据模型中去,取得了较大进展.近年来,针对不确定性数据的研究工作则在更广的范围内取得了更大的进展,即在更丰富的数据类型上处理更多种类的查询任务.图1描述了不确定性数据管理技术的典型框架,它包含4大部分:模型定义、预处理与集成、存储与索引和查询分析处理

.

图1　不确定性数据管理的框架

　　模型定义.定义与应用场景相匹配的数据模型

是不确定性数据管理的首要任务.在不确定性数据管理领域,最常用的模型是可能世界模型(possibleworldmodel)[12213].该模型从一个不确定性数据库演化出很多确定的数据库实例(称为可能世界实例),而且所有实例的概 …… 此处隐藏：3854字，全部文档内容请下载后查看。喜欢就下载吧 ……