用于不一致检测的数据源选择算法的研究

发布时间：2021-03-03 00:20

　　数据质量是衡量数据好坏的重要标准之一。通常数据质量分为几个维度来评价数据的好坏:一致性,完整性,准确性,数据冗余。在许多领域中,如商业、音乐、体育等,这些数据源可能会提供劣质的数据信息。这些劣质的数据会给用户在很多方面造成不便（如数据冗余,不一致,不完整等）,导致数据的利用有效性降低。因此我们需要一个快速有效的检测数据错误的方法提高数据的使用效率。一致性是数据质量的核心标准之一。当同一实体的相同属性出现不同信息,这个数据就是不一致的。数据不一致性会导致数据质量降低,在数据源指代同一实体时包含错误或矛盾的数据,使得数据源选择难度增大,数据源的可靠性降低。当前针对数据一致性的检测主要是通过检查数据是否违反依赖规则,例如函数依赖、条件函数依赖等来判定。然而,仅仅通过依赖规则来检测不一致错误是不够的,这是因为一个完全满足依赖规则集合的数据集依然可能存在着错误。为了发现目标数据集中更多的错误,我们考虑同时利用多数据源和依赖规则集合检测目标数据集中的不一致错误。然而,由于数据源数目的庞大,访问所有的数据源会引入巨大开销,这使得不一致检测的成本过于巨大。为解决该问题,我们考虑从数据源集合中选择k个数... 

【文章来源】：黑龙江大学黑龙江省

【文章页数】：63 页

【学位级别】：硕士

【部分图文】：

论文框架

图 2-1 布隆过滤器例子Fig 2-1 A example for bloom filter判断 Y 元素是否处于集合中时，采用上述同样的方法将 Y 通过哈位数组上，得到相应位置的点，将该位置置为 1。在判断过程中，如果有任意一个点不为 1，我们可以判断该元素一。相反，如果每个点均为 1，则该元素可能存在集合中。里我们需要注意：布隆过滤器的假阴性为 0，存在假阳性误判率，判断元素一定存在集合中。很明显，在这个过程中并不能保证查找全正确的。所以我们在利用布隆过滤器的时候需要考虑如何根据元位数组 1 的大小及哈希函数的个数，使得假阳性最小。定集合 A，B，以及它们的布隆过滤器[24] ，k 为布隆过滤器中的，l 为布隆过滤器的长度。下面我们将给出布隆过滤器的相关性质

生成元组（no_tuple） 20000 20000概率范围（min_perc,max_perc） （100%，100%） （30%，90%）值域（size_domain） 1000 1000数据源个数（#Sources） 1 100选取哈希个数（#Hash） 100 100我们实现了两种选择算法：一种是基于估计覆盖的近似算法，称为 BF-Greedy；一种是对所有数据源的访问得到的精确覆盖信息的贪心选择算法，称为 Greedy。我们将 BF-Greedy 与 Greedy 算法进行了比较，验证了算法的效率与正确性。实验的硬件环境是：Win10 系统的 PC 机，内存为 8GB，算法用 C++实现。3.5.2 实验比较我们首先在实际数据集上，对选取的数据源个数 K 为 1~10，哈希函数个数#Hash 为 1~10 的准确性进行了比较。对比结果如图 3-1-图 3-4 所示。


本文编号：3060228