大数据可用性研究综述

大数据可用性研究综述

近年来，信息技术的快速发展，尤其是信息获取技术、物理信息系统、网络、物联网、社交网络等技术的快速发展导致了数据规模的爆炸增长。大数据被广泛使用。能源、工业、运输、服务、科学和文化、医疗和其他领域都积累了结核病、pb和if级大数据。这些数据为人类带来了巨大的幸福，已经成为信息社会的重要财富。例如，沃尔玛著名的全球知名超市必须在每个小时处理100多条用户要求，并维护超过2.5美元的数据库。在高能物理实验中，2008年开始投资的大型强对撞机每年生成超过25pb数据。社交网络的扎克现在拥有500万张照片。大数据蕴含着巨大的价值,对社会、经济、科学研究等各个方面都具有重要的战略意义,为人们更深入地感知、认识和控制物理世界提供了前所未有的丰富信息.例如,著名国际咨询机构Gartner在2012年预测全球大数据相关产业的规模将达到2320亿美元;2010年时代杂志刊载的医学界年度十大突破中,医疗科技公司CardioDX通过对1亿个基因样本的分析,最终识别出能够预测冠心病的23个主要基因;2009年Google的研究人员通过对每日超过30亿次搜索请求和网页数据的挖掘分析,在H1N1流感爆发几周就预测出流感传播;通过对微博等网络大数据的挖掘分析能够发现社会动态,预警重大和突发性事件.由于大数据的迅速涌现及其巨大价值,大数据已经引起国内外学术界、工业界和政府部门的广泛关注.美国等世界发达国家都制定和启动了大数据研究计划,投入大量资金支持大数据研究.我国对建设大数据管理基础设施的需求已经提出了指导性的方针.《国家中长期科技发展规划纲要(2006—2020)》指出:“信息领域要重点研究开发……海量存储和安全存储等关键技术”.《国民经济和社会发展第十二个五年规划纲要》提出:“重点研究……海量信息处理及知识挖掘的理论与方法……”.虽然目前大数据研究已经蓬勃兴起,但是工作主要集中在大数据的存储、管理、挖掘分析等方面,数据可用性问题没有得到足够重视.随着大数据的爆炸性增长,劣质数据也随之而来,导致数据质量低劣,极大地降低了数据的可用性.事实表明,大数据在可用性方面存在严重问题(以下简称数据可用性问题).国外权威机构的统计表明,美国企业信息系统中1%~30%的数据存在各种错误和误差,美国医疗信息系统中13.6%~81%的关键数据不完整或陈旧.国际著名科技咨询机构Gartner的调查显示,全球财富1000强企业中超过25%的企业信息系统中的数据不正确或不准确.随着大数据的不断增长,数据可用性问题将日趋严重,也必将导致源于数据的知识和决策的严重错误.数据可用性问题及其所导致的知识和决策错误已经在全球范围内造成了恶劣后果,严重困扰着信息社会.在美国,由于数据错误而引发的医疗事故,每年导致约98000名患者死亡,约占全部医疗事故致死人数的50%;由于数据错误和陈旧而引起的生产事故和决策失误,每年给美国工业企业造成约6110亿美元的损失,约占美国GDP的6%;美国零售业每年因标价数据错误而导致25亿美元的损失;在美国银行业,由于数据不一致问题而失察的信用卡欺诈在2006年就造成48亿美元的损失.据有关专家推算,在数据仓库项目的开发过程中,清理不洁数据通常需要花费30%~80%的开发时间和开发预算;数据可用性问题平均给每个企业增加的成本是该企业产值的10%~20%.此外,由于网络的普及,很多应用可以从不同的数据源抽取和集成信息,致使劣质信息产生和传播的风险达到了空前的水平.事实上,数据可用性问题是信息化社会中固有的问题.它们不仅在西方发达国家存在,而是在任何一个信息化社会都普遍存在.尽管我国尚未公布相关统计信息,我们没有理由相信我国不存在类似的问题.例如,我们通过对某国有大型企业信息中心的TB级数据的抽样检验,发现10%的信息存在各种类型的错误.综上所述,确保数据可用性是关系到大数据时代的国计民生、社会和谐等方面的一项重大战略任务,是圆满完成大数据管理基础设施建设、有效发挥大数据作用的重要前提.因此,深入开展数据可用性基础理论和关键技术的研究具有重要战略意义.本文介绍大数据可用性的基本概念,讨论大数据可用性的挑战和研究问题,并综述数据可用性方面的研究成果.1大数据应用的概念、挑战和研究1.1数据集合的特性我们认为,一个正确的大数据集合至少应满足以下5个性质.1)一致性:数据集合中每个信息都不包含语义错误或相互矛盾的数据.例如,数据(公司=“先导”,国码=“86”,区号=“10”,城市=“上海”)含有一致性错误,因为10是北京区号而非上海区号.又如,若银行信用卡数据库显示某持卡人在北京和新疆两地同时使用同一信用卡消费,则出现数据不一致,预示发生信用卡欺诈的可能.2)精确性:数据集合中每个数据都能准确表述现实世界中的实体.例如,某城市人口数量为4130465,数据库中记载为400万,宏观来看该信息是合理的,但不精确.一致的信息也可能含有误差,未必精确.在许多应用领域,信息精确性至关重要.3)完整性:数据集合中包含足够的数据来回答各种查询和支持各种计算.例如,某医疗数据库中的数据一致且精确,但遗失某些患者的既往病史,从而存在不完整性,可能导致不正确的诊断甚至严重医疗事故.4)时效性:信息集合中每个信息都与时俱进,不陈旧过时.例如,某数据库中的用户地址在2010年是正确的,但在2011年未必正确,即数据过时.据统计,商业和医疗信息库中平均50%的用户信息在2年内可能过时,而过时信息将会导致严重后果.5)实体同一性:同一实体在各种数据源中的描述统一.例如,为防止信用卡欺诈,银行需监测信用卡的使用者和持有者是否为同一人.又如,企业的市场、销售和服务部门可能维护各自的数据库,如果这些数据库之间没有共享统一的客户标识,企业的兼并和重组会使兼并后的公司的客户数据库中存在大量具有差异的重复客户信息,导致实体表达混乱.根据以上5个性质,我们可以如下定义数据可用性:一个数据集合满足上述5个性质的程度是该数据集合的可用性.1.2大数据或数据辅助的理论和技术研究确保数据可用性是一项十分困难的任务.考虑到大数据的数据量大、数据产生速度快、数据类型复杂、价值大密度低等4个特点,确保大数据可用性将变得难上加难.我们需要针对大数据的4个特点,解决如下大数据可用性的5个挑战性研究问题.1)高质量大数据获取与整合的理论和技术高质量数据的获取是确保信息可用性的重要前提.海量数据的来源多种多样(如复杂物理信息系统、物联网、Internet上的数据资源),数据模态千差万别(如关系数据、XML数据、图数据、流数据、标量数据、矢量数据),质量参差不齐,加工整合困难.这些问题在当今突飞猛进的传感网、信息物理融合系统和物联网及其产生的大数据背景下尤其严重.因此,我们需要解决如下挑战性问题:在数据获取阶段把住质量关,探索从物理信息系统等多数据源有效地获取高质量大数据的理论和方法,研究高效数据过滤方法,建立多模态大数据融合计算的理论和算法,实现高质量数据获取和精准整合,继而发现数据演变规律.2)完整的大数据可用性理论体系在数据可用性研究中,我们必须回答如下问题:如何形式化地表示数据可用性?如何从理论上判定数据可用性?如何定量地评估数据可用性?数据错误自动发现和修复的理论依据是什么?数据和数据质量融合管理(简称量质融合管理)的理论基础是什么?数据如何演化?没有一个完整的数据可用性理论体系,这些问题是无法回答的.因此,我们需要建立统一的框架,提出完整的数据可用性理论体系,解决如下挑战性问题:建立大数据可用性的理论模型、大数据可用性的形式化系统和推理机制、大数据可用性评估理论和算法、大数据量质融合管理的理论和算法、大数据演化机理、大数据可用性所涉及的计算问题的复杂性理论和算法设计与分析的新方法.3)数据错误自动检测与修复的理论和技术现有的数据可用性的方法和系统缺乏坚实的理论基础,不能实现自动的错误检测和修复.为了实现数据错误的自动检测和修复,我们需要在数据可用性理论体系基础上解决如下挑战性问题:提出大数据错误自动检测和修复问题的可计算性理论、大数据错误自动检测和修复问题的计算复杂性理论、大数据错误自动检测和修复方法的可信性理论、高效实用的大数据错误自动检测与修复算法.4)弱可用数据上近似计算的理论和技术当数据中的错误不能彻底修复时,这些数据称为弱可用数据.直接在弱可用数据上进行满足给定精度需求的近似计算,不失为一个有意义的选择.遗憾的是现有的理论与算法无法支持弱可用数据上的近似计算.因此,我们需要解决如下挑战性问题:提出弱可用大数据近似计算的可行性理论、弱可用大数据近似计算问题的计算复杂性理论、弱可用大数据上近似计算结果的质量评估理论、弱可用大数据上的近似计算方法.5)弱可用数据上的知识发掘与演化的机理大数据的可用性问题必然导致源于数据的知识的可用性问题.当数据完全可用时,从正确的大数据中发掘知识以及从数据演化探索知识演化机理的研究已经很困难.当数据弱可用时,弱可用大数据上的知识发掘与演化机理的研究将更加困难.我们需要解决如下挑战性问题:提出源于弱可用数据的知识可用性评估理论与方法、数据可用性与知识可用性的相关性理论、弱可用大数据上知识发现的计算复杂性理论和算法设计与分析新方法、源于弱可用数据的知识校验与纠偏的理论和方法、源于弱可用数据的知识演变机理.综上所述,大数据可用性在基础理论、算法和工程技术各层面都提出了严峻的挑战性研究问题.目前大数据可用性研究工作还刚刚开始,仅触及少数几个侧面,大量科学技术问题有待解决,向我们提出了新的挑战,也为我们提供了新的机遇.2国内外研究进展动态国内外已经开展了一些数据可用性的研究工作,但是大数据可用性研究还刚刚起步.下面,我们分别从高质量大数据获取与整合、大数据可用性理论体系、数据错误自动检测与修复、弱可用数据的近似计算、弱可用数据的知识挖掘等方面,介绍国内外研究进展情况和发展趋势.2.1高质量数据获取与整合大数据主要有3个来源:1)分布在Web上的丰富数据库资源;2)物理信息系统,如智能电网、智慧城市等;3)科学实验与观测数据(简称科学数据),如高能物理实验数据、生物数据、空间观测数据等.通常,物理信息系统数据和科学数据一般都通过由传感器或观测设备构成的传感网来获取.大数据获取和整合是指从Web数据源或传感网获取数据并将其加工整合为存储在计算系统中的数据集合.高质量大数据获取与整合是指最大化数据可用性的大数据获取与整合过程.下面我们从Web数据的获取与整合、传感网数据的获取与整合两个方面,介绍高质量数据获取与整合的研究进展.2.1.1判定数据源之间的复制关系Web上存在丰富的数据源.人们经常需要从多个Web数据源获取数据,并将其整合为自己需要的数据集合,这个过程通常被称为Web数据集成.在Web数据集成中,数据源的质量会极大地影响集成数据的可用性.如何判定和选择高质量数据源,使其成为数据获取的源泉,是获得高质量集成数据的关键问题.文献发现数据源之间的数据复制关系能够帮助系统更好地选取高质量的数据源、改善集成数据的可用性.针对静态数据,文献提出了基于贝叶斯分析的方法,判定数据源之间的复制关系,并基于复制关系提出了高质量数据获取与整合的方法,提高了获取与整合后的数据的可用性.文献针对动态数据,提出利用数据源中数据更新历史来判定数据源之间的复制关系的方法,利用隐马尔可夫模型来判定数据源的复制关系,并利用贝叶斯模型改善数据获取的过程,提高了结果数据的可用性.文献进一步考虑更复杂的数据复制关系,包括部分数据复制、多个数据源同步复制、多数据源传递复制,给出了判定复制关系、提高集成数据可用性的算法.文献给出了一个判定数据复制关系的原型演示系统.文献对上述工作进行了系统性综述.2.1.2网内数据获取算法文献[15-16]针对无线传感网能量受限的特点,探索了在保障数据精确性的前提下以最小能量开销获取感知数据的问题,提出了从无线传感网获取数据的(ε,δ)-近似随机算法,确保获取数据的精度大于ε的概率小于δ.文献研究了如何从传感网获取数据,使得物理世界能够被准确近似,从而获取高精度数据,提高数据的可用性.该文献使用Hermit插值及三次样条插值技术,提出了两个面向物理过程的高精度变频数据采集算法,算法能够在保证数据可用性的前提下最小化传输到网络中的数据量,实现对物理世界的ε-近似逼近,使得获取的数据所描述的物理世界与真实物理世界的误差小于ε,其中ε可以是任意小的正数.文献针对地理位置相近传感器节点的数据中存在冗余的问题,提出了位置信息敏感的数据获取方法,利用数据源之间的地理关联特征,过滤冗余数据,提高获取的数据在事件监测应用中的可用性,减低了误判的概率,并给出了能源有效的网内数据获取算法.2.1.3全面系统的研究高质量大数据获取与整合研究工作刚刚起步,研究结果还不多见,缺乏全面系统的研究,很多问题还没有解决,大量的新问题有待发现,这方面的研究任重道远.2.2大数据的可用性理论体系本节从一致性、完整性、精确性、时效性、实体同一性以及这5个可用性维度交互作用等6个方面综述大数据可用性理论体系的研究进展.2.2.1扩展的条件函数依赖语义规则有关数据一致性理论体系的研究结果可以分为两类:基于语义规则的数据一致性理论体系、基于统计学的数据一致性描述方法.1)基于语义规则的数据一致性理论体系在经典的关系数据系统中,函数依赖和包含依赖可以用来描述数据的一致性,给出了一种数据一致性的理论体系.但是,这种理论体系的能力极其受限,很多数据一致性约束无法表达,很多数据一致性错误不能被发现.针对函数依赖和包含依赖的局限性,文献[19-20]对其进行了扩展,提出条件函数依赖和条件包含依赖的语义规则,用来描述复杂数据一致性约束,发现和修复复杂的数据一致性错误.文献[20-22]进一步研究了条件函数依赖的推理问题、可满足问题、覆盖问题、检测问题、传递问题的计算复杂度及其求解算法.文献研究了条件包含依赖的推理问题和可满足问题的计算复杂度及其求解算法.文献给出了条件函数依赖和条件包含依赖的详细综述.文献针对条件函数依赖无法描述“并”语义的问题,提出了扩展的条件函数依赖,并证明了扩展的条件函数依赖的推理和可满足等问题与条件函数依赖的对应问题具有相同的计算复杂度.文献在有时间戳的数据上提出了序列依赖语义规则,用来描述随时间变化数据的一致性约束,试图解决随时间变化数据的一致性错误的发现和修复问题.文献针对异构数据源中由数据格式不一致引发的一致性错误,利用描述属性值相似性测度扩充了函数依赖,用来描述异构数据的一致性约束,发现和修复异构数据的一致性错误.文献研究了如何从数据中有效地发现条件函数依赖规则的问题,提出了一种具有剪枝能力搜索算法,有效地发现条件函数依赖.针对同样的问题,文献提出了另外4种算法,更有效地解决了条件函数依赖发现问题.2)基于统计学的数据一致性描述方法文献利用统计模型来描述数据的一致性,并通过求解和比较模型参数的方法来发现和修复数据不一致性错误.文献提出了基于统计知识的数据不一致性描述方法,并给出了基于超团的数据一致性提升算法.2.2.2研究问题的计算复杂性传统的完整性研究可以追溯到20世纪80年代开始的对数据库中“null”语义的扩展讨论.早期研究大多关注于如何在数据库中表述缺失数据.最经典的工作当属基于条件表(conditionaltable)的不完整数据表述系统.条件表是传统关系表的扩展,允许属性值中出现变量和逻辑表达式.变量表示缺失值.逻辑表达式表示缺失值之间的逻辑关系.条件表既可以表示不完整数据,也支持不完整数据上的查询处理.为表述缺失信息,文献提出了另一种关系数据库的扩展模型,给出了封闭世界假设和开放世界假设的概念,并在这两种假设下研究了如下判定问题的计算复杂性:一个不完整数据库能否转换为满足一致性约束的完整数据库.文献提出了“opennull”的概念,提出了在封闭式假设下数据库中缺失属性值的表示方法.传统的数据完整性研究工作一般都建立在封闭世界假设开放世界假设的基础上.封闭世界假设表示数据库包含了所有表述现实世界实体的元组,这些元组的某些属性值可能遗缺.开放世界假设表示数据库中不仅属性值可能遗失,表示现实世界实体的元组也可能完全遗缺.然而,表示现实世界的数据库经常既不是完全封闭的,也不是完全开放的.基于这个考虑,文献针对元组遗失问题,提出了相对完整性理论来表述数据库相对于给定的主数据和查询的完整性,研究了如下问题的计算复杂性:1)给定主数据和查询,判定一个数据库是否是完全的;2)给定主数据和查询,判定是否存在一个数据库相对给定的主数据和查询是完整的.文献扩展了文献的研究结果,使之也适用于元组的属性遗失问题.文献[37-38]将传统的完整性理论扩展到XML数据上,研究了如何表示不完整XML数据的问题.2.2.3不确定性的描述方法与评估算法数据精确性方面的研究工作目前还非常少见,只有文献把不确定性视为精确度低的现象,提出了一种基于可能世界语义的数据精确性描述方法,并给出了对应的精确性评估算法.2.2.4实体时效研究数据时效性和时态数据库的研究是不同的.时态数据库主要研究如何查询带有时间戳的信息和如何描述时间约束.在实际应用领域,时间戳信息经常未知或不完全.于是,数据时效性研究的目的是在时间戳信息不存在或不完全的条件下,建立数据时效的理论体系,解决数据时效性的判定问题、数据时效性错误的自动发现和修复问题.文献提出了一个数据时效性模型,用基于规则的方法描述同一实体对应的不同元组的属性值的时序关系,提出基于实体的最新值的查询语义,并给出了应用时序关系和拷贝关系推导实体最新信息的推理机制.基于这个模型和时效性查询语义,文献给出了回答用户查询的计算复杂性,并研究了在实体最新值缺失的情况下如何扩展拷贝关系以找到实体的最新值.2.2.5基于规则的实体同一性描述实体同一性是数据可用性方面研究最多的一个维度.最早的工作来自于文献.文献从统计学角度,形式化地定义了实体同一性错误检测的问题.文献[47-48]在数据库领域较早地提出了识别实体同一性错误的问题.文献[49-51]等给出了实体同一性研究的综述.以下,我们依据描述实体同一性的不同方法来介绍实体同一性的研究进展.1)基于语义规则的实体同一性描述方法这类方法的大致思想是利用经验知识来给出解决实体同一性问题的准则.文献提出了一个简单的方法,即通过比较表示实体的不同关系元组的主键来确定这些元组是否指代同一实体.当元组主键缺失时,利用函数依赖补齐元组中缺失的主键值.文献[47-48]提出了基于等值理论的规则来推导元组中属性值之间的等价关系,用一组关系属性来描述实体同一性,通过比较多个关系元组中某些属性的值是否同时等价来判定这些元组是否指代同一实体.文献[53-54]给出了一个基于字符串转换规则的框架,利用字符串之间的转换关系描述属性值之间的等价关系,进而描述实体同一性.文献研究了如何从例子中学习字符串转换规则,从而得到描述实体同一性的规则.文献在此框架下,进一步考虑元组之间的关系,提出了一个基于逻辑编程的方法来描述实体同一性.文献提出用否定规则描述实体同一性,并针对否定规则对实体同一性的影响进行了研究.文献提出了用聚集约束来描述实体同一性的方法.文献首次形式化地提出了实体同一性描述规则,系统地研究了给出的规则的推理问题,使得用来描述实体同一性的规则不再是松散的集合,而是可以相互配合相互推理,提高了此类方法描述实体同一性的能力.文献进一步在动态语义下研究实体同一性规则的相互作用及推理问题.文献结合期望最大化(EM)算法和无监督学习方法来研究获取实体同一性描述规则的方法.文献介绍了一个基于规则的系统,解决了半结构化数据上的实体同一性的判定问题.文献定义了图数据的实体同一性问题,并基于合并节点、增删边、标记节点等操作,提出了描述实体同一性的方法.文献[64-67]在数据上提出了一系列新的图模式的定义、标准和匹配算法,新的图模式描述方法可以用来描述图结构数据上的实体同一性.2)基于相似性测度的实体同一性描述方法设E是实体集合,E中两个实体的相似性测度是一个函数S:E×E→.对于y∈E,S(x,y)越大,x和y就越可能是相同实体.一般来说,相似性函数的输出值高于某个阈值时,则判定两个实体相同.文献[68-69]是较早地提出利用字符串属性值上定义的距离测度来描述实体同一性的工作.文献利用信息检索领域中的tf.idf相似性度量方法扩展了基于字符串的相似性测度,提出了描述实体同一性的另一种方法.为了更有效地计算实体间的相似性,文献研究了实体间相似性判定的问题,基于如下思想:如果A和B都经常与其他同一组元素一起出现,则A与B的相似性较高,提出一种新的描述实体同一性的相似性测度的定义.文献利用聚簇的思想,提出了一种新的描述实体同一性的方法.文献基于合并“rankedlist”方法,提出了一种综合考虑多个属性的相似性测度的实体同一性度量方法.文献基于机器学习方法,提出了结合多个属性相似性测度描述实体同一性的方法.文献利用基于马尔科夫链的方法,提出描述实体同一性的相似性测度.文献[76-77]基于滑动窗口和“gram”概念,描述XML节点之间的相似性.我们可以用这样的相似性测度来描述XML数据上的实体同一性.文献研究了从文本数据中抽取实体的问题,利用编辑距离来描述实体同一性.文献考虑RFID数据中的实体同一性问题,提出了描述RFID数据实体同一性的RPCV方法.2.2.6下一步研究目前的研究把数据的一致性、精确性、完整性、时效性、实体同一性分离,把每个特性视为一个独立领域,进行孤立的研究.然而,这些特性交互影响,任何可用性管理系统必须具有同时确保数据一致性、精确性、完整性、时效性、实体同一性的能力.我们需要提出一个统一的逻辑框架来解决这个问题.但目前还未有深入的研究结果,文献从管理学角度对各个特性出现的实例作了基本的介绍,但没有开展深入的研究,文献探讨了数据修复和元组匹配的交互影响,基于条件函数约束和匹配约束,提出了一个同时支持数据修复和实体识别的信息清洗框架.在这方面有很多重要的研究问题还未被考虑,有大量的挑战性问题有待解决.2.2.7应用价值研究数据一致性方面的研究工作主要关注集中方式存储的关系数据,分布式存储的关系数据和非关系数据的一致性理论工作还很少,适用于大数据的数据一致性相关技术还需要进一步探索.数据完整性方面的研究工作很少.针对传统的完整性假设有了一些模型和相关问题的理论结果,但是这些结果对于很多实际应用无意义.为此,人们开始研究具有普遍实际应用价值的完整性理论和方法,但是目前只有相对完整性方面的初步结果.我们还需要建立更一般形式的完整性理论,开展更深入的研究.数据精确性方面的研究工作基本上是空白,亟需深入研究.数据时效性方面的研究工作非常少,只有针对特殊应用的少量研究结果,亟需深入系统地研究.实体同一性方面的研究工作主要针对关系数据.关系数据上实体同一性研究已基本趋向成熟,但是复杂结构数据、半结构化数据、非结构化数据等非关系数据上的实体同一性方面的研究还很少见,尚需深入研究.总之,目前大数据的可用性方面的研究工作尚处于起步阶段.目前的工作主要针对一致性和实体同一性开展了较为深入的研究,各个特性之间彼此的关系还没有较为深入地探讨.非关系数据以及分布式存储数据的可用性研究工作还很少.2.3数据错误自动修复研究进展数据错误的自动检测研究主要集中在一致性错误和实体同一性错误两个方面.数据错误自动修复研究则主要集中在一致性错误、完整性错误和实体同一性错误3个方面.下面,我们分5个方面来综述数据错误自动检测与修复的研究进展.2.3.1自动检测算法基于函数依赖和条件函数依赖,文献[82-83]针对集中存储的关系数据库,使用SQL语言设计了自动检测算法,用于查找违反条件函数约束和条件包含约束的元组.文献研究了在分布式环境下检测数据一致性错误的问题,目标是最小化数据通信量.文献给出了一种增量式的分布式数据库中数据一致性错误的检测方法.2.3.2基于数据分块处理的实体识别效率实体同一性错误是指在数据库中存在描述同一个现实世界实体的n个(n>1)数据元组.于是,实体同一性错误检测的关键是识别数据库中相似实体,简称实体识别.实体识别方面的研究工作很多,趋于成熟.以下,我们分4个方面介绍实体识别的研究进展.1)以最大化识别精度为目标的实体识别方法最大化实体识别精度是实体识别研究的主要目标之一,围绕这个目标人们开展了大量研究.文献利用字符串等价关系词典的精确信息,计算实体之间的相似性,提高了实体识别的精度.文献提出了描述实体之间关系的统计模型,提高了实体识别的精度,并给出了高精度的实体识别算法.在基于统计学的实体识别方法中,参数设置错误和训练数据缺失会导致检测结果的不准确.针对这类问题,文献提出了一种两阶段的统计学方法,完成实体识别,提高了实体识别的精度.文献[89-90]提出了利用机器学习方法提高实体同一性检测精度的方法.文献提出了CollectiveEntityMatching的模型.该模型不仅利用元组之间的相似信息和元组同现的频度信息,还充分考虑了元组检测结果之间的影响,利用检测的中间结果进行综合推理,提高了实体识别的精度.2)以最大化识别效率为目标的实体识别方法降低实体识别算法的时间复杂性是实体识别研究的另一个主要目标.虽然人们在这方面作出了巨大努力,但是现有的实体识别算法的最坏情况的时间复杂度皆为Ω(n2).为了改进实体识别的效率,文献较早地提出了数据分块处理的思想.在文献的方法中,首先,元组被按照不同的属性值单独排序,然后,利用固定长度的窗口顺序扫描每一个元组序列,并在窗口内部对实体进行匹配操作,最后将多个属性上的匹配结果合并得到最后的实体识别结果.假设窗口大小为L,元组数目为n,该方法能够将实体识别的代价从O(n2)降至O(L×n),在实际应用中会大大提高实体识别的效率.然而,在保证实体识别精度的情况下,L的最坏情况是n,因此算法的最坏时间代价仍然是O(n2).聚簇是实体识别的常用方法,然而聚簇算法的代价通常都比较高,并且随输入大小的增加,聚簇算法的代价增长非常快.文献利用数据分块处理的思想,将元组分块按照某些属性值的不同分为独立的块,然后在每个块内单独运行聚簇算法,最后把块上的聚簇结果合并得到实体识别的结果.文献中的方法降低了每次调用的聚簇算法的时间代价,整体上提高了基于聚簇方法的实体识别算法的效率.文献针对数据规模比较大的情况,提出了基于Hash函数将数据分块的方法,并给出了对应的实体识别算法,改进了实体识别过程的效率.文献对两种实际中经常用到的数据分块方法进行了形式化地描述并进行了分析对比.其中,一种是利用简单的策略(例如随即选取的Hash函数)将数据划分,另一种是利用某些语义信息(例如基于属性值的描述性规则)将数据划分块.在对比中,从实体识别的时间效率角度来看,第2种方法具有明显的优势.然而,实际应用中要找到具有适合语义信息的规则是非常困难的,有时甚至是不存在的.文献提出了一种基于机器学习的数据分块策略来改进实体识别的效率.通常,实际中采用的数据分块方法并不能保证块间数据的独立性.在这种情况下,分块方法在提高实体识别效率的同时,也降低了实体识别的精度.为了解决这个问题,文献基于增量计算的思想,提出了迭代地实体识别方法.在每次迭代中,首先把上一次迭代计算得到的每个分块的实体识别结果传输到其他块内,然后每个分块根据收到的更新结果增量式地计算各自块内的实体识别结果,这样的迭代计算一直进行直到结果不在改变或迭代次数达到给定阈值.该方法在保证实体识别效率的前提下改进了实体识别的结果精度.文献比较全面地综述了实体识别方法中的各种数据分块策略.文献针对大数据的情况,基于数据分块计算的思想,利用云计算的环境来加速大规模数据上的实体识别效率.文献针对实际应用中用户所需数据仅占全部数据很小比例的情况,解决了在返回查询结果的同时给出实体识别结果的问题.该方法利用“边查询边识别实体”的思想,仅在与查询结果涉及的实体相关的元组上运行识别算法,在较小地降低查询执行效率的前提下提高了实体识别方法的效率.文献针对实体识别结果相互影响的问题,基于实体识别规则的动态语义,考虑识别规则之间的关系,提出了一种增量式的实体识别方法,提高了识别效率.大多数应用都假设属性值是字符串,因此,提高基于字符串的相似性匹配的效率是提高实体识别效率的重要方法.文献较早地提出了基于字符串相似性的实体识别中的优化问题,并给出了初步的优化算法.文献对关系数据上基于字符串相似性匹配的实体识别问题作进一步的抽象,提出了“相似连接”和“相似查询”操作,并将其作为数据库的一个基本操作来研究.文献提出了利用倒排索引加速相似查询的方法,并且针对索引占用空间大的问题,给出了缩减索引空间代价的方法,提高了实体识别的效率.文献针对相似连接问题,将字符串的相似性计算转化为集合的相似连接问题,并提出了集合的相似连接操作的算法,给出了基于字符串前缀、后缀的过滤方法,提高了基于相似连接的实体识别方法的效率.文献针对变长字符串,提出了基于变长字符串搜索的方法解决长字符的相似查询问题,提高了属性值为长字符串情况下的实体识别问题.文献[106-108]研究了基于n-gram的近似字符串匹配问题,其基本思想是在字符串上建立n-gram索引,将字符串之间的距离转化为对应n-gram交集的数量,然后基于n-gram的集合语义给出高效的相似连接算法,从而改进了实体识别的效率.文献研究了高维数据上实体识别问题,利用近似地计算高维数据相似性的思想,提出了LSS算法,并利用GPU的特性给出了对应的高效实现方法.文献[110-111]针对半结构化数据的实体识别问题,基于同时匹配属性值和结构信息的思想,提出了一个基于树结构匹配的高效的实体识别算法.3)实体识别系统的实现方法现有的研究工作已经提出了很多实体识别方法,差别很大,要想在一个系统里同时运用这些方法很难.文献针对这个问题,提出了一个解决实体识别问题的通用系统框架,支持插入不同的构建来定制实体识别方法,可以灵活地实现多个实体识别方法的整合.大多数已有的实体识别研究都是针对实体识别操作内部来进行优化,文献对实体识别问题进行了形式化的描述,把“比较”和“合并”等操作抽象出来作为黑盒处理,给出了优化方法提高整个实体识别过程的效率.文献把实体识别涉及的操作看作黑盒,把实体识别过程抽象为代数操作序列,解决了在操作执行顺序上的优化问题.该工作提出了一种基于用户示例驱动的方法,根据用户输入的实体识别过程示例,自动地生成与用户示例语义一致的最优实体识别操作序列,提高了整个实体识别系统的效率.不同的实体识别方法是往往针对不同的应用,文献提出通过集成多个实体识别方法来提高实体识别精度的思想,提出了基于语义信息的多实体识别方法集成的机制,提高了整个实体识别方法的精度.4)实体识别方法的测评虽然实体识别的方法有很多,但很难对其进行综合、公平的比较.原因是没有公认的评测集,没有公认的比较测度.这方面仅有一些初步的工作.文献对比了各种基于字符串匹配的实体识别的相似性度量.文献[117-118]提出了建立实体识别评测集的问题,并给出了实现评测集的指导思想,但并没有给出具体的实现.文献[119-120]在真实数据上对比了各种实体识别方法的效率.文献较少了比较11种不同实体识别方法的逻辑框架.文献在实体识别结果和正确结果都给定的情况下,针对评价实体识别结果优劣的问题,提出了一个基于“合并”和“分裂”操作的实体识别结果评价测度,并给出了理论性分析.2.3.3数据一致性错误修复算法设计下面我们从两个方面综述目前已经提出的数据一致性错误自动修复的方法.1)基于语义规则的方法文献针对传统的函数依赖所发现的数据不一致错误,给出了基于删除元组的修复数据不一致错误的方法.文献针对传统的函数依赖和包含依赖规所发现的数据不一致错误,提出了通过修改元组属性值来修复数据不一致错误的方法.该文给出了修复操作的代价模型,并给出了在这个模型下代价优化的数据一致性错误修复算法.文献针对由条件函数依赖所发现的数据一致性错误,证明了数据一致性错误的修复问题以及数据一致性错误增量式修复问题都是NP完全问题,并设计了启发式近似算法自动修复数据的不一致错误.在某些情况下,用户能够给出一些修复后数据的正确性描述(基于用户定义的强制性约束).如果一个可能修复不满足这个描述,它就是不合理的.文献针对这个问题,定义了一个由所有合理修复构成的空间,并且给出了修复算法.文献针对两个元组的修复不独立的情况,给出了修复数据不一致错误的算法.2)基于统计学的方法文献提出了一种基于概率的数据一致性错误修复方法.该方法首先假定存在一个满足一致性约束的合理修复的空间,然后依据合理修复的概率分布进行抽样,最后使用抽取出来的合理修复完成数据的修复.文献[128-130]分别以RFID和传感器网络为背景,针对利用统计学定义的数据一致性错误,提出了修复数据一致性错误的方法.2.3.4基于聚簇和传统聚簇方法的实体同一性错误修复方法修复数据的实体同一性错误就是要把描述同一个现实世界实体的多个元组合并为一个单独的元组,从而为用户提供实体同一的信息.文献利用数据融合技术,解决了实体同一性错误的修复问题.数据的一次性修复会引起不可逆转的错误(即失去的数据无法恢复).文献针对这个问题,提出利用一系列修复取代一次性修复的思想,给出了利用参数控制的实体同一性错误修复方法,通过一系列不同参数的修复,获得不同修复结果,最后把这些结果综合为最终的修复结果,避免了修复引起的错误.文献提出了基于概率方法对查询结果中的实体同一性错误进行修复的方法,该方法通过改写查询,将概率信息的计算加入到查询执行中,使得查询结果中的实体一致性错误得到修复.文献介绍了一个实体同一性错误修复系统.文献[135-136]提出了一种基于传统的聚簇方法的实体同一性错误修复方法,并给出了基于统计信息的算法优劣衡量标准.在基于聚簇方法修复实体同一性错误的过程中,簇之间的阈值设置是一个关键问题,文献考虑到不同元组应设置不同阈值,提出了一种基于变化阈值的聚簇方法来提高实体同一性错误修复的精度.大多数实体同一性错误修复的研究工作都假设实体的每个属性只有一个值.文献研究了作这个假设不成立时的实体同一性错误修复问题,把实体同一性错误的修复问题抽象成一个K部图上的聚簇问题,并提出了基于爬山和贪心的两种启发式实体同一性错误修复方法.2.3.5基于概率模型的缺失数据值估计方法数据完整性的修复工作比较少,只有文献针对两种特殊类型的应用(年龄推断和