软件学报ISSN1000-9825, CODEN RUXUEW Journal of so/nare,201627(7):1605-1625|doi:10.13328/ cnki. jos.005038] ◎中国科学院软件研究所版权所有 +86-10-62562563 大数据可用性的研究进展 李建中,王宏志,高宏 (哈尔滨工业大学计算机科学与技术学院黑龙江哈尔滨150001) 通讯作者:李建中,E-mai:lijzh@hit.edu.cn 摘要:信息技术的迅速发展,催生了大数据时代的到来大数据已经成为信息社会的重要财富,为人们更深入地 感知、认识和控制物理世界提供了前所未有的丰富信息然而随着数据规模的扩大,劣质数据也随之而来,导致大数 据质量低劣,极大地降低了大数据的可用性,严重困扰着信息社会近年来,数据可用性问题引起了学术界和工业界 的共同关注,展开了深入的研究,取得了一系列研究成果介绍了数据可用性的基本概念,讨论数据可用性的挑战与 研究问题综述了数据可用性方面的研究成果,探索了大数据可用性的未来研究方向 关键词:大数据;数据可用性;数据质量;数据清洗;数据管理 中图法分类号:TP311 中文引用格式:李建中,王宏志高宏大数据可用性的研究进展软件学报2016,27(7):1605-1625.htp/www.jos.org.cn/1000 9825/5038hm 英文引用格式:LiJz, Wang HZ,GaoH. State-of-the-Art of research on big data usability. Ruan jian Xue Bao/Journal of Software2016,27(7):1605-1625(inChinese).http://www.jos.orgcn/1000-9825/5038.htm State-of-the-Art of Research on Big Data Usability LI Jian-Zhong, WANG Hong-Zhi, GAO Hong ( School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China) Abstract: The rapid development of information technology gives rise to the big data era. Big data has become an important wealth of formation society, and has provided unprece world. However, withthe growth in data scale, dirty datacomes along. Dirty data leads to the low qualityand usability of big data, and seriously harms the information society. In recent years, the data usability problems have drawn the attentions of both the academia and dustry. In-Depth studies have been conducted, and a series of research results have been obtained. This paper introduces the concept of data usability, discusses the challenges and research issues, reviews the research results and explories future research directions in this Key words: big data, data usability; data quality; data cleaning; data management 信息技术的迅速发展特别是数据获取技术的突飞猛进催生了大数据时代的到来包括我国在内的世界很 多国家都在很多领域积累了PB(1015字节)级以上规模的大数据这些大数据对于国民经济发展、社会进步、社 会安全和稳定、科学研究模式变革等人类社会的各个方面都具有重大价值,为人类更深入地感知、认识和控制 物理世界提供了前所未有的丰富信息大数据已经开始造福于人类,成为信息社会的重要财富,引起了学术界 工业界和各国政府的高度重视研究工作风起云涌 基金项目:国家重点基础研究发展计划(973)(2012CB316200,国家自然科学基金(U1509216,61472099) Foundation item: National Basic Research Program of China(973)(2012CB3 16200 ); National Natural Science Foundation of China 收稿时间:2016-05-12;采用时间:2016-05-17;jos在线出版时间:201605-19 CNKI网络优先出版:2016-05-1816:45:38,htp/ww. cnki. net/kcms/deta12560.TP.20160518.1645.001html ◎中国科学院软件研究所htp:/w.jos.org.cn
软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn Journal of Software,2016,27(7):1605−1625 [doi: 10.13328/j.cnki.jos.005038] http://www.jos.org.cn ©中国科学院软件研究所版权所有. Tel: +86-10-62562563 大数据可用性的研究进展∗ 李建中, 王宏志, 高 宏 (哈尔滨工业大学 计算机科学与技术学院,黑龙江 哈尔滨 150001) 通讯作者: 李建中, E-mail: lijzh@hit.edu.cn 摘 要: 信息技术的迅速发展,催生了大数据时代的到来.大数据已经成为信息社会的重要财富,为人们更深入地 感知、认识和控制物理世界提供了前所未有的丰富信息.然而随着数据规模的扩大,劣质数据也随之而来,导致大数 据质量低劣,极大地降低了大数据的可用性,严重困扰着信息社会.近年来,数据可用性问题引起了学术界和工业界 的共同关注,展开了深入的研究,取得了一系列研究成果.介绍了数据可用性的基本概念,讨论数据可用性的挑战与 研究问题,综述了数据可用性方面的研究成果,探索了大数据可用性的未来研究方向. 关键词: 大数据;数据可用性;数据质量;数据清洗;数据管理 中图法分类号: TP311 中文引用格式: 李建中,王宏志,高宏.大数据可用性的研究进展.软件学报,2016,27(7):1605−1625. http://www.jos.org.cn/1000- 9825/5038.htm 英文引用格式: Li JZ, Wang HZ, Gao H. State-of-the-Art of research on big data usability. Ruan Jian Xue Bao/Journal of Software, 2016, 27(7):1605−1625 (in Chinese). http://www.jos.org.cn/1000-9825/5038.htm State-of-the-Art of Research on Big Data Usability LI Jian-Zhong, WANG Hong-Zhi, GAO Hong (School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China) Abstract: The rapid development of information technology gives rise to the big data era. Big data has become an important wealth of information society, and has provided unprecedented rich information for people to further perceive, understand and control the physical world. However, withthe growth in data scale, dirty datacomes along. Dirty data leads to the low qualityand usability of big data, and seriously harms the information society. In recent years, the data usability problems have drawn the attentions of both the academia and industry. In-Depth studies have been conducted, and a series of research results have been obtained. This paper introduces the concept of data usability, discusses the challenges and research issues, reviews the research results and explories future research directions in this area. Key words: big data; data usability; data quality; data cleaning; data management 信息技术的迅速发展,特别是数据获取技术的突飞猛进,催生了大数据时代的到来,包括我国在内的世界很 多国家都在很多领域积累了 PB(1015 字节)级以上规模的大数据.这些大数据对于国民经济发展、社会进步、社 会安全和稳定、科学研究模式变革等人类社会的各个方面都具有重大价值,为人类更深入地感知、认识和控制 物理世界提供了前所未有的丰富信息.大数据已经开始造福于人类,成为信息社会的重要财富,引起了学术界、 工业界和各国政府的高度重视,研究工作风起云涌. ∗ 基金项目: 国家重点基础研究发展计划(973)(2012CB316200); 国家自然科学基金(U1509216, 61472099) Foundation item: National Basic Research Program of China (973) (2012CB316200); National Natural Science Foundation of China (U1509216, 61472099) 收稿时间: 2016-05-12; 采用时间: 2016-05-17; jos 在线出版时间: 2016-05-19 CNKI 网络优先出版：2016-05-18 16:45:38, http://www.cnki.net/kcms/detail/11.2560.TP.20160518.1645.001.html
Journal of so/ fare软件学报Vol27,No.7,Juy2016 然而,随着大数据的爆炸性增长,劣质数据也随之而来,导致数据质量低劣,极大地降低了数据的可用性国 外权威机构的统计表明美国的企业信息系统中,1%30%的数据存在各种错误和误差,美国的医疗信息系统 中,13.6%-81%的关键数据不完整或陈旧国际著名的科技咨询机构 Gartner的调查结果显示全球财富1000 强企业中,超过25%的企业信息系统中存在数据错误时 数据可用性问题及其所导致的知识和决策错误已经在全球范围内造成了恶劣的后果严重困扰着信息社 会例如在医疗方面美国由于数据错误引发的医疗事故每年导致的患者死亡人数高达98000名以上向在工业 方面错误和陈旧的数据每年给美国的工业企业造成约6110亿美元的损失在商业方面美国的零售业中每 年仅错误标价这一种数据可用性问题的诱因,就导致了25亿美元的损失在金融方面仅在2006年在美国的 银行业中,由于数据不一致而导致的信用卡欺诈失察就造成48亿美元的损失,在数据仓库开发过程中,30% 80%的开发时间和开发预算花费在清理数据错误方面,数据可用性问题给每个企业增加的平均成本是产值的 0%-20%明因而大数据的广泛应用对数据可用性的保障提出了迫切需求 数据可用性问题是信息化社会的固有问题不仅西方发达国家存在我国也存在例如我们通过对我国某 个大型医药企业信息中心的大规模数据进行抽 6以上的数据存在错误 综上所述确保数据可用性是关系到信息社会存亡的重大任务,是有效发掘和利用大数据价值的前提深入 开展数据可用性研究,具有重要的战略意义最近几年,数据可用性的研究引起了全球的关注中国国家重大基 础研究发展计划(973计划012年启动了为期5年的“海量数据可用性基础理论与关键技术研究”项目.目前,大 数据可用性的研究蓬勃开展,成为大数据研究的一个重要方面,取得了很多研究成果本文旨在介绍大数据可用 性的基本概念分析大数据可用性的研究问题介绍大数据可用性的研究进展探索未来的研究方向 1大数据可用性概念、挑战与研究问题 11数据可用性的基本概念 数据可用性具有很多度量指标文献[0列出了20个数据可用性指标,文献[1]归纳了40个数据可用性指 标我们针对大数据的实际应用,对大数据的可用性度量指标进行了全面而系统的分析抽象出如下5个实际可 亍的度量指标12 数据一致性 数据集合中每个信息都不包含语义错误或相互矛盾的数据例如,数据(公司=“先导”,国码=“86”,区号= “10”,城市=“上海”)含有一致性错误,因为10是北京区号而非上海区号 数据精确性 数据集合中每个数据都能准确表述现实世界中的实体例如某城市人口数量为4130465,而数据库中记 载为400万宏观来看,该信息是合理的,但不精确 ·数据完整性 数据集合中包含足够的数据来回答各种查询,并支持各种计算例如某医疗数据库中的数据一致且精确 但遗失某些患者的既往病史,从而存在不完整性,可能导致不正确的诊断甚至严重医疗事故 数据时效性 信息集合中,每个信息都与时俱进不过时例如,某数据库中的用户地址在2010年是正确的但在2011年未 必正确,即数据过时 ·实体同一性 同一实体的标识在所有数据集合中必须相同而且数据必须一致例如企业的市场、销售和服务部门可能 维护各自的数据库,如果这些数据库中的同一个实体没有相同的标识或数据不一致将存在大量具有差异的重 复数据,导致实体表达混乱 设集合D的数据一致性、精确性、完整性、时效性和实体同一性分别为Q1,Q2Q3Q4和Q3,则数据可用性 可以定义为 中国科学院软件研究所htp:/ww.jos.org.cn
1606 Journal of Software 软件学报 Vol.27, No.7, July 2016 然而,随着大数据的爆炸性增长,劣质数据也随之而来,导致数据质量低劣,极大地降低了数据的可用性.国 外权威机构的统计表明:美国的企业信息系统中,1%~30%的数据存在各种错误和误差[1];美国的医疗信息系统 中,13.6%~81%的关键数据不完整或陈旧[2].国际著名的科技咨询机构 Gartner 的调查结果显示:全球财富 1 000 强企业中,超过 25%的企业信息系统中存在数据错误[3]. 数据可用性问题及其所导致的知识和决策错误已经在全球范围内造成了恶劣的后果,严重困扰着信息社 会.例如:在医疗方面,美国由于数据错误引发的医疗事故每年导致的患者死亡人数高达 98 000 名以上[4];在工业 方面,错误和陈旧的数据每年给美国的工业企业造成约 6 110 亿美元的损失[5];在商业方面,美国的零售业中,每 年仅错误标价这一种数据可用性问题的诱因,就导致了 25 亿美元的损失[6];在金融方面,仅在 2006 年,在美国的 银行业中,由于数据不一致而导致的信用卡欺诈失察就造成 48 亿美元的损失[7];在数据仓库开发过程中,30%~ 80%的开发时间和开发预算花费在清理数据错误方面[8];数据可用性问题给每个企业增加的平均成本是产值的 10%~20%[9].因而,大数据的广泛应用对数据可用性的保障提出了迫切需求. 数据可用性问题是信息化社会的固有问题,不仅西方发达国家存在,我国也存在.例如,我们通过对我国某 个大型医药企业信息中心的大规模数据进行抽样检验,发现 10%以上的数据存在错误. 综上所述,确保数据可用性是关系到信息社会存亡的重大任务,是有效发掘和利用大数据价值的前提.深入 开展数据可用性研究,具有重要的战略意义.最近几年,数据可用性的研究引起了全球的关注.中国国家重大基 础研究发展计划(973 计划)2012 年启动了为期 5 年的“海量数据可用性基础理论与关键技术研究”项目.目前,大 数据可用性的研究蓬勃开展,成为大数据研究的一个重要方面,取得了很多研究成果.本文旨在介绍大数据可用 性的基本概念,分析大数据可用性的研究问题,介绍大数据可用性的研究进展,探索未来的研究方向. 1 大数据可用性概念、挑战与研究问题 1.1 数据可用性的基本概念 数据可用性具有很多度量指标.文献[10]列出了 20 个数据可用性指标,文献[11]归纳了 40 个数据可用性指 标.我们针对大数据的实际应用,对大数据的可用性度量指标进行了全面而系统的分析,抽象出如下 5 个实际可 行的度量指标[12]. • 数据一致性 数据集合中,每个信息都不包含语义错误或相互矛盾的数据.例如,数据(公司=“先导”,国码=“86”,区号= “10”,城市=“上海”)含有一致性错误,因为 10 是北京区号而非上海区号. • 数据精确性 数据集合中,每个数据都能准确表述现实世界中的实体.例如,某城市人口数量为 4 130 465,而数据库中记 载为 400 万.宏观来看,该信息是合理的,但不精确. • 数据完整性 数据集合中包含足够的数据来回答各种查询,并支持各种计算.例如,某医疗数据库中的数据一致且精确, 但遗失某些患者的既往病史,从而存在不完整性,可能导致不正确的诊断甚至严重医疗事故. • 数据时效性 信息集合中,每个信息都与时俱进,不过时.例如,某数据库中的用户地址在 2010 年是正确的,但在 2011 年未 必正确,即数据过时. • 实体同一性 同一实体的标识在所有数据集合中必须相同而且数据必须一致.例如,企业的市场、销售和服务部门可能 维护各自的数据库,如果这些数据库中的同一个实体没有相同的标识或数据不一致,将存在大量具有差异的重 复数据,导致实体表达混乱. 设集合 D 的数据一致性、精确性、完整性、时效性和实体同一性分别为 Q1,Q2,Q3,Q4 和 Q5,则数据可用性 可以定义为
李建中等:大数据可用性的研究进展 1607 usability(D501+802+803+&04+8Os, 其中,δ,⑤,6,6和6是由用户根据实际需要确定的权值,且6+2+3+64+B=1 1.2大数据可用性的挑战和研究问题 大数据可用性向我们提出了如下3个挑战问题 (1)量质融合管理如何实现大数据的数量与质量的融合管理? 现有的大数据管理研究仅关注数据的规模、系统的处理能力和可扩展性,重在“量”的管理,忽视了数据 质℃(即质量)的管理我们面临的第一个挑战是确保大数据的质量,将大数据管理从“量”的管理拓展到“质”的管 理,最终实现“量”与“质”的融合管理为了彻底实现量质融合管理,我们必须研究量质融合管理问题提出完整的 理论体系解决关键技术问题 (2)劣质容忍原理:如何完成劣质数据上的精确或近似计算? 数据错误几乎无处不在已成为不争的事实“劣质容忍”是指在数据存在错误的情况下,如何完成精确或近 似计算为了实现劣质容忍,我们必须完成如下两个挑战性任务:第一,自动发现并修正大数据的错误将可校正 的劣质数据修复为完全正确的可用数据,支持正确的计算第二很多数据错误无法完全修复经过修复后,这些 数据成为部分正确的弱可用数据我们必须解决如何在弱可用大数据上完成高质量的近似计算 (3)深度演化机理:如何认知大数据演化的机理,追索数据错误根源? 数据不是一成不变的它会随着时间和物理世界的变化而发生演化现有的大数据研究忽略了按数据的演 化机理所进行的研究,使得数据错误的根源难以追索我们需要探索大数据的深度演化机理,即,以可用性为核 心的多源信息集合在时间、空间、形态、粒度等多个维度上正向协同的演化机理 为了应对上述挑战,我们需要以数据的一致性、精确性、完整性、时效性和实体同一性为核心,以保障信 息可用性为目标,研究以下7个问题,创建一套完整的确保海量信息可用性的理论、方法和技术 (1)大数据可用性的表达机理 首先探索数据的一致性、精确性、完整性、时效性、实体同一性的语义规则,建立大数据可用性语义表 达规则系统,判定规则系统可否公理化如果可公理化,则建立公理系统;然后,确定从大数据自动发现语义规则 问题的计算复杂性并设计求解算法;最后,确定大数据可用性自动推理问题的计算复杂性并设计求解算法 (2)大数据可用性的判定理论 首先,分别建立大数据的一致性、精确性、完整性、时效性、实体同一性的数学模型;然后,根据大数据研 究可用性这5项指标之间的相互影响,建立大数据可用性的综合数学模型最后,确定大数据可用性判定问题的 计算复杂性,设计求解算法 (3)大数据的演化原理 探索大数据的演化过程,建立大数据演化的世系模型及追踪技术,包括时空、多粒度、多路径和不确定的 大数据演化的理论,演化的可逆性判定与近似求解算法演化描述的复杂性理论和方法,以及网络化、多粒度 随机化的世系追踪和数据错误追踪技术 (4)大数据量质融合管理的理论和技术 首先,建立支持大数据量质融合管理的数据模型和相关理论,包括数据的逻辑结构、运算系统、数据的语 义约束模型;然后,解决数据质量管理模型和理论与传统数据管理模型和理论的融合问题,建立大数据量质融合 管理的模型和理论;最后,研究大数据量质融合管理关键问题的可计算性和计算复杂性,并设计求解算法 (5)高质量数据获取与整合的理论和技术 高质量数据的获取,是确保大数据可用性的重要环节大数据的来源多种多样类型千差万别,质量参差不 齐整合困难这些问题在当今突飞猛进的传感网和物联网背景下尤为严重我们需要解决如下具有挑战性的问 题:最优化逼近物理世界的高精度数据获取的理论和技术、最大化数据与问题求解相关性的高相关数据获取的 理论和技术、最小化无价值数据的高纯度数据获取的理论和技术 (6)数据错误自动检测与修复的理论和技术 中国科学院软件研究所htp:/ww.jos.org.cn
李建中 等:大数据可用性的研究进展 1607 usability(D)=δ1Q1+δ2Q2+δ3Q3+δ4Q4+δ5Q5, 其中,δ1,δ2,δ3,δ4 和δ5 是由用户根据实际需要确定的权值,且δ1+δ2+δ3+δ4+δ5=1. 1.2 大数据可用性的挑战和研究问题 大数据可用性向我们提出了如下 3 个挑战问题. (1) 量质融合管理:如何实现大数据的数量与质量的融合管理? 现有的大数据管理研究仅关注数据的规模、系统的处理能力和可扩展性,重在“量”的管理,忽视了数据 “质”(即质量)的管理.我们面临的第一个挑战是确保大数据的质量,将大数据管理从“量”的管理拓展到“质”的管 理,最终实现“量”与“质”的融合管理.为了彻底实现量质融合管理,我们必须研究量质融合管理问题,提出完整的 理论体系,解决关键技术问题. (2) 劣质容忍原理:如何完成劣质数据上的精确或近似计算? 数据错误几乎无处不在已成为不争的事实.“劣质容忍”是指在数据存在错误的情况下,如何完成精确或近 似计算.为了实现劣质容忍,我们必须完成如下两个挑战性任务:第一,自动发现并修正大数据的错误,将可校正 的劣质数据修复为完全正确的可用数据,支持正确的计算;第二,很多数据错误无法完全修复,经过修复后,这些 数据成为部分正确的弱可用数据.我们必须解决如何在弱可用大数据上完成高质量的近似计算. (3) 深度演化机理:如何认知大数据演化的机理,追索数据错误根源? 数据不是一成不变的,它会随着时间和物理世界的变化而发生演化.现有的大数据研究忽略了按数据的演 化机理所进行的研究,使得数据错误的根源难以追索.我们需要探索大数据的深度演化机理,即,以可用性为核 心的多源信息集合在时间、空间、形态、粒度等多个维度上正向协同的演化机理. 为了应对上述挑战,我们需要以数据的一致性、精确性、完整性、时效性和实体同一性为核心,以保障信 息可用性为目标,研究以下 7 个问题,创建一套完整的确保海量信息可用性的理论、方法和技术. (1) 大数据可用性的表达机理 首先,探索数据的一致性、精确性、完整性、时效性、实体同一性的语义规则,建立大数据可用性语义表 达规则系统,判定规则系统可否公理化,如果可公理化,则建立公理系统;然后,确定从大数据自动发现语义规则 问题的计算复杂性,并设计求解算法;最后,确定大数据可用性自动推理问题的计算复杂性,并设计求解算法. (2) 大数据可用性的判定理论 首先,分别建立大数据的一致性、精确性、完整性、时效性、实体同一性的数学模型;然后,根据大数据研 究可用性这 5 项指标之间的相互影响,建立大数据可用性的综合数学模型;最后,确定大数据可用性判定问题的 计算复杂性,设计求解算法. (3) 大数据的演化原理 探索大数据的演化过程,建立大数据演化的世系模型及追踪技术,包括时空、多粒度、多路径和不确定的 大数据演化的理论,演化的可逆性判定与近似求解算法,演化描述的复杂性理论和方法,以及网络化、多粒度、 随机化的世系追踪和数据错误追踪技术. (4) 大数据量质融合管理的理论和技术 首先,建立支持大数据量质融合管理的数据模型和相关理论,包括数据的逻辑结构、运算系统、数据的语 义约束模型;然后,解决数据质量管理模型和理论与传统数据管理模型和理论的融合问题,建立大数据量质融合 管理的模型和理论;最后,研究大数据量质融合管理关键问题的可计算性和计算复杂性,并设计求解算法. (5) 高质量数据获取与整合的理论和技术 高质量数据的获取,是确保大数据可用性的重要环节.大数据的来源多种多样,类型千差万别,质量参差不 齐,整合困难.这些问题在当今突飞猛进的传感网和物联网背景下尤为严重.我们需要解决如下具有挑战性的问 题:最优化逼近物理世界的高精度数据获取的理论和技术、最大化数据与问题求解相关性的高相关数据获取的 理论和技术、最小化无价值数据的高纯度数据获取的理论和技术. (6) 数据错误自动检测与修复的理论和技术
l608 Journal of so/ fare软件学报Vol27,No.7,Juy2016 数据错误的自动检测和修复是十分困难的问题我们需要在大数据可用性的表达机理、大数据可用性的判 定理论、大数据演化原理的基础上探索大数据错误自动检测和修复的理论和技术,主要包括数据错误自动检 测和修复问题的可计算性理论、计算复杂性理论、修复结果可信性理论、大数据错误自动检测与修复算法 (7)弱可用数据上的近似计算的理论和算法 当一个数据集合中的错误不能彻底修复时我们称其为弱可用数据于是,弱可用数据上近似计算(如查询 分析、挖掘等)的理论和算法成为重要的研究问题弱可用数据上的近似计算不同于传统意义下的近似计算,它 是在具有一致性错误、完整性错误、精确性错误、时效性错误或实体冋一性错误的数据上近似地求解满足给 定精度要求的问题的解现有的近似理论与算法无法支持弱可用数据上的近似计算,因此我们需要研究弱可用 数据近似计算的可行性理论、弱可用数据计算问题的计算复杂性理论和算法、弱可用数据近似计算结果的质 量评估理论 2大数据可用性的研究进展 近年来,人们开展了大量的研究工作,取得了很多研究成果,文献[12-14]是关于数据可用性早期研究工作 的 综述本节综述大数据可用性研究的新进展,包括数据可用性表达机理、数据可用性判定的理论和方法、数据 错误检测与修复的理论与方法、弱可用数据近似计算的理论和算法、高质量数据获取的理论和方法、大数 可用性管理系统 2.1数据可用性的表达机理的研究进展 数据可用性的表达机理主要解决如何表达一个数据集合的数据一致性、精确性、完整性、时效性和实体 同一性及其相关理论问题,为数据可用性的判定和数据错误的自动发现与修复奠定基础 (1)数据一致性的表达机理 文献[!5]对函数依赖理论进行了扩展,提出了基于条件函数依赖的数据一致性表达机制,证明了存在有穷 推理规则集使该机制可有穷公理化,给出了具有4条推理规则的公理系统并证明了公理系统的有效性和完备 性文献[16]研究了如何从数据中有效地发现条件函数依赖的问题提出了4种有效发现条件函数依赖的算法 文献[17-19研究了条件函数依赖的推理问题、覆盖问题、检测问题、传递问题的计算复杂度及其求解算法 文献[44]研究了条件函数依赖的置信度评估问题,提出了基于抽样的条件函数依赖置信度评估算法,并证明了 该算法能够以1-。概率给出相对误差小于ε的估计结果,其中,∞0,0<1. 文献20]针对条件函数依赖无法描述“并”语义的问题,提出了表示支持“与”和“并”语义的扩展的条件函数 依赖文献[21]提出了微条件函数依赖文献[20,211分别证明了各自的扩展条件函数依赖规则系统是可公理化 的,建立了公理系统,证明了公理系统的有效性和完备性,并确定了自动推理问题的计算复杂性,提出了求解算 法文献[120,21]还分别确定了各自的扩展条件函数依赖的自动挖掘问题的计算复杂性,并提出挖掘算法文 [2]提出了概率数据库中随机条件函数依赖 文献[23]在有时间戳的数据上提出了序列依赖语义规则,用来描述随时间变化数据的一致性约束,试图解 决随时间变化数据的一致性错误的发现和修复问题 文献[24]针对异枃数据源中由数据格式不一致引发的一致性错误,利用属性值的相似性扩展了函数依赖, 用来描述异构数据的一致性发现和修复异构数据的一致性错误 文献[25]利用统计模型来描述数据的一致性,并通过求解和比较模型参数的方法来发现和修复数据不一致 性错误文献[26提出了基于统计知识的数据不一致性描述方法,并给出了基于超团的数据一致性提升算法 文献171-75]研究了数据一致性规则挖掘问题分别提出了在数据集合中挖掘各种数据一致性规则的算法 (2)数据完整性的表达机理 传统的数据完整性研究工作一般都建立在封闭世界或开放世界假设的基础上封闭世界假设表示数据库 包含了所有表述现实世界实体的元组,这些元组的某些属性值可能遗缺开放世界假设表示数据库中不仅属性 值可能遗失,描述实体的元组也可能完全遗缺然而,现实世界的数据库经常既不是完全封闭的,也不是完全开 中国科学院软件研究所htp:/ww.jos.org.cn
1608 Journal of Software 软件学报 Vol.27, No.7, July 2016 数据错误的自动检测和修复是十分困难的问题.我们需要在大数据可用性的表达机理、大数据可用性的判 定理论、大数据演化原理的基础上,探索大数据错误自动检测和修复的理论和技术,主要包括:数据错误自动检 测和修复问题的可计算性理论、计算复杂性理论、修复结果可信性理论、大数据错误自动检测与修复算法. (7) 弱可用数据上的近似计算的理论和算法 当一个数据集合中的错误不能彻底修复时,我们称其为弱可用数据.于是,弱可用数据上近似计算(如查询、 分析、挖掘等)的理论和算法成为重要的研究问题.弱可用数据上的近似计算不同于传统意义下的近似计算,它 是在具有一致性错误、完整性错误、精确性错误、时效性错误或实体同一性错误的数据上近似地求解满足给 定精度要求的问题的解.现有的近似理论与算法无法支持弱可用数据上的近似计算,因此,我们需要研究弱可用 数据近似计算的可行性理论、弱可用数据计算问题的计算复杂性理论和算法、弱可用数据近似计算结果的质 量评估理论. 2 大数据可用性的研究进展 近年来,人们开展了大量的研究工作,取得了很多研究成果,文献[12−14]是关于数据可用性早期研究工作的 综述.本节综述大数据可用性研究的新进展,包括数据可用性表达机理、数据可用性判定的理论和方法、数据 错误检测与修复的理论与方法、弱可用数据近似计算的理论和算法、高质量数据获取的理论和方法、大数据 可用性管理系统. 2.1 数据可用性的表达机理的研究进展 数据可用性的表达机理主要解决如何表达一个数据集合的数据一致性、精确性、完整性、时效性和实体 同一性及其相关理论问题,为数据可用性的判定和数据错误的自动发现与修复奠定基础. (1) 数据一致性的表达机理 文献[15]对函数依赖理论进行了扩展,提出了基于条件函数依赖的数据一致性表达机制,证明了存在有穷 推理规则集使该机制可有穷公理化,给出了具有 4 条推理规则的公理系统,并证明了公理系统的有效性和完备 性.文献[16]研究了如何从数据中有效地发现条件函数依赖的问题,提出了 4 种有效发现条件函数依赖的算法. 文献[17−19]研究了条件函数依赖的推理问题、覆盖问题、检测问题、传递问题的计算复杂度及其求解算法. 文献[44]研究了条件函数依赖的置信度评估问题,提出了基于抽样的条件函数依赖置信度评估算法,并证明了 该算法能够以 1−δ的概率给出相对误差小于ε的估计结果,其中,ε>0,0<δ<1. 文献[20]针对条件函数依赖无法描述“并”语义的问题,提出了表示支持“与”和“并”语义的扩展的条件函数 依赖.文献[21]提出了微条件函数依赖.文献[20,21]分别证明了各自的扩展条件函数依赖规则系统是可公理化 的,建立了公理系统,证明了公理系统的有效性和完备性,并确定了自动推理问题的计算复杂性,提出了求解算 法.文献[20,21]还分别确定了各自的扩展条件函数依赖的自动挖掘问题的计算复杂性,并提出挖掘算法.文献 [22]提出了概率数据库中随机条件函数依赖. 文献[23]在有时间戳的数据上提出了序列依赖语义规则,用来描述随时间变化数据的一致性约束,试图解 决随时间变化数据的一致性错误的发现和修复问题. 文献[24]针对异构数据源中由数据格式不一致引发的一致性错误,利用属性值的相似性扩展了函数依赖, 用来描述异构数据的一致性,发现和修复异构数据的一致性错误. 文献[25]利用统计模型来描述数据的一致性,并通过求解和比较模型参数的方法来发现和修复数据不一致 性错误.文献[26]提出了基于统计知识的数据不一致性描述方法,并给出了基于超团的数据一致性提升算法. 文献[71−75]研究了数据一致性规则挖掘问题,分别提出了在数据集合中挖掘各种数据一致性规则的算法. (2) 数据完整性的表达机理 传统的数据完整性研究工作一般都建立在封闭世界或开放世界假设的基础上.封闭世界假设表示数据库 包含了所有表述现实世界实体的元组,这些元组的某些属性值可能遗缺.开放世界假设表示数据库中不仅属性 值可能遗失,描述实体的元组也可能完全遗缺.然而,现实世界的数据库经常既不是完全封闭的,也不是完全开
李建中等:大数据可用性的研究进展 放的基于这个考虑,文献[27,28]扩展了包含依赖提出了一种表示数据完整性的包含依赖规则系统,定义了规则 的语法和语义,证明了规则系统是可公理化的,建立了公理系统证明了22个相关基础问题的不可计算性 coNP完全性、完全性、2-完全性或 EXPTIME-完全性文献[29扩展了文献[27,28]的研究结果 文献[30,31]将传统的完整性理论扩展到XML数据上研究了XML数据的问题完整性表达机制 (3)数据时效性的表达机理 文献[32]在同一个实体具有多个元组的假设下,提出了一种基于规则的数据时效性表示机制,定义了同 实体对应的不同元组的属性值的时序关系表示方法,提出了基于实体的最新值的时效性查询语义,并给出了应 用元组间的时序关系和拷贝关系推导实体最新信息的推理机制基于这种数据时效性表达机制和时效性查询 语义,文献[32]还给出了用户查询的计算复杂性,并研究了在实体最新值缺失的情况下如何扩展元组间拷贝关 系以找到实体的最新值但是,“同一个实体具有多个元组”的假设使得这种数据时效性表达机制具有很大的局 限性 为了突破文献[32]的数据时效性表达机制的局限性文献[33]提出了基于不确定规则的数据时效性表达机 制,定义了数据时效性规则的语法和语义,证明了规则系统是可有穷公理化的,建立了具有两条推理规则的公理 系统证明了公理系统的有效性和完备性,同时证明了数据时效性规则自动推理问题是P问题,确定了问题的时 复杂性下界,并给出求解推理问题的最优化算法文献[3]还证明了规则挖掘问题是NP-难的,并给出O(n)和 O(n2)时间近似挖掘算法,n是数据集合的大小 (4)实体同一性的表达机理 文献[34]提出了基于规则的实体同一性表达机制,定义了实体同一性规则的语法和语义,证明了对于任意 数据集合D都存在一个有效、一致、完整和独立的实体规则集合∑同时证明了可满足问题和语义蕴含问题皆 为P问题而且它们的时间复杂性下界都是),并给出了求解这两个问题的时间复杂性为)的最优化 算法文献[34]还研究了从数据集合D中挖掘实体同一性规则的问题,证明了该问题是P问题且其时间复杂性下 界为D)给出了时间复杂性为O(D)的最优化求解算法并且证明该算法能够从数据集合D中挖掘出满足 有效性、一致性、完整性和独立性的实体同一性规则集合,即,算法是正确的 文献[35]提出了实体同一性描述规则,系统地研究了规则的推理问题,提高了描述实体同一性的能力.文献 [36]进一步在动态语义下研究了实体同一性规则的相互作用及推理问题 文献[37提出用否定规则描述实体的同一性并研究了否定规则对实体同一性的影响.文献[38]提出了用聚 集约束来描述实体同一性的方法文献[39]结合EM算法和无监督学习方法提出了获取实体同一性描述规则的 方法 (5)数据精确性的表达机理 文献[40在“同一个实体具有多个元组”的假设下,提出了一种基于规则的数据精确性表示机制,定义了同 实体对应的不同元组的属性值之间的精确性偏序关系;在此基础上定义了数据精确性规则的语法和语义,确 定了规则系统的推理问题的计算复杂性,给出了求解问题的算法并提出了相应的精确性错误修复框架. 文献[4I]把不确定性视为精确度低的现象,提出了一种基于可能世界语义的数据精确性描述方法,并给出 了对应的精确性评估算法 22数据可用性判定的研究进展 数据可用性判定问题定义如下给定任意数据集合D,计算D的可用性 usability(D)数据可用性判定的关键 在于数据的一致性、精确性、完整性、时效性和实体同一性的判定.本节介绍数据一致性、精确性、完整性 时效性和实体同一性的研究进展 (1)数据一致性判定的理论和算法 文献[42]系统地研究了数据一致性判定问题 ·首先,基于数据一致性表达机制建立了数据一致性的数学模型给定数据集合D和D上的条件函数依 赖集∑D的一致性定义为 Consistency(D=|DD,其中,D是D中满足∑的最大子集,并证明了:如果 中国科学院软件研究所htp:/ww.jos.org.cn
李建中 等:大数据可用性的研究进展 1609 放的.基于这个考虑,文献[27,28]扩展了包含依赖,提出了一种表示数据完整性的包含依赖规则系统,定义了规则 的语法和语义,证明了规则系统是可公理化的,建立了公理系统,证明了 22 个相关基础问题的不可计算性、 coNP-完全性、 3 p Σ -完全性、 2 P Π -完全性或 EXPTIME-完全性.文献[29]扩展了文献[27,28]的研究结果. 文献[30,31]将传统的完整性理论扩展到 XML 数据上,研究了 XML 数据的问题完整性表达机制. (3) 数据时效性的表达机理 文献[32]在同一个实体具有多个元组的假设下,提出了一种基于规则的数据时效性表示机制,定义了同一 实体对应的不同元组的属性值的时序关系表示方法,提出了基于实体的最新值的时效性查询语义,并给出了应 用元组间的时序关系和拷贝关系推导实体最新信息的推理机制.基于这种数据时效性表达机制和时效性查询 语义,文献[32]还给出了用户查询的计算复杂性,并研究了在实体最新值缺失的情况下如何扩展元组间拷贝关 系以找到实体的最新值.但是,“同一个实体具有多个元组”的假设,使得这种数据时效性表达机制具有很大的局 限性. 为了突破文献[32]的数据时效性表达机制的局限性,文献[33]提出了基于不确定规则的数据时效性表达机 制,定义了数据时效性规则的语法和语义,证明了规则系统是可有穷公理化的,建立了具有两条推理规则的公理 系统,证明了公理系统的有效性和完备性,同时证明了数据时效性规则自动推理问题是 P 问题,确定了问题的时 间复杂性下界,并给出求解推理问题的最优化算法.文献[33]还证明了规则挖掘问题是 NP-难的,并给出 O(n)和 O(n2 )时间近似挖掘算法,n 是数据集合的大小. (4) 实体同一性的表达机理 文献[34]提出了基于规则的实体同一性表达机制,定义了实体同一性规则的语法和语义,证明了对于任意 数据集合 D 都存在一个有效、一致、完整和独立的实体规则集合 Σ,同时证明了可满足问题和语义蕴含问题皆 为 P 问题,而且它们的时间复杂性下界都是 Ω(|Σ| 2 ),并给出了求解这两个问题的时间复杂性为 Ω(|Σ| 2 )的最优化 算法.文献[34]还研究了从数据集合 D中挖掘实体同一性规则的问题,证明了该问题是 P问题且其时间复杂性下 界为 Ω(|D| 2 ),给出了时间复杂性为 O(|D| 2 )的最优化求解算法,并且证明该算法能够从数据集合 D 中挖掘出满足 有效性、一致性、完整性和独立性的实体同一性规则集合,即,算法是正确的. 文献[35]提出了实体同一性描述规则,系统地研究了规则的推理问题,提高了描述实体同一性的能力.文献 [36]进一步在动态语义下研究了实体同一性规则的相互作用及推理问题. 文献[37]提出用否定规则描述实体的同一性,并研究了否定规则对实体同一性的影响.文献[38]提出了用聚 集约束来描述实体同一性的方法.文献[39]结合 EM 算法和无监督学习方法,提出了获取实体同一性描述规则的 方法. (5) 数据精确性的表达机理 文献[40]在“同一个实体具有多个元组”的假设下,提出了一种基于规则的数据精确性表示机制,定义了同 一实体对应的不同元组的属性值之间的精确性偏序关系;在此基础上定义了数据精确性规则的语法和语义,确 定了规则系统的推理问题的计算复杂性,给出了求解问题的算法,并提出了相应的精确性错误修复框架. 文献[41]把不确定性视为精确度低的现象,提出了一种基于可能世界语义的数据精确性描述方法,并给出 了对应的精确性评估算法. 2.2 数据可用性判定的研究进展 数据可用性判定问题定义如下:给定任意数据集合 D,计算 D 的可用性 usability(D).数据可用性判定的关键 在于数据的一致性、精确性、完整性、时效性和实体同一性的判定.本节介绍数据一致性、精确性、完整性、 时效性和实体同一性的研究进展. (1) 数据一致性判定的理论和算法 文献[42]系统地研究了数据一致性判定问题. • 首先,基于数据一致性表达机制建立了数据一致性的数学模型.给定数据集合 D 和 D 上的条件函数依 赖集 Σ,D 的一致性定义为 Consistency(D)=|D′|/|D|,其中,D′是 D 中满足 Σ 的最大子集,并证明了:如果
Journal of so/ fare软件学报Vol27,No.7,Juy2016 D满足条件函数依赖集合∑则满足,从而降低了求解判定问题的难度 其次研究了数据一致性判定问题的计算复杂性和近似性证明数据一致性判定问题是NP完全的;不 存在多项式时间(2-近似算法,除非 unique game猜想为真;问题是1.3606不可多项式时间近似的,除 非P=NP,规则为3且属性为4时,问题是1.0625不可近似的; ·最后给出了一种近似比最优化的O( nlogn)时间的2近似算法,并给出了一种O(log(n)时间的(2+)-随 机近似算法 文献[43]研究了使用条件函数依赖评价数据一致性的关键问题—一最小元组删除集的计算问题证明了该 问题是NP完全的给出了基于冲突图的近似求解算法,算法的近似比为2-(1/2)2,其中,是给定的条件函数依 赖集 (2)数据时效性判定的理论和算法 数据时效性判定方法可以分为两类即,基于时间戳的时效性判定和独立于时间戳的时效性判定 基于时间戳的时效性判定要求数据集合中每个数据值具有时间戳文献145-50把数据从上一次更新到本 保质期7给定一个数据文献5把F的时效性定义为概么时效性文献15481假设数据有一个确定的 次使用的时间间隔定义为数据年龄Age,从不同角度定义了数搪 4ge()-7()>0而文献[48]则在T)PAge(V) 的条件下把数据的Age()定义为V的时效性文献[46,47]假设数据时效性随时间流逝的减弱程度可以用时效 性衰减函数/来刻画,定义数据V的时效性为ep)×g.文献[49]把数据年龄定义为数据的时效性文献[50提出 了一种基于模糊逻辑来推断时效性衰减函数的时效性判定方法 针对实际应用中时间戳常常不存在的情况,文献133研究了独立于时间戳的数据时效性判定方法 首先在数据时效性表达机制的基础上提出了数据时效性的数学模型; 然后证明了时效性判定问题是P问题,且其时间复杂性下界为2(n2) 最后给出了两种基于时效图的数据时效性判定算法:一种是针对一般时效图的On1ogn)时间算法,另 种是针对无环时效图的O(m2)时间最优化算法 文献[51]研究了相对于査询的数据时效性判定问题,建立了数据相对时效性的数学模型.针对最新值査询 和时效序列查询这两类查询,提出了查询结果的时效性判定方法,并将每类查询作为一个整体给出了数据集合 相对于每类查询的平均时效性判定方法 (3)数据完整性判定的理论和算法 文献[52]研究了数据完整性判定问题 首先给出了一种数据完整性模型,这种数据模型避免了假阳性错误,即,避免能够由函数依赖可导出的 值被误判为缺失值; ·然后,确定了数据完整性判定问题的计算复杂性证明了该问题是P问题,且其时间复杂度下界是 ·最后给出了时间复杂度为On2)的最优化判定算法并给出了一种适用于大数据的(E,-近似算法,其 时间和空间复杂性均为O(Eln(2) 文献[53]进一步扩展了这项研究结果. 文献[54]综述了早期的数据完整判定的研究工作,介绍了不同种类的数据完整度的定义和计算方法 文献[55]提出了判定地理数据完整性的计算方法文献[56给出了时间序列数据完整性判定方法文献[57, 58]给出了其他特定数据集合的数据完整性判定方法 (4)数据精确性判定的理论和算法 对于数据集合中的不精确值,其精确值难以预知于是,数据精确性判定问题是一个非常困难的问题.文献 [5960]提出了一种多模态数据集的精确性判定方法,使用均方误差这一参数衡量数据的精确性该方法把数据 集合中的数据分为3类,即可量度型、可比性型、分类型针对每类数据的特点建立了不同的精确性数学模型, 并组合这些数学模型,最终建立了数据精确性的数学模型针对精确值可知与不可知两种情况,该方法提供了不 中国科学院软件研究所htp:/ww.jos.org.cn
1610 Journal of Software 软件学报 Vol.27, No.7, July 2016 D′满足条件函数依赖集合 Σ,则满足 Σ* ,从而降低了求解判定问题的难度; • 其次,研究了数据一致性判定问题的计算复杂性和近似性,证明:数据一致性判定问题是 NP-完全的;不 存在多项式时间(2−ε)-近似算法,除非 unique game 猜想为真;问题是 1.3606 不可多项式时间近似的,除 非 P=NP;规则为 3 且属性为 4 时,问题是 1.0625 不可近似的; • 最后,给出了一种近似比最优化的 O(nlogn)时间的 2-近似算法,并给出了一种 O(log(n))时间的(2+ε)-随 机近似算法. 文献[43]研究了使用条件函数依赖评价数据一致性的关键问题——最小元组删除集的计算问题,证明了该 问题是 NP-完全的,给出了基于冲突图的近似求解算法,算法的近似比为 2−(1/2)|Σ| ,其中,Σ是给定的条件函数依 赖集. (2) 数据时效性判定的理论和算法 数据时效性判定方法可以分为两类,即,基于时间戳的时效性判定和独立于时间戳的时效性判定. 基于时间戳的时效性判定要求数据集合中每个数据值具有时间戳.文献[45−50]把数据从上一次更新到本 次使用的时间间隔定义为数据年龄 Age,从不同角度定义了数据的时效性.文献[45,48]假设数据有一个确定的 保质期 T.给定一个数据 V,文献[45]把 V 的时效性定义为概率 Pr[Age(V)−T(V)>0],而文献[48]则在 T(V)>Age(V) 的条件下把数据的 Age(V)定义为 V 的时效性.文献[46,47]假设数据时效性随时间流逝的减弱程度可以用时效 性衰减函数 f 来刻画,定义数据 V 的时效性为 e−f(V)×Age(V) .文献[49]把数据年龄定义为数据的时效性.文献[50]提出 了一种基于模糊逻辑来推断时效性衰减函数的时效性判定方法. 针对实际应用中时间戳常常不存在的情况,文献[33]研究了独立于时间戳的数据时效性判定方法. • 首先,在数据时效性表达机制的基础上提出了数据时效性的数学模型; • 然后,证明了时效性判定问题是 P 问题,且其时间复杂性下界为Ω(n2 ); • 最后,给出了两种基于时效图的数据时效性判定算法:一种是针对一般时效图的 O(n2 logn)时间算法,另 一种是针对无环时效图的 O(n2 )时间最优化算法. 文献[51]研究了相对于查询的数据时效性判定问题,建立了数据相对时效性的数学模型.针对最新值查询 和时效序列查询这两类查询,提出了查询结果的时效性判定方法,并将每类查询作为一个整体,给出了数据集合 相对于每类查询的平均时效性判定方法. (3) 数据完整性判定的理论和算法 文献[52]研究了数据完整性判定问题. • 首先,给出了一种数据完整性模型,这种数据模型避免了假阳性错误,即,避免能够由函数依赖可导出的 值被误判为缺失值; • 然后,确定了数据完整性判定问题的计算复杂性,证明了该问题是 P 问题,且其时间复杂度下界是 Ω(n2 ); • 最后,给出了时间复杂度为 O(n2 )的最优化判定算法,并给出了一种适用于大数据的(ε,δ)-近似算法,其 时间和空间复杂性均为 O(ε −2 ln(δ −1 )). 文献[53]进一步扩展了这项研究结果. 文献[54]综述了早期的数据完整判定的研究工作,介绍了不同种类的数据完整度的定义和计算方法. 文献[55]提出了判定地理数据完整性的计算方法.文献[56]给出了时间序列数据完整性判定方法.文献[57, 58]给出了其他特定数据集合的数据完整性判定方法. (4) 数据精确性判定的理论和算法 对于数据集合中的不精确值,其精确值难以预知.于是,数据精确性判定问题是一个非常困难的问题.文献 [59,60]提出了一种多模态数据集的精确性判定方法,使用均方误差这一参数衡量数据的精确性.该方法把数据 集合中的数据分为 3 类,即可量度型、可比性型、分类型.针对每类数据的特点,建立了不同的精确性数学模型, 并组合这些数学模型,最终建立了数据精确性的数学模型.针对精确值可知与不可知两种情况,该方法提供了不
李建中等:大数据可用性的研究进展 同的数据精确性判定算法在精确值可知的情况下,直接用均方误差来判定数据的精确性;在精确值缺失的情况 下,针对不同的数据类型,分别提出了二次规划算法、迭代算法和EM算法,以求解各类数据精确性的判定问题 最后确定整个数据集合的精确性. (5)实体同一性判定的理论和算法 文献[61]提出了一种基于实体识别结果的实体同一性判定方法 首先,定义了元组之间的距离用以描述任意两个元组在所有属性上的值的不一致的程度,并基于元组 的距离进一步定义了实体同一性的数学模型 其次,研究了实体同一性判定的计算复杂性证明了实体同一性判定问题是NP难的 最后分别给出了求解实体同一性判定问题的4个子问题的 O(nlogn)时间2-近似算法和 O(nlogn)时间 n近似算法,并最终给出了O( nlogn)时间的n-近似算法 2.3数据错误检测与修复研究进 数据可用性具有数据一致性、完整性、精确性、时效性和实体同一性这5个维度.数据错误检测和修复方 面的研究主要围绕一致性、完整性、时效性和实体同一性这5个方面开展研究,在考虑了多维度错误的同时检 测与修复问题本节介绍这些研究结果 (1)数据一致性错误的检测与修复 基于条件函数依赖,人们提出了很多数据一致性错误的检测与修复方法文献[6,63]针对集中存储的关系 数据库,使用SQL语言设计了自动检测算法,用于查找违反条件函数依赖和条件包含依赖的元组文献[64]研究 了在分布式环境下检测数据一致性错误的问题,目标是最小化数据通信量文献[65]给出了一种增量式的分布 式数据库中数据一致性错误的检测方法 文献[66铪给出了基于主数据的数据一致性修复问题给定数据集合D、条件函数依赖集∑和主数据Dm修 复D中的数据一致性错误 首先证明了该问题是NP完全的、不存在多项式时间的 O(ogn)近似算法除非NP=P, 然后,提出了与主数据相关的修复规则证明修复规则的一致性问题和覆盖问题是coNP-完全的; ·最后,基于主数据和修复规则,提出了启发式数据一致性错误修复算法」 文献[6研究了基于用户反馈的数据一致性错误修复问题,证明了对于多类查询该问题分别是NP完全 的、∑-完全的或 PSPACE完全的而对于选择投影查询该问题是P问题针对选择-投影查询给出了时间复 杂性为O(n)的精确的问题求解算法 文献[68]研究了数据一致性修复问题中,数据集合的一致性表达规则可能不正确的问题,提出了相对信任 的概念,用以判定是数据可信还是一致性表达规则可信,从而确定是修改数据还是修改一致性表达规则,并提 出了相应算法 文献69]设计了一个数据不一致性修复框架提出了不同的一致性约束条件类型和选择最优值的方法,用 以解决数据一致性错误修复问题,提出了新的修复规则语义和一种计算最优修复方案的算法 文献[70]提出了基于 Hadoop并行平台的不一致数据检测与修复算法 (2)数据时效性错误的检测与修复 文献[76]合并时效函数依赖与近似函数依赖提出了时效近似函数依赖并给出其基本定义和一些相关的 数据挖掘技术 文献[7提出了一种模型,通过部分时间顺序和时间约束来指定数据时效性并通过不变的条件函数依赖 来强化数据时效性 文献[78]针对网络数据的时效性提出了时效规则发现问题给出了基于关联规则和离群点识别的机器学习 算法,从而实现了数据的时效性检测与修复 文献[79提出一类新的时效性修复规则CRR,将规则和统计的方法结合起来修复过时数据该规则一方面 能够通过规则模式表达领域知识,另一方面还能够使用其特有的分布表来描述数据随时间变化的统计信息. 中国科学院软件研究所htp:/ww.jos.org.cn
李建中 等:大数据可用性的研究进展 1611 同的数据精确性判定算法.在精确值可知的情况下,直接用均方误差来判定数据的精确性;在精确值缺失的情况 下,针对不同的数据类型,分别提出了二次规划算法、迭代算法和 EM 算法,以求解各类数据精确性的判定问题, 最后确定整个数据集合的精确性. (5) 实体同一性判定的理论和算法 文献[61]提出了一种基于实体识别结果的实体同一性判定方法. • 首先,定义了元组之间的距离,用以描述任意两个元组在所有属性上的值的不一致的程度,并基于元组 的距离进一步定义了实体同一性的数学模型; • 其次,研究了实体同一性判定的计算复杂性,证明了实体同一性判定问题是 NP-难的; • 最后,分别给出了求解实体同一性判定问题的 4 个子问题的 O(nlogn)时间 2-近似算法和 O(nlogn)时间 n-近似算法,并最终给出了 O(nlogn)时间的 n-近似算法. 2.3 数据错误检测与修复研究进展 数据可用性具有数据一致性、完整性、精确性、时效性和实体同一性这 5 个维度.数据错误检测和修复方 面的研究主要围绕一致性、完整性、时效性和实体同一性这 5 个方面开展研究,在考虑了多维度错误的同时检 测与修复问题.本节介绍这些研究结果. (1) 数据一致性错误的检测与修复 基于条件函数依赖,人们提出了很多数据一致性错误的检测与修复方法.文献[62,63]针对集中存储的关系 数据库,使用 SQL 语言设计了自动检测算法,用于查找违反条件函数依赖和条件包含依赖的元组.文献[64]研究 了在分布式环境下检测数据一致性错误的问题,目标是最小化数据通信量.文献[65]给出了一种增量式的分布 式数据库中数据一致性错误的检测方法. 文献[66]给出了基于主数据的数据一致性修复问题:给定数据集合 D、条件函数依赖集 Σ 和主数据 Dm,修 复 D 中的数据一致性错误. • 首先,证明了该问题是 NP-完全的、不存在多项式时间的 O(logn)-近似算法,除非 NP=P; • 然后,提出了与主数据相关的修复规则,证明修复规则的一致性问题和覆盖问题是 coNP-完全的; • 最后,基于主数据和修复规则,提出了启发式数据一致性错误修复算法. 文献[67]研究了基于用户反馈的数据一致性错误修复问题,证明了对于多类查询,该问题分别是 NP-完全 的、 2 P Σ -完全的或 PSPACE-完全的;而对于选择-投影查询,该问题是 P 问题.针对选择-投影查询,给出了时间复 杂性为 O(n2 )的精确的问题求解算法. 文献[68]研究了数据一致性修复问题中,数据集合的一致性表达规则可能不正确的问题,提出了相对信任 的概念,用以判定是数据可信,还是一致性表达规则可信,从而确定是修改数据还是修改一致性表达规则,并提 出了相应算法. 文献[69]设计了一个数据不一致性修复框架,提出了不同的一致性约束条件类型和选择最优值的方法,用 以解决数据一致性错误修复问题,提出了新的修复规则语义和一种计算最优修复方案的算法. 文献[70]提出了基于 Hadoop 并行平台的不一致数据检测与修复算法. (2) 数据时效性错误的检测与修复 文献[76]合并时效函数依赖与近似函数依赖,提出了时效近似函数依赖,并给出其基本定义和一些相关的 数据挖掘技术. 文献[77]提出了一种模型,通过部分时间顺序和时间约束来指定数据时效性,并通过不变的条件函数依赖 来强化数据时效性. 文献[78]针对网络数据的时效性提出了时效规则发现问题,给出了基于关联规则和离群点识别的机器学习 算法,从而实现了数据的时效性检测与修复. 文献[79]提出一类新的时效性修复规则 CRR,将规则和统计的方法结合起来修复过时数据.该规则一方面 能够通过规则模式表达领域知识,另一方面还能够使用其特有的分布表来描述数据随时间变化的统计信息.由
l612 Journal of so/ fare软件学报Vol27,No.7,Juy2016 于静态数据上的CCR模式生成问题是NP难的该文献给出了两种解决该问题的多项式时间近似算法,并提出 了修复代价约束条件下的最优修复计划产生算法.文献[80]研究动态数据环境下CRR的生成问题以及基于 CRR的数据修复问题,提出了两条剪枝原则,用于快速产生CRR模式 (3)数据完整性错误的检测与修复 数据完全性错误检测与修复的研究主要集中在缺失值的填充方法研究上按照缺失值填充所使用的数据 来源缺失值填充方法可以分为内部数据填充和外部数据填充两类内部数据填充是利用正在修复的数据集合 中的值来填充缺失值;而外部数据填充是指利用正在修复的数据集合之外的数据来填充缺失值,如网上数据. 文献[81]研究缺失值填充的基础理论分析了3种不完整数据修复方法,即,基于确定答案和表现系统的方 法、基于逻辑的方法和基于相对值排序的方法为缺失值填充建立了理论基础文献[98]证明,在普通条件下缺失 值的最小化修复是NP难问题,并提出了有效的近似算法 文献[82-89]提出了利用内部数据填充缺失值的方法文献[82,83,85-88]研究了连续型缺失值的填充问题. 文献[83,87,88]提出了如何填充性别、国家等离散型缺失值的方法.文献[89,90提出了利用相似性规则填充非数 值型缺失值的方法 文献[91-93]研究了用网络上的数据填充缺失值的问题,提出了多种利用网络数据来填充缺失值的方法.文 献[95]提出了以最小化网络查询代价为目标的利用网络数据填充缺失值的方法文献6]提出了利用贝叶斯网 络与众包相结合,利用网络数据缺失值填充的方法,这种方法在利用贝叶斯网络进行简单概率推理的基础上,结 合了众包技术,将部分缺失元组发送至众包平台,利用人工反馈获得可靠的填充值 文献[94]提出了利用内部数据和外部数据相结合的缺失值填充方法 文献[97]研究了半结构化数据开闭标签不匹配的问题提出了一种动态规划算法和一种基于经验主义的组 合边界算法,以填充丢失的标签. (4)实体同一性错误的检测与修复 实体同一性错误的检测与修复的关键是实体识别,即,从数据集合中发现描述现实世界同一实体的不同数 据实体识别的研究结果很多 使用众包的方法来提高实体识别精度是目前的一个研究热点文献[99]提出一种基于众包的实体识别方 法,提高了识别结果的精度文献[100]针对已有的基于众包的实体识别算法需要开发者参与而导致实体匹配算 法扩展性不强的问题,提出了无需开发者参与的众包算法文献[101]研究了提高众包方法中人类回答出错的问 题提出了 bDENSE算法提高了利用众包方法识别实体的准确率文献[02]提出了一种人机混合的实体识别方 法文献[03]针对实体识别中计算机对一些实体的识别准确率低而需要人工标记相似实体对的问题,提出了 种以最小化人工标记实体对数目的实体识别方法 非结构数据中的实体识别问题也是目前人们关注的热点,目前的工作主要集中在链接描述同一实体的不 同命名上文献[04]针对微博文本的实体链接问题通过社交和时间上下文分析,考虑实体流行程度、实体近期 行程度、用户兴趣这3个方面提出了一种实体链接方法文献[105]针对网络文本和复杂信息网络的关联 题提出了一种概率模型,以链接各个命名的实体并使用EM算法对模型中的链接权重进行估计文献[106针对 商业过程中的重复事件检测问题提出了一个新的事件相似度函数迭代地计算邻居间的相似度,并给出了相应 的算法 动态变化数据中的实体识别也是一个重要的研究问题文献[107针对时序数据建立一个实体变化模型,用 来实现动态变化数据中的实体识别文献[108]提出了一种方法解决如何利用已有的实体识别结果来节省数据 变化所带来的实体识别的冗余工作的问题文献[09]针对大数据时代数据变化快而导致的描述实体的记录集 合快速失效问题提出了一个新的解决方案,递增、有效地更新实体识别结果,确保实体识别结果的质量 提高实体识别的效率是实体识别的目标之一文献[10针对内嵌数据的重复删除过程中磁盘瓶颈对主存 影响的问题,提出了一种能够动态地从磁盘中预先提取指纹并存入缓存的框架,以有效地支持实体识别文献 [I.用基于抽样的算法来提高实体识别的效率,该算法与其他算法相比,效率提升了2~3个数量级文献[2 中国科学院软件研究所htp:/ww.jos.org.cn
1612 Journal of Software 软件学报 Vol.27, No.7, July 2016 于静态数据上的 CCR 模式生成问题是 NP-难的,该文献给出了两种解决该问题的多项式时间近似算法,并提出 了修复代价约束条件下的最优修复计划产生算法.文献[80]研究动态数据环境下 CRR 的生成问题以及基于 CRR 的数据修复问题,提出了两条剪枝原则,用于快速产生 CRR 模式. (3) 数据完整性错误的检测与修复 数据完全性错误检测与修复的研究主要集中在缺失值的填充方法研究上.按照缺失值填充所使用的数据 来源,缺失值填充方法可以分为内部数据填充和外部数据填充两类.内部数据填充是利用正在修复的数据集合 中的值来填充缺失值;而外部数据填充是指利用正在修复的数据集合之外的数据来填充缺失值,如网上数据. 文献[81]研究缺失值填充的基础理论,分析了 3 种不完整数据修复方法,即,基于确定答案和表现系统的方 法、基于逻辑的方法和基于相对值排序的方法,为缺失值填充建立了理论基础.文献[98]证明,在普通条件下缺失 值的最小化修复是 NP-难问题,并提出了有效的近似算法. 文献[82−89]提出了利用内部数据填充缺失值的方法.文献[82,83,85−88]研究了连续型缺失值的填充问题. 文献[83,87,88]提出了如何填充性别、国家等离散型缺失值的方法.文献[89,90]提出了利用相似性规则填充非数 值型缺失值的方法. 文献[91−93]研究了用网络上的数据填充缺失值的问题,提出了多种利用网络数据来填充缺失值的方法.文 献[95]提出了以最小化网络查询代价为目标的利用网络数据填充缺失值的方法.文献[96]提出了利用贝叶斯网 络与众包相结合,利用网络数据缺失值填充的方法,这种方法在利用贝叶斯网络进行简单概率推理的基础上,结 合了众包技术,将部分缺失元组发送至众包平台,利用人工反馈获得可靠的填充值. 文献[94]提出了利用内部数据和外部数据相结合的缺失值填充方法. 文献[97]研究了半结构化数据开闭标签不匹配的问题,提出了一种动态规划算法和一种基于经验主义的组 合边界算法,以填充丢失的标签. (4) 实体同一性错误的检测与修复 实体同一性错误的检测与修复的关键是实体识别,即,从数据集合中发现描述现实世界同一实体的不同数 据.实体识别的研究结果很多. 使用众包的方法来提高实体识别精度,是目前的一个研究热点.文献[99]提出一种基于众包的实体识别方 法,提高了识别结果的精度.文献[100]针对已有的基于众包的实体识别算法需要开发者参与而导致实体匹配算 法扩展性不强的问题,提出了无需开发者参与的众包算法.文献[101]研究了提高众包方法中人类回答出错的问 题,提出了 bDENSE 算法,提高了利用众包方法识别实体的准确率.文献[102]提出了一种人机混合的实体识别方 法.文献[103]针对实体识别中计算机对一些实体的识别准确率低而需要人工标记相似实体对的问题,提出了一 种以最小化人工标记实体对数目的实体识别方法. 非结构数据中的实体识别问题也是目前人们关注的热点,目前的工作主要集中在链接描述同一实体的不 同命名上.文献[104]针对微博文本的实体链接问题,通过社交和时间上下文分析,考虑实体流行程度、实体近期 流行程度、用户兴趣这 3 个方面,提出了一种实体链接方法.文献[105]针对网络文本和复杂信息网络的关联问 题,提出了一种概率模型,以链接各个命名的实体,并使用 EM 算法对模型中的链接权重进行估计.文献[106]针对 商业过程中的重复事件检测问题,提出了一个新的事件相似度函数,迭代地计算邻居间的相似度,并给出了相应 的算法. 动态变化数据中的实体识别也是一个重要的研究问题.文献[107]针对时序数据建立一个实体变化模型,用 来实现动态变化数据中的实体识别.文献[108]提出了一种方法,解决如何利用已有的实体识别结果来节省数据 变化所带来的实体识别的冗余工作的问题.文献[109]针对大数据时代数据变化快而导致的描述实体的记录集 合快速失效问题,提出了一个新的解决方案,递增、有效地更新实体识别结果,确保实体识别结果的质量. 提高实体识别的效率是实体识别的目标之一.文献[110]针对内嵌数据的重复删除过程中磁盘瓶颈对主存 影响的问题,提出了一种能够动态地从磁盘中预先提取指纹并存入缓存的框架,以有效地支持实体识别.文献 [111]采用基于抽样的算法来提高实体识别的效率,该算法与其他算法相比,效率提升了 2~3 个数量级.文献[112]
李建中等:大数据可用性的研究进展 1613 提出了大数据实体识别的近似算法文献[1l提出了多模态数据的实体识别方法文献[4在无需计算元组相 似性的前提下,提岀了一种新的实体识别规则,有效地描述了实体匹配条件,并提出从数据中发现规则的有效算 法,给出了基于规则的实体识别算法 提高实体识别的准确率,是实体识别的另一个目标文献[-118]提出了一系列具有高准确率的实体识别 实体不同一错误的修复,通常称为真值发现,即,发现描述同一实体同一属性的不同值中的真实值.文献 1!9]针对真值发现中的长尾现象提出了一种置信度可知的真值发现方法文献[120提出了不同数据源的数据 冲突的两种解决方法文献[12]利用概率模型解决了流数据中的真值发现问题.文献[I2提出了一种自动真值 发现算法,利用 Sherlock规则和参考表,发现冲突数据集合中的真值 (5)多维度错误的组合修复方法 文献[123]研究了数据可用性各个维度之间的关系,发现: 完整性错误修复结果会引起一致性、时效性、精确性的变化; 致性错误修复结果会引起时效性和精确性的变化, 时效性错误修复结果会引起一致性和精确性的变化 清确性错误修复结果不会引起其他可用性维度的变化. 这些结果为多维度错误的组合修复奠定了基础 文献[124]提出了同时修复数据时效性错误和一致性错误的方法,利用最新的和一致的实体数据构造出准 确的实体描述数据 文献[125提出了同时检测和修复数据的一致性错误、完整性错误和实体同一性错误的优化技术 (6)其他错误检测与修复方法 些学者研究了数据错误根源的发现问题文献[126利用贝叶斯方法来建立代价模型,用以诊断大数据中 发生的错误,并判断错误发生的源头和原因文献[127扩展了文献[16]中提出的基于贝叶斯推理的代价模型 用于发现数据中的错误的共同属性追寻产生错误的原因 很多学者硏究了如何组合现有方法实现数据错误的检测与修复.文献[128]结合定量数据清洗和逻辑数据 洗方法,将数据清洗问题转化为最小统计失真修复问题给出了基于EMD的修复策略文献29]将模式映 和数据修复两个问题综合考虑给出了模式映射和数据修复问题的综合定义,提出了求解该问题的基于 Chase 的算法文献[130]提出了一种统一框架来处理数据清洗问题文献[131提出了基于正则表达式的结构化数据修 复算法 些学者研究了特定类型数据的错误清洗问题文献[132]提出了基于众包的不确定数据的清洗方法文献 [13]提出了事件数据错误的检测与修复方法 一些学者研究了动态数据上的错误检测与修复问题文献[34提出了动态变化数据的数据修复分类器在 考虑数据语法错误和语义错误的基础上加入了用户的修复偏好根据历史修复记录来预测当前所需的修复方 法文献[135将增量错误检测技术应用于分布式数据上,试图解决在数据不断变化的情况下数据错误的动态检 测问题,证明了该问题是NP难的,提出了增量式错误检测算法文献[136]根据数据分布利用数据分区和机器学 习技术预测可能的数据更新,提出了一种动态数据错误检测与修复方法 2.4高质量数据获取的研究进展 大数据的来源多种多样,如 Internet上的丰富数据资源、物联网和科学实验系统中的传感器或传感网数据 源的质量会极大地影响数据的可用性高质量数据源的选择,是获得高质量数据的基础高质量的大数据获取方 法,是确保数据获取质量的关键近年来,高质量数据获取的研究主要集中在高质量数据源的选择、 Internet数据 的高质量获取方法和基于传感器或传感网的感知数据的高质量获取方法这3个方面本节介绍这3个方面的研 究进展 (1)高质量数据源的选择方法 ◎中国科学院软件研究所htp:/w.jos.org.cn
李建中 等:大数据可用性的研究进展 1613 提出了大数据实体识别的近似算法.文献[113]提出了多模态数据的实体识别方法.文献[114]在无需计算元组相 似性的前提下,提出了一种新的实体识别规则,有效地描述了实体匹配条件,并提出从数据中发现规则的有效算 法,给出了基于规则的实体识别算法. 提高实体识别的准确率,是实体识别的另一个目标.文献[115−118]提出了一系列具有高准确率的实体识别 方法. 实体不同一错误的修复,通常称为真值发现,即,发现描述同一实体同一属性的不同值中的真实值.文献 [119]针对真值发现中的长尾现象,提出了一种置信度可知的真值发现方法.文献[120]提出了不同数据源的数据 冲突的两种解决方法.文献[121]利用概率模型解决了流数据中的真值发现问题.文献[122]提出了一种自动真值 发现算法,利用 Sherlock 规则和参考表,发现冲突数据集合中的真值. (5) 多维度错误的组合修复方法 文献[123]研究了数据可用性各个维度之间的关系,发现: • 完整性错误修复结果会引起一致性、时效性、精确性的变化; • 一致性错误修复结果会引起时效性和精确性的变化; • 时效性错误修复结果会引起一致性和精确性的变化; • 精确性错误修复结果不会引起其他可用性维度的变化. 这些结果为多维度错误的组合修复奠定了基础. 文献[124]提出了同时修复数据时效性错误和一致性错误的方法,利用最新的和一致的实体数据构造出准 确的实体描述数据. 文献[125]提出了同时检测和修复数据的一致性错误、完整性错误和实体同一性错误的优化技术. (6) 其他错误检测与修复方法 一些学者研究了数据错误根源的发现问题.文献[126]利用贝叶斯方法来建立代价模型,用以诊断大数据中 发生的错误,并判断错误发生的源头和原因.文献[127]扩展了文献[126]中提出的基于贝叶斯推理的代价模型, 用于发现数据中的错误的共同属性,追寻产生错误的原因. 很多学者研究了如何组合现有方法实现数据错误的检测与修复.文献[128]结合定量数据清洗和逻辑数据 清洗方法,将数据清洗问题转化为最小统计失真修复问题,给出了基于 EMD 的修复策略.文献[129]将模式映射 和数据修复两个问题综合考虑,给出了模式映射和数据修复问题的综合定义,提出了求解该问题的基于 Chase 的算法.文献[130]提出了一种统一框架来处理数据清洗问题.文献[131]提出了基于正则表达式的结构化数据修 复算法. 一些学者研究了特定类型数据的错误清洗问题.文献[132]提出了基于众包的不确定数据的清洗方法.文献 [133]提出了事件数据错误的检测与修复方法. 一些学者研究了动态数据上的错误检测与修复问题.文献[134]提出了动态变化数据的数据修复分类器,在 考虑数据语法错误和语义错误的基础上加入了用户的修复偏好,根据历史修复记录来预测当前所需的修复方 法.文献[135]将增量错误检测技术应用于分布式数据上,试图解决在数据不断变化的情况下数据错误的动态检 测问题,证明了该问题是 NP-难的,提出了增量式错误检测算法.文献[136]根据数据分布,利用数据分区和机器学 习技术预测可能的数据更新,提出了一种动态数据错误检测与修复方法. 2.4 高质量数据获取的研究进展 大数据的来源多种多样,如 Internet 上的丰富数据资源、物联网和科学实验系统中的传感器或传感网.数据 源的质量会极大地影响数据的可用性.高质量数据源的选择,是获得高质量数据的基础.高质量的大数据获取方 法,是确保数据获取质量的关键.近年来,高质量数据获取的研究主要集中在高质量数据源的选择、Internet 数据 的高质量获取方法和基于传感器或传感网的感知数据的高质量获取方法这 3 个方面.本节介绍这 3 个方面的研 究进展. (1) 高质量数据源的选择方法
1614 Journal of so/ fare软件学报Vol27,No.7,Juy2016 为了确保高质量地获取数据,高质量的数据源选择是十分重要的文献[13刀研究了网络信息抽取器在数据 中引入错误的概率,提岀了数据源的正确度和所抽取数据的正确度的联合推理概率模型,用于解决数据源可信 度的评估问题文献[138]针对传统数据集成使用的数据源选择算法仅考虑静态数据源以及仅以数据融合准确 度为衡量标准的问题,提出了新的数据源质量评估标准和它们的计算模型,并针对动态数据源给出了一种高质 量数据源选择方法文献[139针对数据融合问题提出了基于数据源的质量,通过贝叶斯分析推导数据源质量 方法文献[40]针对实际应用中经常出现的同一个实体具有多个冲突数据源的情况,提出了源数据可靠性的 估计方法文献[141]介绍了作者建立的数据源选择系统,很好地解决了数据一致性问题 (2) Internet数据的高质量获取方法 文献[142]发现,数据源之间的数据复制关系能够帮助系统更好地选取高质量的数据源、改善集成数据的可 用性针对静态数据,提出了基于贝叶斯分析的方法,判定数据源之间的复制关系,并基于复制关系提出了高质 量数据获取与整合的方法提高了获取与整合后的数据的可用性文献[43]针对动态数据,提出了利用数据源中 的数据更新历史来判定数据源之间复制关系的方法,利用隐马尔可夫模型来判定数据源的复制关系并利用贝 叶斯模型改善数据获取的过程提高了数据获取质量文献[44进一步考虑更复杂的数据复制关系包括部分数 据复制、多个数据源同步复制、多数据源传递复制给出了判定复制关系、提高数据集成质量的算法文献[14 给出了一个判定数据复制关系的演示系统原型 文献[146]对 Internet数据高质量获取与融合的研究工作进行了系统的综述 (3)感知数据的高质量获取方法 文献[147,148]针对无线传感网能量受限的特点探索了在保障数据精确性的前提下,以最小能量开销获取 感知数据的问题,提出了从无线传感网获取数据的(-近似随机算法,确保获取数据的精度大于ε的概率小于δ 文献[149,150]研究了如何从传感网获取数据,使得物理世界能够被准确近似,从而获取高精度数据使用 Hermit插值、三次样条插值、分段线性拟合等方法,提出了多种面向物理过程的高精度数据获取算法,实现了 对物理世界的s近似,其中,∞0 文献[51]针对地理位置相近的传感器节点的数据中存在冗余数据的问题提出了位置敏感的数据获取方 法利用数据源之间的地理关联特征过滤冗余数据,提高了获取的数据在事件监测应用中的可用性,降低了误判 概率 文献[152]研究了多模态数据获取问题,定义了基于事件模型和代价约束的最优覆盖问题,证明了该问题是 NP完全的提出了求解该问题的O(n1)时间准确算法和O(n)时间的(1-e-)近似算法其中n是节点个数k是 节点的类别数 文献[54,155]分别针对感知大数据和多种应用并行执行这两种情况,提出了感知大数据的支配数据集的 获取方法和同时支持多应用的高质量感知数据获取方法 文献[156,157]针对恶意篡改感知数据的问题,提出了两种确保感知数据不被破坏的方法从而保证了数据 获取的质量 2.5弱可用数据近似计算的研究进展 当一个数据集合的数据错误不能被彻底清除时,我们称其为弱可用数据弱可用数据的计算是一个新研究 领域,研究成果还不多,主要集中在弱可用数据的查询、挖掘和查询结果的质量评估上本节介绍弱可用数据计 算的主要研究结果 (1)弱可用数据上的查询处理与挖掘 针对具有实体统一性错误的数据,文献[158]研究了弱可用数据的查询处理问题提出了在具有实体同一性 错误的数据上处理选择-投影-连接查询的算法 文献[159]统一考虑实体识别和数据集成,提出了同时支持实体识别和数据集成的在线查询处理方法文献 [160]提出了在具有实体同一性错误的数据上求解相似性连接的算法 针对具有完整性数据的数据,文献[61]提出了基于改写关系代数表达式的查询处理方法文献[62]实现了 中国科学院软件研究所htp:/ww.jos.org.cn
1614 Journal of Software 软件学报 Vol.27, No.7, July 2016 为了确保高质量地获取数据,高质量的数据源选择是十分重要的.文献[137]研究了网络信息抽取器在数据 中引入错误的概率,提出了数据源的正确度和所抽取数据的正确度的联合推理概率模型,用于解决数据源可信 度的评估问题.文献[138]针对传统数据集成使用的数据源选择算法仅考虑静态数据源以及仅以数据融合准确 度为衡量标准的问题,提出了新的数据源质量评估标准和它们的计算模型,并针对动态数据源给出了一种高质 量数据源选择方法.文献[139]针对数据融合问题,提出了基于数据源的质量,通过贝叶斯分析,推导数据源质量 的方法.文献[140]针对实际应用中经常出现的同一个实体具有多个冲突数据源的情况,提出了源数据可靠性的 估计方法.文献[141]介绍了作者建立的数据源选择系统,很好地解决了数据一致性问题. (2) Internet 数据的高质量获取方法 文献[142]发现,数据源之间的数据复制关系能够帮助系统更好地选取高质量的数据源、改善集成数据的可 用性.针对静态数据,提出了基于贝叶斯分析的方法,判定数据源之间的复制关系,并基于复制关系提出了高质 量数据获取与整合的方法,提高了获取与整合后的数据的可用性.文献[143]针对动态数据,提出了利用数据源中 的数据更新历史来判定数据源之间复制关系的方法,利用隐马尔可夫模型来判定数据源的复制关系,并利用贝 叶斯模型改善数据获取的过程,提高了数据获取质量.文献[144]进一步考虑更复杂的数据复制关系,包括部分数 据复制、多个数据源同步复制、多数据源传递复制,给出了判定复制关系、提高数据集成质量的算法.文献[145] 给出了一个判定数据复制关系的演示系统原型. 文献[146]对 Internet 数据高质量获取与融合的研究工作进行了系统的综述. (3) 感知数据的高质量获取方法 文献[147,148]针对无线传感网能量受限的特点,探索了在保障数据精确性的前提下,以最小能量开销获取 感知数据的问题,提出了从无线传感网获取数据的(ε,δ)-近似随机算法,确保获取数据的精度大于ε的概率小于δ. 文献[149,150]研究了如何从传感网获取数据,使得物理世界能够被准确近似,从而获取高精度数据.使用 Hermit 插值、三次样条插值、分段线性拟合等方法,提出了多种面向物理过程的高精度数据获取算法,实现了 对物理世界的ε-近似[153],其中,ε>0. 文献[151]针对地理位置相近的传感器节点的数据中存在冗余数据的问题,提出了位置敏感的数据获取方 法.利用数据源之间的地理关联特征过滤冗余数据,提高了获取的数据在事件监测应用中的可用性,降低了误判 的概率. 文献[152]研究了多模态数据获取问题,定义了基于事件模型和代价约束的最优覆盖问题,证明了该问题是 NP-完全的,提出了求解该问题的 O(nk−1 )时间准确算法和 O(n5 )时间的(1−e−1 )-近似算法,其中,n 是节点个数,k 是 节点的类别数. 文献[154,155]分别针对感知大数据和多种应用并行执行这两种情况,提出了感知大数据的支配数据集的 获取方法和同时支持多应用的高质量感知数据获取方法. 文献[156,157]针对恶意篡改感知数据的问题,提出了两种确保感知数据不被破坏的方法,从而保证了数据 获取的质量. 2.5 弱可用数据近似计算的研究进展 当一个数据集合的数据错误不能被彻底清除时,我们称其为弱可用数据.弱可用数据的计算是一个新研究 领域,研究成果还不多,主要集中在弱可用数据的查询、挖掘和查询结果的质量评估上.本节介绍弱可用数据计 算的主要研究结果. (1) 弱可用数据上的查询处理与挖掘 针对具有实体统一性错误的数据,文献[158]研究了弱可用数据的查询处理问题,提出了在具有实体同一性 错误的数据上处理选择-投影-连接查询的算法. 文献[159]统一考虑实体识别和数据集成,提出了同时支持实体识别和数据集成的在线查询处理方法.文献 [160]提出了在具有实体同一性错误的数据上求解相似性连接的算法. 针对具有完整性数据的数据,文献[161]提出了基于改写关系代数表达式的查询处理方法.文献[162]实现了