www.kjdb.org 科技导报2014，32（34
）
大数据质量管理：大数据质量管理：问题与研究进展
王宏志
哈尔滨工业大学计算机科学与技术学院，哈尔滨150001
摘要
当前大数据在多个领域广泛存在，大数据的质量对其有效应用起着至关重要的作用，因而需要对大数据进行质量管理。
尽管数据质量管理方面已经有一些研究成果，但由于大数据具有规模大、速度快和多样性高的特点，现有的方法难以适用于大数据质量管理。本文针对错误发现、错误修复和劣质数据查询处理，综述了大数据质量管理的问题与挑战，认为大数据质量管理的挑战主要有计算困难、错误混杂和缺少知识3个方面。本文依据这3个方面的解决方法，对大数据质量管理目前的研究进展进行了综述，并展望了大数据质量管理未来的研究方向。关键词数据质量；大数据；数据清洗中图分类号
TP311.13
文献标志码
A
doi
10.3981/j.issn.1000-7857.2014.34.011
Big Data Quality Management:Problems and Progress
Department WANG Hongzhi
of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China
Abstract
quality management Big data techniques have wide applications. for big data are Since in demand. the quality Although of big data some plays theories a crucial and techniques role in these for data-centric data quality management applications, have data
big been proposed, due to the volume, variety and velocity of big data, current methods could hardly be applied to data management for
data data. management. management, This paper The progress and discusses identifies the of big data intractability, problems and quality management mixed challenges errors for in and error these the detection, three lack aspects of error knowledge repair is reviewed as and and three query open new processing problems challenges of dirty data in big for to future data research
quality are Keywords
proposed. data quality; big data; data cleaning
当前，大数据得到了广泛应用，对科学和产业产生了巨致成本极其巨大以致难以有效实施。
大影响。关于大数据的准确定义，科学界仍缺乏统一认识，从字面上理解，其最本质的特点在于数据量“大”，除此之外，生，也更易于产生不一致数据，2）由于高速性，数据的大量更新会导致过时数据迅速产
为人工错误检测与修复带来还包括了获取、管理及处理时的复杂性。大数据具有明显的困难。例如，大型强子对撞机实验设备中包含了15亿个传感时代特征，习惯上将其总结为4个“V ”：规模性（volume ），高速器，平均每秒收集超过4亿条实验数据，更新的数据将会导致性（velocity ），多样性（variety ）和价值稀疏性（value ）。由于大之前存储数据迅速过时，而在更新速度如此快的情况下，传数据的这些特征，使其有更大可能产生数据质量问题，即出统方法难以有效用新数据替换对应的旧数据。
现不一致、不精确、不完整、过时等问题或者描述同一实体的数据出现冲突（简称为实体不同一）等错误[1]。大数据有可能使得数据有更大的可能产生不一致和冲突。例如，3）大数据的多样性指的是数据来源和形式上的多样，在互联网这
产生数据质量问题，其具体原因如下：
上不同电子商务网站中获取到的描述同一商品的数据有很1）由于规模性，如果对其采用人工错误检测与修复，大数据获取、存储、传输和计算过程中可
大可能存在冲突。
能产生更多错误，将导
如果没有良好的数据质量，大数据将会对决策产生误
收稿日期：2014-09-25；修回日期：2014-11-06
基金项目：国家重点基础研究发展计划（973计划）项目（2012CB316200）；国家自然科学基金项目（61472099）作者简介：王宏志，副教授，研究方向为大数据管理、数据质量、复杂数据管理，电子信箱：[email protected]引用格式：王宏志. 大数据质量管理：问题与研究进展[J].科技导报, 2014, 32(34):78-84.
78
科技导报2014，32（34）www.kjdb.org
导，甚至产生有害的结果。根据估算，数据错误每年造成美推理系统。
国工业界经济损失约占GDP 的6%[2]。在医疗大数据应用方目前基于规则的方法难以直接应用于大数据。一方面，面，根据美国医疗委员会的统计，由于数据错误引起的医疗规则通常需要人来给出，而对于大数据而言，人难以了解数事故仅在美国每年就导致高达98000名患者丧生[3]。在电信据的全貌，故难以给出有效的规则，尽管有一些规则发现算大数据应用中，数据错误经常导致故障排除的延误、多余设备法提出[15~18]，但这些算法需要一个数据量较小且质量高的学租用和服务费收取错误，损害了企业信誉并失去很多用户[4]。习集合，在大数据上难以有效找到这样的集合。另一方面，在商业大数据的应用中，美国零售业每年仅因标价错误就损大数据高速的更新会使得规则迅速失效。
失25亿美元[5]。在金融大数据的应用中，2008年因数据质量问题导致的信用卡欺诈失察即造成48亿美元的损失[6]。统计据集合，3）基于主数据的错误发现。主数据是一个高质量的数
用于给多种应用提供企业核心业务实体的一个同步数据显示，50%以上的数据仓库项目由于数据质量问题而不一致的视图[19]，以主数据为基准，可以用来发现数据中的错得不取消或延迟[7]。
误。例如，文献[20]提出了信息相对完全理论来表述信息库由于大数据存在数据质量问题，并且会带来严重的后相对于主数据和用户查询的完整性，相对于主数据和用户查果，因此需要对大数据进行质量管理，从而确保基于大数据询，判定一个信息库完全与否。然而，当前主数据通常是人各种应用的有效实施。由于其重要性，研究人员围绕数据质工维护的一个小规模的数据集合，对于大数据，其部分数据量管理展开了研究，取得了一系列的研究成果，然而，大数据难以体现出其全貌，而维护大规模的主数据需要更高的成为数据质量管理带来了诸多挑战问题，进一步增加了数据质本；而大数据的高速性也需要主数据进行相应的快速更新，量管理的难度，同时也给数据质量管理带来了新的研究机从而导致了成本的进一步提高。遇。本文对数据质量管理的现有方法进行简要综述，分析大1.2
错误修复
数据为数据质量管理带来的挑战，同时对大数据质量管理研数据错误修复是指对存在错误的数据进行修改或者补究进行综述，并展望未来的研究方向。
充，提高其质量。根据数据错误修复思路的不同，数据修复可以分为基于规则的修复、真值发现和基于机器学习的修复。
1大数据质量管理的问题与挑战
质量管理包含错误发现、错误修复和容忍错误的近似查
使其满足给定规则的数据修复方法。文献1）基于规则的修复。基于规则的修复主要指修改数据
[21]提出了一种基询处理等不同方面，因此依照数据质量管理的不同方面，综于函数依赖的修复算法GREEDY_REPAIR，它采用启发式的
述这些方面的问题和现有解决方案，进而分析对大数据进行方法来修复字符串型数据，以修改破坏约束右部属性的取值质量管理时面临的挑战。来纠正不一致。启发式算法BATCHREPAIR [22]由上述方法扩1.1
错误发现
展得到，该方法针对函数依赖修复效果欠佳的问题，采用条
错误发现指的是发现存在质量问题的数据，根据方法的件函数依赖进行不一致数据的修复工作。文献[23]从图论方不同，当前的研究主要有实体识别、基于规则的错误发现和法入手修复不一致数据，提出了通过删除元组解决数据不一基于主数据的错误发现3类方法。
致的冲突图模型及相应方法，以删除元组为修复操作，将不1）实体识别。实体识别指的是发现描述同一现实世界
一致数据修复问题转化为图上最大独立集问题。文献[24]针中实体的不同数据。通过实体识别，可以有效地检测出实体对多种约束组合时出现的冲突现象，提出了多规则的修复框不同一、过时等错误。实体识别是数据质量方面研究最多的架，以及新的语义限制等价生成依赖，基于类间的偏序关系问题，研究人员已提出了多个实体识别算法[8]。尽管也有一
确定修复顺序。对于过时数据的修复问题，文献[25]将冲突些工作研究如何提高识别实体的效率[9]，但当前实体识别的消解问题转化为求解集合中最新且一致的值，并提出了基于计算复杂性仍然远超过线性，难以应用于大数据。
时间偏序和条件函数依赖的冲突消解方法。文献[20]讨论了数据库不完全时，如何扩展这个信息库以包括足够的信息来利用给定规则捕捉数据中的错误，2）基于规则的错误发现。基于规则的错误发现指的是
即找出违反规则的元组作为回答用户的查询。
错误元组。规则有多种形式，包括描述一致性的函数约束[10]、
条件函数约束[11]、条件包含约束[12]、描述时效性的时序约束[13]述实体属性的真实值实现。文献2）真值发现。对于实体不同一数据的修复通过发现描
[26]通过迭代方式计算源的和描述精确性的精确性约束等。文献[11]针对集中存储的关真实度和值的自信度，然后通过值的自信度寻找真值。文献系数据库，设计了基于SQL 语言的自动检测算法，用于查找违反条件函数约束和条件包含约束的数据元组。文献[13]在
[27]自信度推测出来。文献考虑了数据源之间的依赖关系，[28]提出了基于数据源之间的依赖关这种依赖关系需要从值
时间戳缺失的情况下，用完整性约束语言来描述同一实体不系的真值发现，使独立的数据源在投票过程中具有更高的权同信息值间的时序关系，给出了应用时序关系和拷贝关系推重。文献[29]给出了贝叶斯推理模型，其推理的真值必须满导实体最新信息的推理机制。文献[14]提供了一个模型来确足最大后验概率，但此算法的指数复杂度使其难以实际应定相对准确的数据，提出了精确性确定规则和chase 程序的
用，尽管有基于抽样的近似算法，但该算法的抽样对初始值
79
www.kjdb.org 科技导报2014，32（34
）
比较敏感，测试样本也必须具有很好的质量。
计算开展研究。Khalefa 等[46]第一次提出了不完整数据skyline 查询的概念，并提出替换算法、桶算法和skyline 算法。Alwan 从数据的完整部分学习相应的模型用于填充缺失的值。基3）机器学习。机器学习主要用于不完整性数据的修复，
等[47]提出对不完整数据进行填充值的skyline 查询方法，利用于机器学习技术的缺失值填充方法主要包括决策树[30]、贝叶
填充后的属性值进一步减少skyline 点个数，从而提高查询精斯网络[31]及神经网络[32]。文献[33]给出了“伪装缺失值”的检度。Bharuka 等[48]基于排序搜索算法（SRA ）解决不完整数据测与清洗方法。
skyline 比，可以渐进式输出查询问题，该方法与文献skyline 点，而不需要等全部数据点处理[46]中提出的ISkyline 算法相出，但如下两方面的问题使得这些方法难以应用于大数据。4）错误修复的难题。尽管当前有一些错误修复方法提
完毕才能一次性输出所有skyline 点。Miao 等[49,50]提出不完整第一，这些方法计算复杂度较高，有的问题甚至是NP （非确定数据k -Skyband 查询问题，并引入失效skyline 、阴影skyline 和图灵机多项式）难问题，难以应用于大数据。第二，由于大数厚度仓库的概念。k -Skyband 查询是指查询数据集中被k 个据中错误存在混杂的情况，这些方法在修复一种错误的同时其他数据项支配的数据项，一个数据项被支配的次数越少，可能会引入另外一种错误，例如基于机器学习的缺失值填充说明该数据项在各个属性上的总体取值情况越好。
可能会引入数据的不一致。1.3
劣质数据查询处理
查询问题。他们要解决的是根据用户过去的上下文偏好信Hadjali 等[51]提出了用户偏好存在丢失情况下的skyline
在一些数据中的错误难以有效修复的情况下，需要容忍息，查询当前上下文中存在偏好丢失情况下不被支配的skyline 数据中的错误，在存在错误的数据上进行查询处理，从存在元组。Arefin 等[52]考虑数据库中存在数据缺失情况下的skyline 质量问题的数据上获得高质量的查询结果。这方面的研究集合查询问题，他们提出了基于替换策略的RBSSQ 算法，可主要可以分为近似数据操作、不一致数据查询处理和有空值以有效解决数据库中元组丢失任意数量维度时的问题。数据的查询处理。
1）近似数据操作。当前主要的近似操作包括近似搜索
Markus 等[53]专门提出了针对偏好数据库查询中空缺值进行处理的方法，通过扩展偏好代数，提出了一种标准模型，能够在和近似连接操作。近似搜索操作在数据库中查找和给定查不破坏偏好支配关系传递性的情况下解决偏好查询问题。
询相似性大于给定阈值的结果，近似连接操作返回2个数据集合中相似性大于给定阈值的对。这两类操作均可在存在难题尚未得到有效解决，4）劣质数据计算中的难题。对大数据而言，一方面是这些计算的时间空间复杂有两方面的
错误的数据集合上得到近似计算结果。针对这两方面问题，性还较高，难以应用于大数据，另一方面在于当前的方法仅面有大量研究结果提出，文献[34]对相关研究结果进行了综述。向一种错误，难以在具有多种混合错误的数据上进行计算。致性查询问题。文献2）不一致数据查询处理。文献[36]首次提出一致性查询问题。文献
[35]综述数据修复和一
1.4
大数据为数据质量管理带来的挑战
根据上述讨论，大数据的特点为数据质量管理带来诸多[37]技术挑战，可归纳为：
修复。文献定义修复语义下的一致性查询，[38]提出EQUIP 系统计算合取查询的一致性解，
即查询需要满足所有的其将一致性查询的补问题归约到0-1规划问题，通过求解规而且增长速度快，1）计算困难。大数据规模巨大，因此大数据的质量管理需要时间和空间复达到PB 级甚至EB 级，
划方程去掉不满足一致性的解。此外，基于析取逻辑程序以
杂性为线性甚至亚线性的算法，也需要相应并行算法加快计
及稳定语义模型可以解任意合取查询的一致性回答问题[39]，算速度。特别是对于增长速度快的大数据需要在应用允许且一致性限制并不局限于主键约束，然而其复杂度为∏p
2。
的时间范围内实施数据质量管理。如何设计时空有效的大文献[40]、[41]研究了CERTAINTY (q ) 问题，即只考虑一致数据质量管理算法是第一个挑战性问题。当前数据质量管性约束为主键约束，修复类型为子集修复的情况。文献[42]理方法较少考虑在大规模数据上的可扩展性，其中一些问题提出一个包含一阶可表达的查询的更大的类，指出不在该类甚至被证明是不可计算问题或NP 完全问题，当前算法的时中的涉及到两个不同关系表进行连接操作的查询一定是不间和空间复杂度远超过线性，难以应用于TB 级以上的数据，可一阶改写的。文献[43]研究了满足函数依赖情况下基于主缺少面向大数据的线性或亚线性算法和并行算法。
键约束的一致性查询问题，首先认为数据库是部分一致的2）混杂错误。大数据的多样性导致其出现错误的根源
（满足函数依赖），基于此研究了CERTAINTY (q ，∑)问题，即在复杂，加之大数据在存储和通信过程中造成的错误，可能出满足函数依赖集合∑的情况下，∑是否是一阶可表达的，此问现多种类型错误混合并相互影响的情况。而错误的多个方题限制∑不带自连接。文献[44]、[45]研究了CERTAINTY (q ) 的面并非独立，会产生关联，例如精确性会影响一致性、实体同
变种：计数的复杂性问题，并证明了对于不带自连接的合取一性和时效性关联。检测与修复相互影响的多种错误是大查询q ，#CERTAINTY (q ) 是P 问题或是#P -完全问题。
数据质量管理的第二个挑战性问题。当前的数据质量管理3）不完整数据的查询处理。当前不完整数据的查询处
方法通常针对某个特定类型错误提出，缺少对错误之间关联理主要集中于skyline 查询。针对不完整数据的skyline 查询
的认知，也缺少多种错误混合发生时的错误检测与修复以及主要针对空缺属性上的支配关系以及基于新支配关系的高效
查询处理技术。
80
科技导报2014，32（34）www.kjdb.org
得到对数据的完整认识；3）知识缺少。大数据价值密度低，大数据规模巨大，仅从小部分数据难以
的强概率保证，从而确保了可扩展性。
来源多样，难以认
其包
知其全貌，从而难以全面认识大数据的语义。如何有效获取含了异常值检测和修复、Cleanix [65]是一个基于并行机群的大数据清洗系统，缺失值填充、实体识别以及冲突消充分的语义信息支持大数据质量管理是第三个挑战性问解等并行数据清洗模块。
题。当前大多数数据质量管理方法需要专家用户指定规则和相关参数，而自动错误检测修复和规则学习算法需要主数流清洗，2）数据清洗的线性亚线性算法。研究主要集中在数据
即通过扫描数据一次完成数据清洗，其主要应用背据或清洁的训练集。就大数据而言，一方面，聘请专家或维景是RFID 数据的清洗。
护主数据成本很高；另一方面，缺少自动选取有效训练集的文献[66]、[67]是早期RFID 数据清洗工作，提出了基于规算法。因此当前数据质量管理算法难以直接应用于大数据。
则的推理方法。这些方法直接作用于数据流上或者RFID 数据已经存储。使用规则的一个例子是将首先识别出的数据[67]2
大数据质量管理研究进展
或者读取次数最多的值[68]置为真值。文献[69]提出的方法利2.1
针对计算困难的解决方法
用参考对象（例如架子等）清洗RFID 数据流。文献[70]通过针对计算困难的问题，主要有两类解决方案，一是采取
考虑容量约束建立概率模型，提出了基于后验阅读率Metrop⁃并行化技术实施数据质量管理，二是为数据清洗设计线性亚线性的算法。
olis-Hasting 置。文献[71]采样来从模型中推理隐变量得到对象标签的位研究了用于对象检测的RFID 数据流清洗方法，
提出了移动环境下对象检测的概率模型，基于该模型设计了刚刚起步，1）并行数据质量管理。并行数据质量管理的研究当前研究工作主要集中在并行实体识别和并行相似性贝叶斯推理用于清洗RFID 数据。为了从运动的分布中抽样连接两个方面。
数据，设计了Gibss 采样器快速有效地清洗RFID 数据。
文献[72]提出了清洗有噪数据流的问题，其中噪声指的实体识别策略。为了简化多个相似性策略的实体识别配置，Dedoop [54]提供一个分块和匹配方法库，支持浏览器输入
是错误标记的训练样例，目标是精确地表示和去除误导的数Dadoop 据，从而提高基于清洁数据流得到的预测模型的精度。为了略自动转化为支持基于训练的机器学习方法，Hadoop 集群上并行执行的将特定的实体识别策MapReduce 任务。达到这个目的，其首先使用偏置方差分解得到用于数据流清Dedoop 洗的最大方差边际（MVM ），基于此概念，进一步提出了局部案[55,56]。文献支持无[57]冗基于余的MapReduce 多次分块平台设计了实体识别算法，
以及先进的负载平衡方和全局的过滤器框架结合局部（在单一数据块中）和全局（跨该方法首先通过属性值并行计算记录间的相似程度，而后基越多个连续数据块）过滤器来发现错误数据。于图聚类的方法进行实体识别从而输出得到最终结果。
2.2
针对混杂错误的解决方法
文献[58]基于MapReduce 框架设计了分类属性的填充算数据质量的多个方面相互关联。当前绝大多数研究人法，该算法利用基于概率的推理填充缺失值，该推理过程是员把数据质量的5个方面当作孤立的方向，已经有研究人员在一个基于属性相关性而建立起来的贝叶斯网络中进行。
开始复合类型错误的检测与修复，文献[73]探讨了信息修复和元组匹配的交互影响，基于条件函数约束和匹配约束提出连接算法，Vernica 这种方法也可以应用到基于等[59]提出了MapReduce 框架下的前缀过滤和PP Jaccard 相似性的相似了一个同时支持信息修复和实体识别的信息清洗框架。文连接。Metwally 和Faloutsos [60]提出了V-SMART-Join 算法，这献[74]提出了一种考虑数据时效性的冲突消解模型，该模型种算法在token 级别聚集相似性分数的贡献，从而计算相似利用时序偏序关系和时序约束来描述时效性，利用常数条件性函数。Afrati 等[61]研究了球散列技术和描点分析法来加速函数依赖描述一致性。该论文提出可以利用数据的时效顺MapReduce 上的相似性连接。Okcan 和Riedewald [62]设计了序辅助修复不一致数据，反之亦然，还提出同时考虑数据时Theta-Join 效性和一致性的统一数据消解算法。NADEEF [75]是一个端到文献[63]框架可以处理任意约束的连接。
研究了基于MapReduce 相似性字符串连接，支
端的数据清洗系统，提供编程界面允许用户输入各种异构的持多种基于集合的相似性函数和基于字母的相似性函数，该数据质量规则, 其中规则包括一致性约束和匹配规则，并提供方法扩展了现有基于划分的签名来支持基于集合的相似性核心算法检测错误并改正错误。函数，使用签名来生成key-value 对，为了减少通讯开销，这种2.3
针对知识缺少的解决方法
方法通过合并key-value 对来减少key-value 对数量。文献当前针对知识缺少的主要解决方法是引入用户的工[64]作。特别是通过众包技术进行数据质量管理。
据分布的划分，提出了ClusterJoin 将每条元组分布到其基于距离函数可能产生框架，这种方法将数据空间进行基于数目前在数据质量管理领域众包技术使用的最为广泛的连接结果的划分中，该方法为不同距离函数设计了一个强候问题是实体识别问题。Demartini 等[76]开发了一个人机交互系选元素过滤集合，从而每个元组仅需要被分不到少数划分中统，并增加了一个实体识别结果筛选概率框架。Wang 等[77]提从而保证正确性，为了解决高维数据中常见的偏斜问题，进出了一个以预算为基础的方法，假设没有足够的金钱标记所而设计了基于采样的动态负载平衡策略，其提供了划分规模
有记录，讨论如何利用有限的资金标识最有用的比较对。
81
www.kjdb.org 科技导报2014，32（34
）
Wang 法了解属性真实值的情况，因此在很多情况下需要容许错误明显不匹配的记录，等[77]开发了一种人机混合系统先用机器方法剔除一些将剩下的匹配对利用众包完成。随后又的存在，在存在错误的劣质数据上进行近似计算。现在已经提出了利用传递关系来减少可众包的记录对，并提出了一种
存在一些劣质数据查询处理算法，然而有两方面的工作做得可优化的标记排列顺序算法[78]。
还比较初步，有待进一步探索，一方面是当前劣质数据的计文献[79]提出了利用众包填充缺失值的策略，首先选择算对算法可扩展性考虑较少，难以应用到大数据，另一方面适用于众包填充的缺失值，继而根据属性类型选择不同缺失是当前劣质数据近似计算的研究成果主要集中在查询处理，
值填充方法。文献[80]将主动学习和众包相结合进行真值发计算的其他重要方面（如数据挖掘等）[85]
研究成果较少，存在
现，该方法采用迭代方法进行真值发现，在每一次迭代中通大量需要研究的问题。
过主动学习发现真值不确定性最高的属性进行众包，并基于返回结果进行投票，根据投票进一步判定真值不确定属性。
质量管理的重要问题之一在于缺乏对数据语义信息的充分4）支持数据质量管理的数据语义信息获取。目前数据
CrowdCleaner [81]是一个适用于Web 上多版本数据的清洗了解。因此支持数据质量管理的数据语义信息获取成为一系统，该系统使用基于众包技术来检测和修复传统数据清洗个亟待解决的问题。当前尽管有基于众包和互联网信息方方法难于解决的问题，并结合主动和被动众包方法纠正多版法用于获取知识以支持数据清洗，但这两方面的研究还刚刚本数据中的错误。
起步，仅覆盖了数据质量中实体统一性、完整性等少数几个维度和部分问题，有很多问题需要研究人员进一步研究和探索。
数据Lofi skyline 等[82,83]提出了采用众包平台数据库技术提高不完整
查询结果质量的方法。提出了精细的错误处理模型，在关注正确元组的同时，更加重点关注那些最有可能4结论
出错的元组。通过利用众包平台结合启发式技术，尽可能消由于具有规模大、多样性高和更新速度快的特点，大数
除错误值，集中处理最可能产生用户期待结果的元组。
据存在数据质量问题的可能性更大。数据质量对大数据应另外一种方法是通过提取互联网信息获取相应的语义用起着至关重要的作用，因此数据质量管理是大数据管理的信息。WebPut [84]是一个基于Web 信息的数据填充信息，该系核心步骤之一。与传统数据质量管理相比，大数据质量管理统扩展了信息提取方法用于形式化向Web 搜索查询以高效存在计算困难、错误混杂和缺少知识3方面的技术挑战亟待检索出缺失值。WebPub 使用了基于置信的方法自动为每个进一步研究。
缺失值选择最有效的填充查询，并设计了贪心的迭代算法确定数据填充顺序，并按顺序依次发布相应的查询。该论文还参考文献（References ）
提出一些优化策略用于在元组级别和数据库级别降低估计填充查询置信度的代价。
[1]Journal Li J Z, of Liu Computer X M. An Research important and aspect Development, of big data:2013, Data usability[J].3未来的工作
[2]1162.
50(6):1147-随着大数据的广泛应用，数据质量管理将越来越重要，
success Eckerson through W W. Data a commitment quality and to the bottom line:Achieving business 而面向大数据质量管理的研究刚刚起步，还存在诸多亟待解[3]The Data Warehousing Institute, 2000:high 12-20.
quality data[R].Renton, WA:决的问题。
[4][M].Institute of Medicine. To err is human:Building a safer health system Bohannon Washington:工作涉及到两种不同种类数据质量问题的协同处理，1）数据质量多维度相互影响的认知。当前尽管有一些
然而，tive SIGMOD heuristic P, Fan The International for W repairing F, National Flaster Academies Press, 1999.
Conference constraints M, et al. A cost-based model and effec⁃on Management by value modification[C].of Data, Baltimore, ACM 尚无综合考虑数据质量多个维度的方法提出，缺乏对这种相互影响的深入认识，而对数据质量问题的全面解决需要对这[5]Maryland, English L. June Plain 14-16, English 2005.
on data quality:Information 种相互影响进行定量分析，而且需要在统一逻辑框架下对不同数据质量问题的统一表达，这方面现在处于空白状态，有[6]ment:待深入研究。
[7][EB/OL].Ben W, The Schulz next frontier[J].DM Review Magazine, 2000.
quality manage⁃Gartner. 2010-03-19, S. Credit [2014-09-25].card statistics, http://www.creditcards.com.
industry facts, debt statistics will Gartner says more than 50percent of data warehouse projects
测与修复算法普遍计算复杂性超过线性，2）高效数据错误检测与修复算法设计。当前的错误检
而且缺少有效的并
OL].have 2005-02-24, limited acceptance [2014-09-25].or will http://www.gartner.com/newsroom/id/be failures through 2007[EB/行算法，难以适用于大数据，而仅有的线性复杂性算法和并[8]492112.
Elmagarmid 行算法只集中在相似性连接、实体识别、RFID 错误检测等几tion:A K, Ipeirotis P G, Verykios V S. Duplicate 个问题，对于大多数错误检测与修复的问题尚无适用于大数ing, A survey[J].IEEE Transactions on Knowledge and Data record Engineer⁃detec⁃据的高效算法提出，给研究人员很大的进一步研究的空间。
[9]Christen 2007, and P. 19(1):A survey 1-16.
of indexing techniques for 多情况下，3）劣质大数据近似计算理论与算法。对于大数据，错误难以完全修复，而且修复过程中经常存在无
在很
[10]neering, deduplication[J].IEEE Transactions on Knowledge scalable and record Data linkage Engi⁃Rahm E, 2012, Do H 24(9):H. Data 1537-1555.
cleaning:Problems and current approaches[J].
82
科技导报2014，32（34）www.kjdb.org
Bulletin Engineering of the Institute tional [11]Fan cies W [31]
Oregon, Conference on Knowledge Discovery and Data Mining, Portland, Mayfield August base for F, capturing Geerts Bulletin, of Electrical and Electronics Engineers Data
F, 2000, 23(4):3-13.
data Jia inconsistencies[J].X B, et al. Conditional ACM Transactions functional dependen⁃on Data⁃for C, Neville 2-4, 1996.
J, Prabhakar S. ERACER:A database approach [12]Bravo Systems, tional statistical The L, Fan W 2008, F, Ma 33(2):S. 1-48.
Extending dependencies with conditions[C].[32]USA, Conference inference on Management and data cleaning[C].of Data, ACM Indianapolis, SIGMOD Interna⁃Setiawan June [13]sity Fan of 33rd Vienna, International Austria, Conference September 23-27, on Very Large Data Bases, Univer⁃prediction N 6-10, Indiana, A, Venkatachalam 2010.
P, Hani A F M. Missing attribute value The [33]
Biomedical based Hua Engineering on artificial and Informatics, neural network 2008, and 1:rough set theory[J].[14]of 30th W F, ACM Geerts F, Wijsen J. Determining 2007.
the currency of data[C].Cao Database [C].butes[C].Y, Fan Systems SIGMOD-SIGACT-SIGART W (PODS),Athens, Greece, Symposium June 12-16, on 2011.
Principles Discovery The M, Pei 13th J. ACM Cleaning SIGKDD disguised missing data:A 306-310.
heuristic approach [15]York, 2013F, International Yu W Y. Determining Conference on the Management relative accuracy of attri⁃Chiang USA, [34]2007.
and Data Mining, San International Jose, California, Conference USA, August on Knowledge 12-15, Lin [16]ings F, Miller June 23-28, R J. Discovering 2013.
of Data, New data quality Fan of [35]nese X Journal M, Wang of Computers, W. Set and string similarity queries:A survey[J].Chi⁃dependencies[J].W the F, VLDB Geerts Endowment, rules[J].The Proceed⁃F, Li J Z, et 2008, al. Discovering 1(1):1166-1177.
conditional functional [36]California:Leopoldo B. Morgan Database &Claypool, repairing 2011, 34(10):2011.
and consistent 1853-1862.
query answering[M].[17]Chu ing, 2011, IEEE Transactions on Knowledge and Data Engineer⁃straints[M]//IntegrityBry F. Query answering [18]
ceedings X, Ilyas 23(5):I F, 683-698.
Papotti P. Discovering denial constraints[J].The Pro⁃Bauckmann of the [37]
York:and Internal in information Control in systems Information with integrity Systems. con⁃Arenas Springer, clusion J, Abedjan VLDB Endowment, Z, Leser U, 2013, et al. 6(13):Discovering 1498-1509.
conditional sistent M, Bertossi 1997:L, 113-130.
New Chomicki J. Consistent query answers in incon⁃Information dependencies[C].Symposium databases[C].Eighteenth ACM SIGACT-SIGMOD-SIGART [19]November and Knowledge The Management, 21st ACM International Maui, Hawaii, Conference in⁃October on Loshin [38]vania, Kolaitis May on Principles of Database Systems, Philadelphia, Pennsyl⁃databases P with G, 31-June Pema 2, binary E, 1999.
integer Tan W programming[J].C. Efficient querying The Proceedings of inconsistent of the [20]2008.
D. Master 2, 2012.
29-data management[M].San Francisco:Morgan Kaufmann, Fan actions W F, Geerts F. Relative information completeness[J].ACM Trans⁃[39]BarcelóVLDB Endowment, [21]
Bohannon on [M]//PracticalP, Bertossi L. 2013, 6(6):397-408.
tive SIGMOD heuristic P, Database Fan Systems, 2010, 35(4):27-35.
for repairing W, Flaster constraints M, et al. A cost-based model and effec⁃[40]2003:Fuxman 208-222.
Aspects Logic of Declarative programs for Languages. querying inconsistent New York:databases Springer, inconsistent A, Fazli [22]Maryland, International Cong USA, June 14-16, Conference on Management by value modification[C].of Data, Baltimore, ACM and accuracy[C].G, Fan W, The Geerts 33rd F, et 2005.
al. Improving data quality:Consistency [41]Management databases[C].E, Miller ACM R J. SIGMOD Conquer:International Efficient management of Fuxman tabases[J].A, Journal Miller of Data, R of J. Baltimore, Maryland, USA, June 14-16, Conference 2005. on Computer First-order and query System rewriting Sciences, for inconsistent 2007, 73(4):da⁃[23]Arenas Bases, University International Conference on Very Large Data sistent [42]Wijsen 610-635.
ization J. [24]434.
databases[J].M, Bertossi of L Vienna, Austria, September 23-27, 2007.
Theoretical E, Chomicki Computer J, et al. Science, Scalar aggregation 2003, 296(3):in incon⁃405-Geerts framework[J].F, Mecca G, Papotti P, et al. The LLUNATIC data-cleaning [43]Database of Consistent tractable queries[C].query answering The 12th under International primary keys:A character⁃Greco consistent S, Pijcke Theory, F, St Wijsen Petersburg, J, et Russia, March 23-25, 2009.
Conference on [25]625-636.
The Proceedings of the VLDB Endowment, 2013, 6(9):Fan tency W F, Geerts F, Tang N, et [44]Maslowski (5):32-65.
databases[J].Proceedings al. Certain of the query VLDB answering Endowment, in partially 2014, 7tive [26]on Galland Data for Engineering, conflict resolution[C].al. 29th Inferring IEEE data International currency and Conference consis⁃from A, Abiteboul Brisbane, S, Marian April A, 8-12, et al. 2013.
Corroborating information [45]Database queries D, with Wijsen self-J. joins[C].Counting The database repairs that satisfy conjunc⁃Maslowski Theory, International D, Wijsen Athens, J. Greece, 17th International Conference on On March 24-28, 2014.
[27]Web disagreeing Dong Search and views[C].Data Mining, The New third York, ACM USA, International Conference on The [46]25, Khalefa 2011.
Workshop on Logic counting in Databases, database San repairs[C].Miniato, The March 4th for [28]dowment-PVLDB, role X L, of Berti-Equille source dependence[J].L, Srivastava The D. Proceedings Integrating February of conflicting 3-6, 2010. the VLDB data:En⁃Dong detection X L, [47]Data incomplete M E, Mokbel data[C].M 2008F, Levandoski J J. Skyline query processing Alwan Engineering plete A A, Ibrahim (ICDE'08), Cancun, IEEE 24th April International 7-12, 2008.
Conference on [29]ment-PVLDB, in Berti-Equille 2009, 2(1):a dynamic world[J].L, Srivastava 550-561.
The Proceedings D. Truth discovery of the VLDB and copying Endow⁃Zhao discovering B, Rubinstein 2009, B 2(1):I P, 562-573.
Gemmell J, et al. A bayesian [48]
on multidmensional H, database[C].Udzir N I, et The al. 3rd Skyline International queries over incom⁃Bharuka Computing ceedings R, Kumar and Informatics, P S. Finding Bandung, skylines June for 8-9, 2011.
Conference [30]
Proceedings truth Lakshminarayan of the from VLDB conflicting Endowment, sources 2012, for data integration[J].approach The to Gold ing data using machine K, Harp learning S A, Goldman techniques[C].R, et 5(6):al. 550-561.
The Imputation Second of Interna⁃
miss⁃[49]
109-117.
Coast, of the Queensland:Twenty-Fourth Australian Australasian incomplete data[C]//Pro⁃Computer Database Society, Conference. 2013, 137:Miao X, Gao Y, Chen L, et al. On efficient k-skyband query process⁃
83
www.kjdb.org 科技导报2014，32（34
）
ing tions. over incomplete data[M]//DatabaseSystems for for [50]Gao Large rfid skyline, Y, Berlin Miao Heidelberg:X, Cui H, Springer, et al. 2013:424-439.
Advanced Applica⁃
[68]Jeffery Data data Bases, analytics[C].Seoul, Korea, The 32nd September International Conference on Very streams[C].S, Garofalakis [51]
Systems and Hadjali with group-Applications, by skyline queries Processing on incomplete k-skyband, data[J].constrained Expert Bases, The 32nd M, Franklin M. Adaptive 12-15, cleaning 2006.
for rfid data incomplete A, [69]of preferences[C]//ProceedingPivert O, Prade 2014, H. Possibilistic 41(10):4959-4974.
of contextual skylines with streams Tran T, Seoul, International Conference on Very Large Data Sutton Korea, C, Cocci September R, et 12-15, al. Probabilistic 2006.
inference over rfid [52]
of Soft Electrical Computing and Electronics and Pattern Recognition. 2010New International York, USA:Conference Institute [70]on in mobile environments[C].The 25th International Conference Chen Data missing Arefin M cy H, Engineering, Ku W, Wang March H, et 29-April al. Leveraging 2, 2009.
spatio-temporal redundan⁃Computer values[C]//ProceedingS, Morimoto Y. Skyline Engineers, sets 2010:queries 57-62.
from databases with [71]
Zhao on for Management rfid data of cleansing[C].Data, Indianapolis, ACM SIGMOD Indiana, International USA, Conference [53]and Markus Electronics Theory Engineers, and Applications. of 22nd International Conference on 2012:Chengdu:Institute of Electrical ing[C].Z, preference E, Knowledge The Ng W. 21st A model-based ACM International approach Conference for RFID on data June Information stream 6-10, cleans⁃2010. and [54]Intelligence, database Patrick R, Florian W, 24-29.
et al. Handling of NULL values in Kolb [72]2012.
Management, Maui, Hawaii, October 29-November 2, Zhu The X [55]The L, Thor Montpellier, queries[C].20th European Conference on Artificial A, France, August 27-31, 2012.
Kolb Proceedings Rahm of the E, VLDB et al. Endowment, Efficient deduplication 2012, 5(12):with hadoop[J].resolution[C].L, Thor A, [73]December IEEE Q, Zhang International P, Wu Conference X D, et al. on Cleansing Data Mining, noisy Cancún,data streams[C].México,Fan and W F, 15-19, Li J Z, 2008.
Ma S, et al. Interaction between record matching [56]
Washington International Rahm E. Load 1878-1881. Council balancing for Open for MapReduce-based entity Kolb lution L, Thor D A, C, Rahm April 1-5, and Distance Education, E. Block-based 2012.
[74]Management data repairing[C].ACM SIGMOD International Conference on Fan on tency W F, Geerts of Data, F, Tang Athens, N, et Greece, al. June 12-16, 2011.
[57]dom, Information with MapReduce[C].load balancing for entity reso⁃and Knowledge The 20th ACM International Conference Huo October [75]ence Ebaid on for Data conflict resolution[C].The Inferring 29th IEEE data currency International and Confer⁃consis⁃data A, Elmagarmid Engineering, A K, Brisbane, Llyas I, April et al. 8-12, NADEEF:2013.
A [58]based R, Wang 24-28, H Z, 2011.
Management, Glasgow, United King⁃Zhu R, et Jin data L, on al. Entity identification in big data Wang MapReduce[J].H EIBM, 2013, 50(S2):20-35.
[76]
2013, cleaning system[J].The Proceedings of the generalized Demartini 6(12):VLDB Endowment, probabilistic G, 1218-1221.
Difallah D [59]opment, based on Map-Reduce[J].Z, Huang S B, Journal et al. Missing value imputation in big Vernica 2013, entity using R, Carey 50(Sl):of Computer Research and Devel⁃M 312-321.
J, Li C. [77]France, linking[C].reasoning The and E, Cudr'e-Mauroux crowdsourcing techniques P. ZenCrowd:for large-Leveraging scale Wang [60]Management mapreduce[C].Metwally of Data, Indianapolis, ACM SIGMOD Efficient parallel set-similarity joins Indiana, International Conference on resolution[J].J, April 21st World Wide Web Conference, Lyon, Kraska 16-20, T, Franklin 2012.
M work [78]1483-1494.
The Proceedings J, of et the al. VLDB CrowdER:Endowment, Crowdsourcing 2012, entity 5(11):Wang [61]Proceedings for A, all-Faloutsos pair similarity C. V-smart-join:joins of multisets A USA, scalable June and mapreduce 6-10, 2010. vectors[J].frame⁃The Afrati crowdsourced J N, Li duce[C].F N, of the VLDB Endowment, 2012:213-300.
[79]ta, joins[C].G L, Kraska International T, et al. Leveraging transitive relations for Ye New [62]Washington International Sarma A D, Council Menestrina for D, Open et al. Fuzzy joins using mapre⁃Okcan ACM A, Riedewald D C, April M. 1-5, and Distance Education, Processing 2012.
theta-joins [80]Lecture C, Wang York, Conference on Management of Da⁃H USA, Z. Capture June 22-27, missing 2013.
values based on crowdsourcing[J].Ye [63]
Athens, SIGMOD International Conference on Management using mapreduce[C].Deng [81]
ing[J].C, Wang Notes in Computer Science, 2014, 8491:783-792.
Tong for D, Greece, June 12-16, 2011.
of Data, for Y Lecture H X, Cao Notes Z, Gao C C, in H, et al. Truth discovery based on crowdsourc⁃Zhang Computer C J, Science, et al. CrowdCleaner:2014, 8485:453-458.
Conference scalable Li G string L, Hao similarity S, et al. joins[C].MassJoin:A mapreduce-based method 30th multi-version [64]2014.
on Data Engineering, Moscow, 2014Russia, IEEE March 30th International 31-April 4, [82]March International data Conference on the web Data cleaning on via crowdsourcing[C].2014IEEE Lofi framework Sarma A D, using He MapReduce[J].Y Y, Chaudhuri The S. Proceedings ClusterJoin:of the A similarity joins ta-error C, 31-April El Maarry 4, K, 2014.
Data Engineering, Moscow, Russia, Balke W T. Skyline [65]Wang ment, 2014, VLDB Endow⁃[83]Berlin:models for focused queries over incomplete da⁃Lofi 23rd H Z, Li 7(12):M D, 1059-1070.
Bu Y Y, et al. databases[C].C, Springer, El Maarry 2013:298-312.
crowd-sourcing[M]//ConceptualModeling. [66]
Management, ACM International A big data cleaning parfait[C].The BornhövdShanghai, Conference on Information and Knowledge [84]base The 16th K, Balke International W T. Skyline Conference queries on in crowd-enabled Li tion C, Lin T, Haller Nov S, 3-7, et al. 2014:Integrating 10-23.
automatic data acquisi⁃ture[J].with [85]
Chen imputation[J].Z Technology, X, Sharaf World M Genoa, A, Wide Sitbon Italy, March 18-22, 2013.
Extending Data⁃Web, L, et 2014, al. A 17(5):web-873-897based approach .
to data cation Y C, Li J Z, Luo J Z. ITCI:An information theory based classifi⁃[67]
1188.
The business Proceedings processes of the experiences VLDB Endowment, with sap's auto-id 2004, 30:infrastruc⁃1182-Rao J, Doraiswamy S, Thakkar H, et al. A deferred cleansing method
Science, algorithm 2014, 8485:for incomplete 167-179.
data[J].Lecture Notes in Computer （责任编辑王媛媛）
84
www.kjdb.org 科技导报2014，32（34
）
大数据质量管理：大数据质量管理：问题与研究进展
王宏志
哈尔滨工业大学计算机科学与技术学院，哈尔滨150001
摘要
当前大数据在多个领域广泛存在，大数据的质量对其有效应用起着至关重要的作用，因而需要对大数据进行质量管理。
尽管数据质量管理方面已经有一些研究成果，但由于大数据具有规模大、速度快和多样性高的特点，现有的方法难以适用于大数据质量管理。本文针对错误发现、错误修复和劣质数据查询处理，综述了大数据质量管理的问题与挑战，认为大数据质量管理的挑战主要有计算困难、错误混杂和缺少知识3个方面。本文依据这3个方面的解决方法，对大数据质量管理目前的研究进展进行了综述，并展望了大数据质量管理未来的研究方向。关键词数据质量；大数据；数据清洗中图分类号
TP311.13
文献标志码
A
doi
10.3981/j.issn.1000-7857.2014.34.011
Big Data Quality Management:Problems and Progress
Department WANG Hongzhi
of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China
Abstract
quality management Big data techniques have wide applications. for big data are Since in demand. the quality Although of big data some plays theories a crucial and techniques role in these for data-centric data quality management applications, have data
big been proposed, due to the volume, variety and velocity of big data, current methods could hardly be applied to data management for
data data. management. management, This paper The progress and discusses identifies the of big data intractability, problems and quality management mixed challenges errors for in and error these the detection, three lack aspects of error knowledge repair is reviewed as and and three query open new processing problems challenges of dirty data in big for to future data research
quality are Keywords
proposed. data quality; big data; data cleaning
当前，大数据得到了广泛应用，对科学和产业产生了巨致成本极其巨大以致难以有效实施。
大影响。关于大数据的准确定义，科学界仍缺乏统一认识，从字面上理解，其最本质的特点在于数据量“大”，除此之外，生，也更易于产生不一致数据，2）由于高速性，数据的大量更新会导致过时数据迅速产
为人工错误检测与修复带来还包括了获取、管理及处理时的复杂性。大数据具有明显的困难。例如，大型强子对撞机实验设备中包含了15亿个传感时代特征，习惯上将其总结为4个“V ”：规模性（volume ），高速器，平均每秒收集超过4亿条实验数据，更新的数据将会导致性（velocity ），多样性（variety ）和价值稀疏性（value ）。由于大之前存储数据迅速过时，而在更新速度如此快的情况下，传数据的这些特征，使其有更大可能产生数据质量问题，即出统方法难以有效用新数据替换对应的旧数据。
现不一致、不精确、不完整、过时等问题或者描述同一实体的数据出现冲突（简称为实体不同一）等错误[1]。大数据有可能使得数据有更大的可能产生不一致和冲突。例如，3）大数据的多样性指的是数据来源和形式上的多样，在互联网这
产生数据质量问题，其具体原因如下：
上不同电子商务网站中获取到的描述同一商品的数据有很1）由于规模性，如果对其采用人工错误检测与修复，大数据获取、存储、传输和计算过程中可
大可能存在冲突。
能产生更多错误，将导
如果没有良好的数据质量，大数据将会对决策产生误
收稿日期：2014-09-25；修回日期：2014-11-06
基金项目：国家重点基础研究发展计划（973计划）项目（2012CB316200）；国家自然科学基金项目（61472099）作者简介：王宏志，副教授，研究方向为大数据管理、数据质量、复杂数据管理，电子信箱：[email protected]引用格式：王宏志. 大数据质量管理：问题与研究进展[J].科技导报, 2014, 32(34):78-84.
78
科技导报2014，32（34）www.kjdb.org
导，甚至产生有害的结果。根据估算，数据错误每年造成美推理系统。
国工业界经济损失约占GDP 的6%[2]。在医疗大数据应用方目前基于规则的方法难以直接应用于大数据。一方面，面，根据美国医疗委员会的统计，由于数据错误引起的医疗规则通常需要人来给出，而对于大数据而言，人难以了解数事故仅在美国每年就导致高达98000名患者丧生[3]。在电信据的全貌，故难以给出有效的规则，尽管有一些规则发现算大数据应用中，数据错误经常导致故障排除的延误、多余设备法提出[15~18]，但这些算法需要一个数据量较小且质量高的学租用和服务费收取错误，损害了企业信誉并失去很多用户[4]。习集合，在大数据上难以有效找到这样的集合。另一方面，在商业大数据的应用中，美国零售业每年仅因标价错误就损大数据高速的更新会使得规则迅速失效。
失25亿美元[5]。在金融大数据的应用中，2008年因数据质量问题导致的信用卡欺诈失察即造成48亿美元的损失[6]。统计据集合，3）基于主数据的错误发现。主数据是一个高质量的数
用于给多种应用提供企业核心业务实体的一个同步数据显示，50%以上的数据仓库项目由于数据质量问题而不一致的视图[19]，以主数据为基准，可以用来发现数据中的错得不取消或延迟[7]。
误。例如，文献[20]提出了信息相对完全理论来表述信息库由于大数据存在数据质量问题，并且会带来严重的后相对于主数据和用户查询的完整性，相对于主数据和用户查果，因此需要对大数据进行质量管理，从而确保基于大数据询，判定一个信息库完全与否。然而，当前主数据通常是人各种应用的有效实施。由于其重要性，研究人员围绕数据质工维护的一个小规模的数据集合，对于大数据，其部分数据量管理展开了研究，取得了一系列的研究成果，然而，大数据难以体现出其全貌，而维护大规模的主数据需要更高的成为数据质量管理带来了诸多挑战问题，进一步增加了数据质本；而大数据的高速性也需要主数据进行相应的快速更新，量管理的难度，同时也给数据质量管理带来了新的研究机从而导致了成本的进一步提高。遇。本文对数据质量管理的现有方法进行简要综述，分析大1.2
错误修复
数据为数据质量管理带来的挑战，同时对大数据质量管理研数据错误修复是指对存在错误的数据进行修改或者补究进行综述，并展望未来的研究方向。
充，提高其质量。根据数据错误修复思路的不同，数据修复可以分为基于规则的修复、真值发现和基于机器学习的修复。
1大数据质量管理的问题与挑战
质量管理包含错误发现、错误修复和容忍错误的近似查
使其满足给定规则的数据修复方法。文献1）基于规则的修复。基于规则的修复主要指修改数据
[21]提出了一种基询处理等不同方面，因此依照数据质量管理的不同方面，综于函数依赖的修复算法GREEDY_REPAIR，它采用启发式的
述这些方面的问题和现有解决方案，进而分析对大数据进行方法来修复字符串型数据，以修改破坏约束右部属性的取值质量管理时面临的挑战。来纠正不一致。启发式算法BATCHREPAIR [22]由上述方法扩1.1
错误发现
展得到，该方法针对函数依赖修复效果欠佳的问题，采用条
错误发现指的是发现存在质量问题的数据，根据方法的件函数依赖进行不一致数据的修复工作。文献[23]从图论方不同，当前的研究主要有实体识别、基于规则的错误发现和法入手修复不一致数据，提出了通过删除元组解决数据不一基于主数据的错误发现3类方法。
致的冲突图模型及相应方法，以删除元组为修复操作，将不1）实体识别。实体识别指的是发现描述同一现实世界
一致数据修复问题转化为图上最大独立集问题。文献[24]针中实体的不同数据。通过实体识别，可以有效地检测出实体对多种约束组合时出现的冲突现象，提出了多规则的修复框不同一、过时等错误。实体识别是数据质量方面研究最多的架，以及新的语义限制等价生成依赖，基于类间的偏序关系问题，研究人员已提出了多个实体识别算法[8]。尽管也有一
确定修复顺序。对于过时数据的修复问题，文献[25]将冲突些工作研究如何提高识别实体的效率[9]，但当前实体识别的消解问题转化为求解集合中最新且一致的值，并提出了基于计算复杂性仍然远超过线性，难以应用于大数据。
时间偏序和条件函数依赖的冲突消解方法。文献[20]讨论了数据库不完全时，如何扩展这个信息库以包括足够的信息来利用给定规则捕捉数据中的错误，2）基于规则的错误发现。基于规则的错误发现指的是
即找出违反规则的元组作为回答用户的查询。
错误元组。规则有多种形式，包括描述一致性的函数约束[10]、
条件函数约束[11]、条件包含约束[12]、描述时效性的时序约束[13]述实体属性的真实值实现。文献2）真值发现。对于实体不同一数据的修复通过发现描
[26]通过迭代方式计算源的和描述精确性的精确性约束等。文献[11]针对集中存储的关真实度和值的自信度，然后通过值的自信度寻找真值。文献系数据库，设计了基于SQL 语言的自动检测算法，用于查找违反条件函数约束和条件包含约束的数据元组。文献[13]在
[27]自信度推测出来。文献考虑了数据源之间的依赖关系，[28]提出了基于数据源之间的依赖关这种依赖关系需要从值
时间戳缺失的情况下，用完整性约束语言来描述同一实体不系的真值发现，使独立的数据源在投票过程中具有更高的权同信息值间的时序关系，给出了应用时序关系和拷贝关系推重。文献[29]给出了贝叶斯推理模型，其推理的真值必须满导实体最新信息的推理机制。文献[14]提供了一个模型来确足最大后验概率，但此算法的指数复杂度使其难以实际应定相对准确的数据，提出了精确性确定规则和chase 程序的
用，尽管有基于抽样的近似算法，但该算法的抽样对初始值
79
www.kjdb.org 科技导报2014，32（34
）
比较敏感，测试样本也必须具有很好的质量。
计算开展研究。Khalefa 等[46]第一次提出了不完整数据skyline 查询的概念，并提出替换算法、桶算法和skyline 算法。Alwan 从数据的完整部分学习相应的模型用于填充缺失的值。基3）机器学习。机器学习主要用于不完整性数据的修复，
等[47]提出对不完整数据进行填充值的skyline 查询方法，利用于机器学习技术的缺失值填充方法主要包括决策树[30]、贝叶
填充后的属性值进一步减少skyline 点个数，从而提高查询精斯网络[31]及神经网络[32]。文献[33]给出了“伪装缺失值”的检度。Bharuka 等[48]基于排序搜索算法（SRA ）解决不完整数据测与清洗方法。
skyline 比，可以渐进式输出查询问题，该方法与文献skyline 点，而不需要等全部数据点处理[46]中提出的ISkyline 算法相出，但如下两方面的问题使得这些方法难以应用于大数据。4）错误修复的难题。尽管当前有一些错误修复方法提
完毕才能一次性输出所有skyline 点。Miao 等[49,50]提出不完整第一，这些方法计算复杂度较高，有的问题甚至是NP （非确定数据k -Skyband 查询问题，并引入失效skyline 、阴影skyline 和图灵机多项式）难问题，难以应用于大数据。第二，由于大数厚度仓库的概念。k -Skyband 查询是指查询数据集中被k 个据中错误存在混杂的情况，这些方法在修复一种错误的同时其他数据项支配的数据项，一个数据项被支配的次数越少，可能会引入另外一种错误，例如基于机器学习的缺失值填充说明该数据项在各个属性上的总体取值情况越好。
可能会引入数据的不一致。1.3
劣质数据查询处理
查询问题。他们要解决的是根据用户过去的上下文偏好信Hadjali 等[51]提出了用户偏好存在丢失情况下的skyline
在一些数据中的错误难以有效修复的情况下，需要容忍息，查询当前上下文中存在偏好丢失情况下不被支配的skyline 数据中的错误，在存在错误的数据上进行查询处理，从存在元组。Arefin 等[52]考虑数据库中存在数据缺失情况下的skyline 质量问题的数据上获得高质量的查询结果。这方面的研究集合查询问题，他们提出了基于替换策略的RBSSQ 算法，可主要可以分为近似数据操作、不一致数据查询处理和有空值以有效解决数据库中元组丢失任意数量维度时的问题。数据的查询处理。
1）近似数据操作。当前主要的近似操作包括近似搜索
Markus 等[53]专门提出了针对偏好数据库查询中空缺值进行处理的方法，通过扩展偏好代数，提出了一种标准模型，能够在和近似连接操作。近似搜索操作在数据库中查找和给定查不破坏偏好支配关系传递性的情况下解决偏好查询问题。
询相似性大于给定阈值的结果，近似连接操作返回2个数据集合中相似性大于给定阈值的对。这两类操作均可在存在难题尚未得到有效解决，4）劣质数据计算中的难题。对大数据而言，一方面是这些计算的时间空间复杂有两方面的
错误的数据集合上得到近似计算结果。针对这两方面问题，性还较高，难以应用于大数据，另一方面在于当前的方法仅面有大量研究结果提出，文献[34]对相关研究结果进行了综述。向一种错误，难以在具有多种混合错误的数据上进行计算。致性查询问题。文献2）不一致数据查询处理。文献[36]首次提出一致性查询问题。文献
[35]综述数据修复和一
1.4
大数据为数据质量管理带来的挑战
根据上述讨论，大数据的特点为数据质量管理带来诸多[37]技术挑战，可归纳为：
修复。文献定义修复语义下的一致性查询，[38]提出EQUIP 系统计算合取查询的一致性解，
即查询需要满足所有的其将一致性查询的补问题归约到0-1规划问题，通过求解规而且增长速度快，1）计算困难。大数据规模巨大，因此大数据的质量管理需要时间和空间复达到PB 级甚至EB 级，
划方程去掉不满足一致性的解。此外，基于析取逻辑程序以
杂性为线性甚至亚线性的算法，也需要相应并行算法加快计
及稳定语义模型可以解任意合取查询的一致性回答问题[39]，算速度。特别是对于增长速度快的大数据需要在应用允许且一致性限制并不局限于主键约束，然而其复杂度为∏p
2。
的时间范围内实施数据质量管理。如何设计时空有效的大文献[40]、[41]研究了CERTAINTY (q ) 问题，即只考虑一致数据质量管理算法是第一个挑战性问题。当前数据质量管性约束为主键约束，修复类型为子集修复的情况。文献[42]理方法较少考虑在大规模数据上的可扩展性，其中一些问题提出一个包含一阶可表达的查询的更大的类，指出不在该类甚至被证明是不可计算问题或NP 完全问题，当前算法的时中的涉及到两个不同关系表进行连接操作的查询一定是不间和空间复杂度远超过线性，难以应用于TB 级以上的数据，可一阶改写的。文献[43]研究了满足函数依赖情况下基于主缺少面向大数据的线性或亚线性算法和并行算法。
键约束的一致性查询问题，首先认为数据库是部分一致的2）混杂错误。大数据的多样性导致其出现错误的根源
（满足函数依赖），基于此研究了CERTAINTY (q ，∑)问题，即在复杂，加之大数据在存储和通信过程中造成的错误，可能出满足函数依赖集合∑的情况下，∑是否是一阶可表达的，此问现多种类型错误混合并相互影响的情况。而错误的多个方题限制∑不带自连接。文献[44]、[45]研究了CERTAINTY (q ) 的面并非独立，会产生关联，例如精确性会影响一致性、实体同
变种：计数的复杂性问题，并证明了对于不带自连接的合取一性和时效性关联。检测与修复相互影响的多种错误是大查询q ，#CERTAINTY (q ) 是P 问题或是#P -完全问题。
数据质量管理的第二个挑战性问题。当前的数据质量管理3）不完整数据的查询处理。当前不完整数据的查询处
方法通常针对某个特定类型错误提出，缺少对错误之间关联理主要集中于skyline 查询。针对不完整数据的skyline 查询
的认知，也缺少多种错误混合发生时的错误检测与修复以及主要针对空缺属性上的支配关系以及基于新支配关系的高效
查询处理技术。
80
科技导报2014，32（34）www.kjdb.org
得到对数据的完整认识；3）知识缺少。大数据价值密度低，大数据规模巨大，仅从小部分数据难以
的强概率保证，从而确保了可扩展性。
来源多样，难以认
其包
知其全貌，从而难以全面认识大数据的语义。如何有效获取含了异常值检测和修复、Cleanix [65]是一个基于并行机群的大数据清洗系统，缺失值填充、实体识别以及冲突消充分的语义信息支持大数据质量管理是第三个挑战性问解等并行数据清洗模块。
题。当前大多数数据质量管理方法需要专家用户指定规则和相关参数，而自动错误检测修复和规则学习算法需要主数流清洗，2）数据清洗的线性亚线性算法。研究主要集中在数据
即通过扫描数据一次完成数据清洗，其主要应用背据或清洁的训练集。就大数据而言，一方面，聘请专家或维景是RFID 数据的清洗。
护主数据成本很高；另一方面，缺少自动选取有效训练集的文献[66]、[67]是早期RFID 数据清洗工作，提出了基于规算法。因此当前数据质量管理算法难以直接应用于大数据。
则的推理方法。这些方法直接作用于数据流上或者RFID 数据已经存储。使用规则的一个例子是将首先识别出的数据[67]2
大数据质量管理研究进展
或者读取次数最多的值[68]置为真值。文献[69]提出的方法利2.1
针对计算困难的解决方法
用参考对象（例如架子等）清洗RFID 数据流。文献[70]通过针对计算困难的问题，主要有两类解决方案，一是采取
考虑容量约束建立概率模型，提出了基于后验阅读率Metrop⁃并行化技术实施数据质量管理，二是为数据清洗设计线性亚线性的算法。
olis-Hasting 置。文献[71]采样来从模型中推理隐变量得到对象标签的位研究了用于对象检测的RFID 数据流清洗方法，
提出了移动环境下对象检测的概率模型，基于该模型设计了刚刚起步，1）并行数据质量管理。并行数据质量管理的研究当前研究工作主要集中在并行实体识别和并行相似性贝叶斯推理用于清洗RFID 数据。为了从运动的分布中抽样连接两个方面。
数据，设计了Gibss 采样器快速有效地清洗RFID 数据。
文献[72]提出了清洗有噪数据流的问题，其中噪声指的实体识别策略。为了简化多个相似性策略的实体识别配置，Dedoop [54]提供一个分块和匹配方法库，支持浏览器输入
是错误标记的训练样例，目标是精确地表示和去除误导的数Dadoop 据，从而提高基于清洁数据流得到的预测模型的精度。为了略自动转化为支持基于训练的机器学习方法，Hadoop 集群上并行执行的将特定的实体识别策MapReduce 任务。达到这个目的，其首先使用偏置方差分解得到用于数据流清Dedoop 洗的最大方差边际（MVM ），基于此概念，进一步提出了局部案[55,56]。文献支持无[57]冗基于余的MapReduce 多次分块平台设计了实体识别算法，
以及先进的负载平衡方和全局的过滤器框架结合局部（在单一数据块中）和全局（跨该方法首先通过属性值并行计算记录间的相似程度，而后基越多个连续数据块）过滤器来发现错误数据。于图聚类的方法进行实体识别从而输出得到最终结果。
2.2
针对混杂错误的解决方法
文献[58]基于MapReduce 框架设计了分类属性的填充算数据质量的多个方面相互关联。当前绝大多数研究人法，该算法利用基于概率的推理填充缺失值，该推理过程是员把数据质量的5个方面当作孤立的方向，已经有研究人员在一个基于属性相关性而建立起来的贝叶斯网络中进行。
开始复合类型错误的检测与修复，文献[73]探讨了信息修复和元组匹配的交互影响，基于条件函数约束和匹配约束提出连接算法，Vernica 这种方法也可以应用到基于等[59]提出了MapReduce 框架下的前缀过滤和PP Jaccard 相似性的相似了一个同时支持信息修复和实体识别的信息清洗框架。文连接。Metwally 和Faloutsos [60]提出了V-SMART-Join 算法，这献[74]提出了一种考虑数据时效性的冲突消解模型，该模型种算法在token 级别聚集相似性分数的贡献，从而计算相似利用时序偏序关系和时序约束来描述时效性，利用常数条件性函数。Afrati 等[61]研究了球散列技术和描点分析法来加速函数依赖描述一致性。该论文提出可以利用数据的时效顺MapReduce 上的相似性连接。Okcan 和Riedewald [62]设计了序辅助修复不一致数据，反之亦然，还提出同时考虑数据时Theta-Join 效性和一致性的统一数据消解算法。NADEEF [75]是一个端到文献[63]框架可以处理任意约束的连接。
研究了基于MapReduce 相似性字符串连接，支
端的数据清洗系统，提供编程界面允许用户输入各种异构的持多种基于集合的相似性函数和基于字母的相似性函数，该数据质量规则, 其中规则包括一致性约束和匹配规则，并提供方法扩展了现有基于划分的签名来支持基于集合的相似性核心算法检测错误并改正错误。函数，使用签名来生成key-value 对，为了减少通讯开销，这种2.3
针对知识缺少的解决方法
方法通过合并key-value 对来减少key-value 对数量。文献当前针对知识缺少的主要解决方法是引入用户的工[64]作。特别是通过众包技术进行数据质量管理。
据分布的划分，提出了ClusterJoin 将每条元组分布到其基于距离函数可能产生框架，这种方法将数据空间进行基于数目前在数据质量管理领域众包技术使用的最为广泛的连接结果的划分中，该方法为不同距离函数设计了一个强候问题是实体识别问题。Demartini 等[76]开发了一个人机交互系选元素过滤集合，从而每个元组仅需要被分不到少数划分中统，并增加了一个实体识别结果筛选概率框架。Wang 等[77]提从而保证正确性，为了解决高维数据中常见的偏斜问题，进出了一个以预算为基础的方法，假设没有足够的金钱标记所而设计了基于采样的动态负载平衡策略，其提供了划分规模
有记录，讨论如何利用有限的资金标识最有用的比较对。
81
www.kjdb.org 科技导报2014，32（34
）
Wang 法了解属性真实值的情况，因此在很多情况下需要容许错误明显不匹配的记录，等[77]开发了一种人机混合系统先用机器方法剔除一些将剩下的匹配对利用众包完成。随后又的存在，在存在错误的劣质数据上进行近似计算。现在已经提出了利用传递关系来减少可众包的记录对，并提出了一种
存在一些劣质数据查询处理算法，然而有两方面的工作做得可优化的标记排列顺序算法[78]。
还比较初步，有待进一步探索，一方面是当前劣质数据的计文献[79]提出了利用众包填充缺失值的策略，首先选择算对算法可扩展性考虑较少，难以应用到大数据，另一方面适用于众包填充的缺失值，继而根据属性类型选择不同缺失是当前劣质数据近似计算的研究成果主要集中在查询处理，
值填充方法。文献[80]将主动学习和众包相结合进行真值发计算的其他重要方面（如数据挖掘等）[85]
研究成果较少，存在
现，该方法采用迭代方法进行真值发现，在每一次迭代中通大量需要研究的问题。
过主动学习发现真值不确定性最高的属性进行众包，并基于返回结果进行投票，根据投票进一步判定真值不确定属性。
质量管理的重要问题之一在于缺乏对数据语义信息的充分4）支持数据质量管理的数据语义信息获取。目前数据
CrowdCleaner [81]是一个适用于Web 上多版本数据的清洗了解。因此支持数据质量管理的数据语义信息获取成为一系统，该系统使用基于众包技术来检测和修复传统数据清洗个亟待解决的问题。当前尽管有基于众包和互联网信息方方法难于解决的问题，并结合主动和被动众包方法纠正多版法用于获取知识以支持数据清洗，但这两方面的研究还刚刚本数据中的错误。
起步，仅覆盖了数据质量中实体统一性、完整性等少数几个维度和部分问题，有很多问题需要研究人员进一步研究和探索。
数据Lofi skyline 等[82,83]提出了采用众包平台数据库技术提高不完整
查询结果质量的方法。提出了精细的错误处理模型，在关注正确元组的同时，更加重点关注那些最有可能4结论
出错的元组。通过利用众包平台结合启发式技术，尽可能消由于具有规模大、多样性高和更新速度快的特点，大数
除错误值，集中处理最可能产生用户期待结果的元组。
据存在数据质量问题的可能性更大。数据质量对大数据应另外一种方法是通过提取互联网信息获取相应的语义用起着至关重要的作用，因此数据质量管理是大数据管理的信息。WebPut [84]是一个基于Web 信息的数据填充信息，该系核心步骤之一。与传统数据质量管理相比，大数据质量管理统扩展了信息提取方法用于形式化向Web 搜索查询以高效存在计算困难、错误混杂和缺少知识3方面的技术挑战亟待检索出缺失值。WebPub 使用了基于置信的方法自动为每个进一步研究。
缺失值选择最有效的填充查询，并设计了贪心的迭代算法确定数据填充顺序，并按顺序依次发布相应的查询。该论文还参考文献（References ）
提出一些优化策略用于在元组级别和数据库级别降低估计填充查询置信度的代价。
[1]Journal Li J Z, of Liu Computer X M. An Research important and aspect Development, of big data:2013, Data usability[J].3未来的工作
[2]1162.
50(6):1147-随着大数据的广泛应用，数据质量管理将越来越重要，
success Eckerson through W W. Data a commitment quality and to the bottom line:Achieving business 而面向大数据质量管理的研究刚刚起步，还存在诸多亟待解[3]The Data Warehousing Institute, 2000:high 12-20.
quality data[R].Renton, WA:决的问题。
[4][M].Institute of Medicine. To err is human:Building a safer health system Bohannon Washington:工作涉及到两种不同种类数据质量问题的协同处理，1）数据质量多维度相互影响的认知。当前尽管有一些
然而，tive SIGMOD heuristic P, Fan The International for W repairing F, National Flaster Academies Press, 1999.
Conference constraints M, et al. A cost-based model and effec⁃on Management by value modification[C].of Data, Baltimore, ACM 尚无综合考虑数据质量多个维度的方法提出，缺乏对这种相互影响的深入认识，而对数据质量问题的全面解决需要对这[5]Maryland, English L. June Plain 14-16, English 2005.
on data quality:Information 种相互影响进行定量分析，而且需要在统一逻辑框架下对不同数据质量问题的统一表达，这方面现在处于空白状态，有[6]ment:待深入研究。
[7][EB/OL].Ben W, The Schulz next frontier[J].DM Review Magazine, 2000.
quality manage⁃Gartner. 2010-03-19, S. Credit [2014-09-25].card statistics, http://www.creditcards.com.
industry facts, debt statistics will Gartner says more than 50percent of data warehouse projects
测与修复算法普遍计算复杂性超过线性，2）高效数据错误检测与修复算法设计。当前的错误检
而且缺少有效的并
OL].have 2005-02-24, limited acceptance [2014-09-25].or will http://www.gartner.com/newsroom/id/be failures through 2007[EB/行算法，难以适用于大数据，而仅有的线性复杂性算法和并[8]492112.
Elmagarmid 行算法只集中在相似性连接、实体识别、RFID 错误检测等几tion:A K, Ipeirotis P G, Verykios V S. Duplicate 个问题，对于大多数错误检测与修复的问题尚无适用于大数ing, A survey[J].IEEE Transactions on Knowledge and Data record Engineer⁃detec⁃据的高效算法提出，给研究人员很大的进一步研究的空间。
[9]Christen 2007, and P. 19(1):A survey 1-16.
of indexing techniques for 多情况下，3）劣质大数据近似计算理论与算法。对于大数据，错误难以完全修复，而且修复过程中经常存在无
在很
[10]neering, deduplication[J].IEEE Transactions on Knowledge scalable and record Data linkage Engi⁃Rahm E, 2012, Do H 24(9):H. Data 1537-1555.
cleaning:Problems and current approaches[J].
82
科技导报2014，32（34）www.kjdb.org
Bulletin Engineering of the Institute tional [11]Fan cies W [31]
Oregon, Conference on Knowledge Discovery and Data Mining, Portland, Mayfield August base for F, capturing Geerts Bulletin, of Electrical and Electronics Engineers Data
F, 2000, 23(4):3-13.
data Jia inconsistencies[J].X B, et al. Conditional ACM Transactions functional dependen⁃on Data⁃for C, Neville 2-4, 1996.
J, Prabhakar S. ERACER:A database approach [12]Bravo Systems, tional statistical The L, Fan W 2008, F, Ma 33(2):S. 1-48.
Extending dependencies with conditions[C].[32]USA, Conference inference on Management and data cleaning[C].of Data, ACM Indianapolis, SIGMOD Interna⁃Setiawan June [13]sity Fan of 33rd Vienna, International Austria, Conference September 23-27, on Very Large Data Bases, Univer⁃prediction N 6-10, Indiana, A, Venkatachalam 2010.
P, Hani A F M. Missing attribute value The [33]
Biomedical based Hua Engineering on artificial and Informatics, neural network 2008, and 1:rough set theory[J].[14]of 30th W F, ACM Geerts F, Wijsen J. Determining 2007.
the currency of data[C].Cao Database [C].butes[C].Y, Fan Systems SIGMOD-SIGACT-SIGART W (PODS),Athens, Greece, Symposium June 12-16, on 2011.
Principles Discovery The M, Pei 13th J. ACM Cleaning SIGKDD disguised missing data:A 306-310.
heuristic approach [15]York, 2013F, International Yu W Y. Determining Conference on the Management relative accuracy of attri⁃Chiang USA, [34]2007.
and Data Mining, San International Jose, California, Conference USA, August on Knowledge 12-15, Lin [16]ings F, Miller June 23-28, R J. Discovering 2013.
of Data, New data quality Fan of [35]nese X Journal M, Wang of Computers, W. Set and string similarity queries:A survey[J].Chi⁃dependencies[J].W the F, VLDB Geerts Endowment, rules[J].The Proceed⁃F, Li J Z, et 2008, al. Discovering 1(1):1166-1177.
conditional functional [36]California:Leopoldo B. Morgan Database &Claypool, repairing 2011, 34(10):2011.
and consistent 1853-1862.
query answering[M].[17]Chu ing, 2011, IEEE Transactions on Knowledge and Data Engineer⁃straints[M]//IntegrityBry F. Query answering [18]
ceedings X, Ilyas 23(5):I F, 683-698.
Papotti P. Discovering denial constraints[J].The Pro⁃Bauckmann of the [37]
York:and Internal in information Control in systems Information with integrity Systems. con⁃Arenas Springer, clusion J, Abedjan VLDB Endowment, Z, Leser U, 2013, et al. 6(13):Discovering 1498-1509.
conditional sistent M, Bertossi 1997:L, 113-130.
New Chomicki J. Consistent query answers in incon⁃Information dependencies[C].Symposium databases[C].Eighteenth ACM SIGACT-SIGMOD-SIGART [19]November and Knowledge The Management, 21st ACM International Maui, Hawaii, Conference in⁃October on Loshin [38]vania, Kolaitis May on Principles of Database Systems, Philadelphia, Pennsyl⁃databases P with G, 31-June Pema 2, binary E, 1999.
integer Tan W programming[J].C. Efficient querying The Proceedings of inconsistent of the [20]2008.
D. Master 2, 2012.
29-data management[M].San Francisco:Morgan Kaufmann, Fan actions W F, Geerts F. Relative information completeness[J].ACM Trans⁃[39]BarcelóVLDB Endowment, [21]
Bohannon on [M]//PracticalP, Bertossi L. 2013, 6(6):397-408.
tive SIGMOD heuristic P, Database Fan Systems, 2010, 35(4):27-35.
for repairing W, Flaster constraints M, et al. A cost-based model and effec⁃[40]2003:Fuxman 208-222.
Aspects Logic of Declarative programs for Languages. querying inconsistent New York:databases Springer, inconsistent A, Fazli [22]Maryland, International Cong USA, June 14-16, Conference on Management by value modification[C].of Data, Baltimore, ACM and accuracy[C].G, Fan W, The Geerts 33rd F, et 2005.
al. Improving data quality:Consistency [41]Management databases[C].E, Miller ACM R J. SIGMOD Conquer:International Efficient management of Fuxman tabases[J].A, Journal Miller of Data, R of J. Baltimore, Maryland, USA, June 14-16, Conference 2005. on Computer First-order and query System rewriting Sciences, for inconsistent 2007, 73(4):da⁃[23]Arenas Bases, University International Conference on Very Large Data sistent [42]Wijsen 610-635.
ization J. [24]434.
databases[J].M, Bertossi of L Vienna, Austria, September 23-27, 2007.
Theoretical E, Chomicki Computer J, et al. Science, Scalar aggregation 2003, 296(3):in incon⁃405-Geerts framework[J].F, Mecca G, Papotti P, et al. The LLUNATIC data-cleaning [43]Database of Consistent tractable queries[C].query answering The 12th under International primary keys:A character⁃Greco consistent S, Pijcke Theory, F, St Wijsen Petersburg, J, et Russia, March 23-25, 2009.
Conference on [25]625-636.
The Proceedings of the VLDB Endowment, 2013, 6(9):Fan tency W F, Geerts F, Tang N, et [44]Maslowski (5):32-65.
databases[J].Proceedings al. Certain of the query VLDB answering Endowment, in partially 2014, 7tive [26]on Galland Data for Engineering, conflict resolution[C].al. 29th Inferring IEEE data International currency and Conference consis⁃from A, Abiteboul Brisbane, S, Marian April A, 8-12, et al. 2013.
Corroborating information [45]Database queries D, with Wijsen self-J. joins[C].Counting The database repairs that satisfy conjunc⁃Maslowski Theory, International D, Wijsen Athens, J. Greece, 17th International Conference on On March 24-28, 2014.
[27]Web disagreeing Dong Search and views[C].Data Mining, The New third York, ACM USA, International Conference on The [46]25, Khalefa 2011.
Workshop on Logic counting in Databases, database San repairs[C].Miniato, The March 4th for [28]dowment-PVLDB, role X L, of Berti-Equille source dependence[J].L, Srivastava The D. Proceedings Integrating February of conflicting 3-6, 2010. the VLDB data:En⁃Dong detection X L, [47]Data incomplete M E, Mokbel data[C].M 2008F, Levandoski J J. Skyline query processing Alwan Engineering plete A A, Ibrahim (ICDE'08), Cancun, IEEE 24th April International 7-12, 2008.
Conference on [29]ment-PVLDB, in Berti-Equille 2009, 2(1):a dynamic world[J].L, Srivastava 550-561.
The Proceedings D. Truth discovery of the VLDB and copying Endow⁃Zhao discovering B, Rubinstein 2009, B 2(1):I P, 562-573.
Gemmell J, et al. A bayesian [48]
on multidmensional H, database[C].Udzir N I, et The al. 3rd Skyline International queries over incom⁃Bharuka Computing ceedings R, Kumar and Informatics, P S. Finding Bandung, skylines June for 8-9, 2011.
Conference [30]
Proceedings truth Lakshminarayan of the from VLDB conflicting Endowment, sources 2012, for data integration[J].approach The to Gold ing data using machine K, Harp learning S A, Goldman techniques[C].R, et 5(6):al. 550-561.
The Imputation Second of Interna⁃
miss⁃[49]
109-117.
Coast, of the Queensland:Twenty-Fourth Australian Australasian incomplete data[C]//Pro⁃Computer Database Society, Conference. 2013, 137:Miao X, Gao Y, Chen L, et al. On efficient k-skyband query process⁃
83
www.kjdb.org 科技导报2014，32（34
）
ing tions. over incomplete data[M]//DatabaseSystems for for [50]Gao Large rfid skyline, Y, Berlin Miao Heidelberg:X, Cui H, Springer, et al. 2013:424-439.
Advanced Applica⁃
[68]Jeffery Data data Bases, analytics[C].Seoul, Korea, The 32nd September International Conference on Very streams[C].S, Garofalakis [51]
Systems and Hadjali with group-Applications, by skyline queries Processing on incomplete k-skyband, data[J].constrained Expert Bases, The 32nd M, Franklin M. Adaptive 12-15, cleaning 2006.
for rfid data incomplete A, [69]of preferences[C]//ProceedingPivert O, Prade 2014, H. Possibilistic 41(10):4959-4974.
of contextual skylines with streams Tran T, Seoul, International Conference on Very Large Data Sutton Korea, C, Cocci September R, et 12-15, al. Probabilistic 2006.
inference over rfid [52]
of Soft Electrical Computing and Electronics and Pattern Recognition. 2010New International York, USA:Conference Institute [70]on in mobile environments[C].The 25th International Conference Chen Data missing Arefin M cy H, Engineering, Ku W, Wang March H, et 29-April al. Leveraging 2, 2009.
spatio-temporal redundan⁃Computer values[C]//ProceedingS, Morimoto Y. Skyline Engineers, sets 2010:queries 57-62.
from databases with [71]
Zhao on for Management rfid data of cleansing[C].Data, Indianapolis, ACM SIGMOD Indiana, International USA, Conference [53]and Markus Electronics Theory Engineers, and Applications. of 22nd International Conference on 2012:Chengdu:Institute of Electrical ing[C].Z, preference E, Knowledge The Ng W. 21st A model-based ACM International approach Conference for RFID on data June Information stream 6-10, cleans⁃2010. and [54]Intelligence, database Patrick R, Florian W, 24-29.
et al. Handling of NULL values in Kolb [72]2012.
Management, Maui, Hawaii, October 29-November 2, Zhu The X [55]The L, Thor Montpellier, queries[C].20th European Conference on Artificial A, France, August 27-31, 2012.
Kolb Proceedings Rahm of the E, VLDB et al. Endowment, Efficient deduplication 2012, 5(12):with hadoop[J].resolution[C].L, Thor A, [73]December IEEE Q, Zhang International P, Wu Conference X D, et al. on Cleansing Data Mining, noisy Cancún,data streams[C].México,Fan and W F, 15-19, Li J Z, 2008.
Ma S, et al. Interaction between record matching [56]
Washington International Rahm E. Load 1878-1881. Council balancing for Open for MapReduce-based entity Kolb lution L, Thor D A, C, Rahm April 1-5, and Distance Education, E. Block-based 2012.
[74]Management data repairing[C].ACM SIGMOD International Conference on Fan on tency W F, Geerts of Data, F, Tang Athens, N, et Greece, al. June 12-16, 2011.
[57]dom, Information with MapReduce[C].load balancing for entity reso⁃and Knowledge The 20th ACM International Conference Huo October [75]ence Ebaid on for Data conflict resolution[C].The Inferring 29th IEEE data currency International and Confer⁃consis⁃data A, Elmagarmid Engineering, A K, Brisbane, Llyas I, April et al. 8-12, NADEEF:2013.
A [58]based R, Wang 24-28, H Z, 2011.
Management, Glasgow, United King⁃Zhu R, et Jin data L, on al. Entity identification in big data Wang MapReduce[J].H EIBM, 2013, 50(S2):20-35.
[76]
2013, cleaning system[J].The Proceedings of the generalized Demartini 6(12):VLDB Endowment, probabilistic G, 1218-1221.
Difallah D [59]opment, based on Map-Reduce[J].Z, Huang S B, Journal et al. Missing value imputation in big Vernica 2013, entity using R, Carey 50(Sl):of Computer Research and Devel⁃M 312-321.
J, Li C. [77]France, linking[C].reasoning The and E, Cudr'e-Mauroux crowdsourcing techniques P. ZenCrowd:for large-Leveraging scale Wang [60]Management mapreduce[C].Metwally of Data, Indianapolis, ACM SIGMOD Efficient parallel set-similarity joins Indiana, International Conference on resolution[J].J, April 21st World Wide Web Conference, Lyon, Kraska 16-20, T, Franklin 2012.
M work [78]1483-1494.
The Proceedings J, of et the al. VLDB CrowdER:Endowment, Crowdsourcing 2012, entity 5(11):Wang [61]Proceedings for A, all-Faloutsos pair similarity C. V-smart-join:joins of multisets A USA, scalable June and mapreduce 6-10, 2010. vectors[J].frame⁃The Afrati crowdsourced J N, Li duce[C].F N, of the VLDB Endowment, 2012:213-300.
[79]ta, joins[C].G L, Kraska International T, et al. Leveraging transitive relations for Ye New [62]Washington International Sarma A D, Council Menestrina for D, Open et al. Fuzzy joins using mapre⁃Okcan ACM A, Riedewald D C, April M. 1-5, and Distance Education, Processing 2012.
theta-joins [80]Lecture C, Wang York, Conference on Management of Da⁃H USA, Z. Capture June 22-27, missing 2013.
values based on crowdsourcing[J].Ye [63]
Athens, SIGMOD International Conference on Management using mapreduce[C].Deng [81]
ing[J].C, Wang Notes in Computer Science, 2014, 8491:783-792.
Tong for D, Greece, June 12-16, 2011.
of Data, for Y Lecture H X, Cao Notes Z, Gao C C, in H, et al. Truth discovery based on crowdsourc⁃Zhang Computer C J, Science, et al. CrowdCleaner:2014, 8485:453-458.
Conference scalable Li G string L, Hao similarity S, et al. joins[C].MassJoin:A mapreduce-based method 30th multi-version [64]2014.
on Data Engineering, Moscow, 2014Russia, IEEE March 30th International 31-April 4, [82]March International data Conference on the web Data cleaning on via crowdsourcing[C].2014IEEE Lofi framework Sarma A D, using He MapReduce[J].Y Y, Chaudhuri The S. Proceedings ClusterJoin:of the A similarity joins ta-error C, 31-April El Maarry 4, K, 2014.
Data Engineering, Moscow, Russia, Balke W T. Skyline [65]Wang ment, 2014, VLDB Endow⁃[83]Berlin:models for focused queries over incomplete da⁃Lofi 23rd H Z, Li 7(12):M D, 1059-1070.
Bu Y Y, et al. databases[C].C, Springer, El Maarry 2013:298-312.
crowd-sourcing[M]//ConceptualModeling. [66]
Management, ACM International A big data cleaning parfait[C].The BornhövdShanghai, Conference on Information and Knowledge [84]base The 16th K, Balke International W T. Skyline Conference queries on in crowd-enabled Li tion C, Lin T, Haller Nov S, 3-7, et al. 2014:Integrating 10-23.
automatic data acquisi⁃ture[J].with [85]
Chen imputation[J].Z Technology, X, Sharaf World M Genoa, A, Wide Sitbon Italy, March 18-22, 2013.
Extending Data⁃Web, L, et 2014, al. A 17(5):web-873-897based approach .
to data cation Y C, Li J Z, Luo J Z. ITCI:An information theory based classifi⁃[67]
1188.
The business Proceedings processes of the experiences VLDB Endowment, with sap's auto-id 2004, 30:infrastruc⁃1182-Rao J, Doraiswamy S, Thakkar H, et al. A deferred cleansing method
Science, algorithm 2014, 8485:for incomplete 167-179.
data[J].Lecture Notes in Computer （责任编辑王媛媛）
84