海量不完整数据的核心数据选择问题的研究

摘要

在大数据时代,越来越多的带有缺失值的数据需要处理,因而数据不完整成为一种常见的数据质量问题.不完整的数据给大数据的查询、挖掘和分析带来了困难.在某些情况下,数据中的很多缺失值是无法被确定的.只能根据用户的需求,在不完整的数据上选择一部分用户感兴趣的核心数据集合,来提高不完整数据的可用性.完整度较高,规模较小,在用户感兴趣的属性上给出更多完整信息的核心数据集合,能够支持高效的查询处理,提高查询结果的准确性和完整性.该文形式化了核心数据选择问题,证明了这至少是一个NP-难问题.由于需要同时优化核心数据集合的完整度、集合的规模以及对于感兴趣属性的覆盖性,现有的基于集合覆盖问题的方法无法解决文中提出的问题.该文提出了一个采用贪心策略,具有理论保证的近似核心数据选择算法ACS.ACS首先判断当前的数据集合是否存在一个满足覆盖性要求的子集合.当这样的子集合存在时,ACS尽量选择完整的元组来组成核心数据集合,当使用完整元组无法满足覆盖性的要求时,ACS选择较少的不完整元组.ACS通过限制选择的次数来获得一个集合大小的上界是运行次数常数倍的子集合,并且保证了对于感兴趣的属性的覆盖比例.通过理论分析可知,ACS能够在近似线性的时间内,找到一个大小至多在给定的大小对数因子内的近似核心数据集合,其中被覆盖的感兴趣的属性的比例至少为(1-1/e),包含的不完整元组的个数至多为给定的核心数据集合的大小,其中e是自然对数的底数.通过在DBLP和NBA球员信息这两个真实数据集合上的实验,表明了所提出的算法ACS的有效性和高效性;通过在规模更大的合成数据上的实验,表明了ACS的良好的扩展性.