一个关于数据清理的相似性连接处理的早期研究2015.docVIP

一个关于数据清理的相似性连接处理的早期研究 摘要 基于相似性的数据清理包括“关闭”的元组的识别，在那里选择合适的域和应用程序功能可以使用各种相似函数去评估数据的相似性。有效的实施这种相似连接的当前方法被紧紧地绑定到所选择的相似函数上。在本文中，我们提出一个新的原始运算符根据各种流行的连接字符串功能的相似性和超越的概念相似度的文本相似性可以用作一个基础来实现相似。 然后我们提出此运算符的有效实现。实验评价中使用真实数据集，，而且往往远比以前的自定义实现特定功能的相似性。填充和维护数据仓库和数据集中的数据存储库一个非常重要的数据清洗操作“加入”类似的数据考虑一个销售数据仓库主产品目录和客户登记记录在这些情况下，最好执行相似的联接。当前方法利用相似属性值之间加入数据之间的关系，例如用于测量相似之处。然而，没有一个相似的字符串函数是已知的整体最佳功能的相似性，而选择通常取决于应用程序域[10，13]请参阅6节。R和S关于θ的连接在连接断定θ是f (R.A, S.A ) α，因为有一个相似函数f和一个门槛α。虽然相似连接也许通过用户定义函数(UDFs)被定义连接谓词表示在结构化查询语言中，但是在执行跨产品后，评价很低效，因为数据库系统通常被迫仅适用于基于联接谓词。[1、8、9]。一个通用数据清洗平台支持基础原始的或具有挑战性的选项，我们建议SSJoin运算符用作基础的原始并显示可用于支持基于几个字符串相似的相似性联接功能编辑相似性，个采样点相似，广义编辑相似，汉明距离，soundex等在定义SSJoin运算符，我们利用设置重叠的观察能有效支持多种功能的相似性[13]。因为稍后我们将显示，这个逻辑运算符的设计和实施，充分利用现有的关系运算符，并帮助定义丰富的选择空间，优化查询涉及的相似加入。SSJoin——表示集的相似性连接——适合用于两个都包含列A和B的关系R和S。再元组中，一组分享相同值R.A值的R.B值构成R.A的相应的集合。SSJoin字符组返回几组不同的的值对R.A,S.A，如果几组相应的R[B]和S[B]的值对的重叠式高于一个使用者指定的阈值，我们允许加权的和不加权的的版本。作为一个例子，考虑两个关系R [国家，城市]和S [国家，城市]。设置=状态和B =城市，SSJoin运算符返回R.state, S.state值对，如果每个国家所发生的城市之间的重叠是超过阈值。因此，它可能会返回的对（华盛顿，WA）和（“威斯康星”，“无线”），因为这些群体内的城市设置重叠显著。第3节中，铸造成一个利用SSJoin运营商的设置。然后，我们为SSJoin。本文的其余部分安排如下：第2节中，我们定义SSJoin运营商。第3节中，我们。第4节中，我们为SSJoin运营商描述了一个高效的物理实现。在第5条中，我们我们物理实现是有效的几个真实数据，有时甚至大大高于自定义实现。在第6和第7我们讨论了相关的 在本节中，我们通过使用一套映射字符串和使用集合重叠测量相似性的一个简单的概念正式的规定一个字符串相似的函数。然后我们规定SSJoin操作符，要求能够被使用去评价集合重叠相似性的这个概念。 有几个著名的映射一个字符串到一个集合的方法。例如：分割分开的单词成集合，分割长度为Q的字符串为集合，即q-grams，等等。例如：字符串“Microsoft Corporation”能够被处理分割视为一组字{‘Microsoft’，‘Corp’}，或者作为一组三个字符长度为一单位的集合{‘Mic‘，‘icr’，‘cro’，‘ros’，‘oso’，‘sof’，‘oft’，‘ft ’，‘t C’，‘ Co’，‘Cor’，‘orp’}。从这以后，我们把集合对应的一个字符串σ记作为Set（σ）。通过上面的任何一种方法，我们可以得到这样的一套。在本文中，我们专注于多集合。每当我们提及到集合，我们指的是多集合。因此，当我们提及集合的交集与并集，我们的意思分别是多并集和多交集。 在一般情况下，元素可能与。这是为了捕捉直觉，一个字符串的不同部分有不同的重要性。例如，在字符串中的Microsoft Corp”，我们可能要联想到更重要的部分Corp”。有闻名于世的关联权重集的元素，如在信息检索中常用的逆文档频率（IDF）上的概念，方法。我们假设，一个集合的元素，如一个字或Q-，，是固定的，它的。被定义为一个集合S的重量是其成员的权重的总和记为WT（S）。WT（S1∩S2）的。σ1，σ2间的重叠相似性Overlap（σ1，σ2）被定义为σ1），σ2））。 关系R和S，每个字符串值属性A，考虑R和S返回的所有元组，其中RA和SA之间的重叠相似超过一定的阈值。我们预计，当两个字符串是几乎相等，其重叠的相似性是高的，因此这是一个自然连接谓词表达的相似性。接下来我们介绍SSJoin，可以用来表