公开(公告)号：US08606771B2

公开(公告)日：2013-12-10

申请号：US12973909

申请日：2010-12-21

申请人： Arvind Arasu ,  Parag Agrawal ,  Kaushik Shriraghav

发明人： Arvind Arasu ,  Parag Agrawal ,  Kaushik Shriraghav

IPC分类号： G06F7/00 ,  G06F17/30

CPC分类号： G06F17/30336

摘要： The claimed subject matter provides a method and a system for the efficient indexing of error tolerant set containment. An exemplary method comprises obtaining a frequency threshold and a query set. All tokens or token sets within the query set are determined, and then all minimal infrequent tokens or all minimal infrequent tokens sets of data records are found and used to build an index. The minimal infrequent tokens or minimal infrequent tokensets are processed in a fixed order, and then a collection of signatures for each minimal infrequent token or token set is determined.

摘要翻译： 所要求保护的主题提供了用于有效地索引误差容限集的方法和系统。 一种示例性方法包括获得频率阈值和查询集。 确定查询集中的所有令牌或令牌集，然后找到所有最小的不频繁令牌或所有最小的不频繁令牌数据记录集，并用于构建索引。 以固定的顺序处理最小的不频繁令牌或最小不频繁的令牌，然后确定每个最小不频繁令牌或令牌集的签名集合。

公开(公告)号：US20120158696A1

公开(公告)日：2012-06-21

申请号：US12973909

申请日：2010-12-21

申请人： Arvind Arasu ,  Parag Agrawal ,  Kaushik Shriraghav

发明人： Arvind Arasu ,  Parag Agrawal ,  Kaushik Shriraghav

IPC分类号： G06F17/30

CPC分类号： G06F17/30336

摘要： The claimed subject matter provides a method and a system for the efficient indexing of error tolerant set containment. An exemplary method comprises obtaining a frequency threshold and a query set. All tokens or token sets within the query set are determined, and then all minimal infrequent tokens or all minimal infrequent tokens sets of data records are found and used to build an index. The minimal infrequent tokens or minimal infrequent tokensets are processed in a fixed order, and then a collection of signatures for each minimal infrequent token or token set is determined.

摘要翻译： 所要求保护的主题提供了用于有效地索引误差容限集的方法和系统。 一种示例性方法包括获得频率阈值和查询集。 确定查询集中的所有令牌或令牌集，然后找到所有最小的不频繁令牌或所有最小的不频繁令牌数据记录集，并用于构建索引。 以固定的顺序处理最小的不频繁令牌或最小不频繁的令牌，然后确定每个最小不频繁令牌或令牌集的签名集合。

公开(公告)号：US07865505B2

公开(公告)日：2011-01-04

申请号：US11668870

申请日：2007-01-30

申请人： Arvind Arasu ,  Venkatesh Ganti ,  Kaushik Shriraghav

发明人： Arvind Arasu ,  Venkatesh Ganti ,  Kaushik Shriraghav

IPC分类号： G06F7/00 ,  G06F17/30

CPC分类号： G06F17/30498 ,  G06F17/30533

摘要： A machine implemented system and method that efficiently facilitates and effectuates exact similarity joins between collections of sets. The system and method obtains a collection of sets and a threshold value from an interface, and based at least in part on an identifiable similarity, such as an overlap or intersection, between the collection of sets the analysis component generates and outputs a candidate pair that at least equals or exceeds the threshold value.

摘要翻译： 一种机器实现的系统和方法，其有效地促进并实现集合集合之间的精确相似性连接。 系统和方法从接口获得集合集合和阈值，并且至少部分地基于分析组件生成的集合集合之间的可识别相似性（例如重叠或交集）并输出候选对， 至少等于或超过阈值。

公开(公告)号：US20120330880A1

公开(公告)日：2012-12-27

申请号：US13166831

申请日：2011-06-23

申请人： Arvind Arasu ,  Kaushik Shriraghav ,  Jian Li

发明人： Arvind Arasu ,  Kaushik Shriraghav ,  Jian Li

IPC分类号： G06F17/30 ,  G06N5/02

CPC分类号： G06F16/24544

摘要： The claimed subject matter provides a method for data generation. The method includes identifying a generative probability distribution based on one or more cardinality constraints for populating a database table. The method also includes selecting one or more values for a corresponding one or more attributes in the database table based on the generative probability distribution and the cardinality constraints. Additionally, the method includes generating a tuple for the database table. The tuple comprises the one or more values.

摘要翻译： 所要求保护的主题提供了用于数据生成的方法。 该方法包括基于用于填充数据库表的一个或多个基数约束识别生成概率分布。 该方法还包括基于生成概率分布和基数约束来选择数据库表中对应的一个或多个属性的一个或多个值。 另外，该方法包括生成数据库表的元组。 元组包含一个或多个值。

公开(公告)号：US09547718B2

公开(公告)日：2017-01-17

申请号：US13325072

申请日：2011-12-14

申请人： Jiewen Huang ,  Zhimin Chen ,  Arvind Arasu ,  Vivek Narasayya

发明人： Jiewen Huang ,  Zhimin Chen ,  Arvind Arasu ,  Vivek Narasayya

IPC分类号： G06F17/30

CPC分类号： G06F17/30867 ,  G06Q30/0201

摘要： A set expansion system is described herein that improves precision, recall, and performance of prior set expansion methods for large sets of data. The system maintains high precision and recall by 1) identifying the qualify of particular lists and applying that quality through a weight, 2) allowing for the specification or negative examples in a set of seeds to reduce the introduction of bad entities into the set, and 3) applying a cutoff to eliminate lists that include a low number of positive matches. The system may perform multiple passes to first generate a good candidate result set and then refine the set to find a set with highest quality. The system may also apply Map Reduce or other distributed processing techniques to allow calculation in parallel. Thus, the system efficiently expands large concept sets from a potentially small set of initial seeds from readily available web data.

摘要翻译： 本文描述了一种扩展系统，可提高大型数据集的先前设置扩展方法的精度，调用和性能。 该系统通过1）确定特定列表的资格并通过权重来应用该质量，保持高精度和召回; 2）允许一组种子中的规范或否定示例，以减少将不良实体引入到集合中; 3）应用截止值来消除包括少量正匹配的列表。 系统可以执行多次通过以首先产生良好的候选结果集合，然后对该集合进行优化以找到具有最高质量的集合。 该系统还可以应用Map Reduce或其他分布式处理技术来并行计算。 因此，系统从容易获得的网络数据的一小部分初始种子中有效地扩展了大概念集。

公开(公告)号：US07610283B2

公开(公告)日：2009-10-27

申请号：US11761425

申请日：2007-06-12

申请人： Arvind Arasu ,  Venkatesh Ganti ,  Shriraghav Kaushik

发明人： Arvind Arasu ,  Venkatesh Ganti ,  Shriraghav Kaushik

IPC分类号： G06F17/30 ,  G06F7/06 ,  G06F7/08 ,  G06F7/10

CPC分类号： G06F17/30312 ,  Y10S707/99931 ,  Y10S707/99932 ,  Y10S707/99933 ,  Y10S707/99935 ,  Y10S707/99937

摘要： Input set indexing for set-similarity lookups. The architecture provides input to an indexing process that enables more efficient lookups for large data sets (e.g., disk-based) without requiring a full scan of the input. A new index structure is provided, the output of which is exact, rather than approximate. The similarity of two sets is specified using a similarity function that maps two sets to a numeric value that represents similarity of the two sets. Threshold-based lookups are addressed where two sets are considered similar if the numeric similarity score is above a threshold. The structure efficiently identifies all input sets within a distance k (e.g., a hamming distance) of the query set. Additional information in the form of frequency of elements (the number of input sets in which an element occurs) is used to improve index performance.

摘要翻译： 用于集合相似性查找的输入集索引。 该体系结构为索引过程提供输入，可以对大数据集（例如，基于磁盘）进行更有效的查找，而无需对输入进行全面扫描。 提供了一个新的索引结构，其输出是精确的，而不是近似的。 使用将两组映射到表示两组相似度的数值的相似度函数来指定两组的相似度。 如果数字相似性分数高于阈值，则基于阈值的查找被解决为其中两个集合被认为是相似的。 该结构有效地识别查询集合的距离k（例如，汉明距离）内的所有输入集合。 使用元素频率（元素发生的输入集合的数量）的形式的附加信息用于提高索引性能。

公开(公告)号：US09081817B2

公开(公告)日：2015-07-14

申请号：US13084527

申请日：2011-04-11

申请人： Arvind Arasu ,  Michaela Götz ,  Shriraghav Kaushik

发明人： Arvind Arasu ,  Michaela Götz ,  Shriraghav Kaushik

IPC分类号： G06F17/30 ,  G06N99/00

CPC分类号： G06F17/30507 ,  G06N99/005

摘要： An active learning record matching system and method for producing a record matching package that is used to identify pairs of duplicate records. Embodiments of the system and method allow a precision threshold to be specified and then generate a learned record matching package having precision greater than this threshold and a recall close to the best possible recall. Embodiments of the system and method use a blocking technique to restrict the space of record matching packages considered and scale to large inputs. The learning method considers several record matching packages, estimates the precision and recall of the packages, and identifies the package with maximum recall having precision greater than equal to the given precision threshold. A human domain expert labels a sample of record pairs in the output of the package as matches or non-matches and this labeling is used to estimate the precision of the package.

摘要翻译： 用于产生用于识别重复记录对的记录匹配包的主动学习记录匹配系统和方法。 系统和方法的实施例允许指定精度阈值，然后产生具有大于该阈值的精度的学习记录匹配包以及接近最佳可能召回的召回。 系统和方法的实施例使用阻塞技术来限制所考虑的记录匹配包的空间并将其缩放到大的输入。 学习方法考虑了几个记录匹配包，估计包的精度和调用，并且识别具有大于等于给定精度阈值的精度的最大召回的包。 人类领域专家将包的输出中的记录对的样本标记为匹配或不匹配，并且该标签用于估计包的精度。

公开(公告)号：US20120259802A1

公开(公告)日：2012-10-11

申请号：US13084527

申请日：2011-04-11

申请人： Arvind Arasu ,  Michaela Götz ,  Shriraghav Kaushik

发明人： Arvind Arasu ,  Michaela Götz ,  Shriraghav Kaushik

IPC分类号： G06F15/18

CPC分类号： G06F17/30507 ,  G06N99/005

摘要： An active learning record matching system and method for producing a record matching package that is used to identify pairs of duplicate records. Embodiments of the system and method allow a precision threshold to be specified and then generate a learned record matching package having precision greater than this threshold and a recall close to the best possible recall. Embodiments of the system and method use a blocking technique to restrict the space of record matching packages considered and scale to large inputs. The learning method considers several record matching packages, estimates the precision and recall of the packages, and identifies the package with maximum recall having precision greater than equal to the given precision threshold. A human domain expert labels a sample of record pairs in the output of the package as matches or non-matches and this labeling is used to estimate the precision of the package.

摘要翻译： 用于产生用于识别重复记录对的记录匹配包的主动学习记录匹配系统和方法。 系统和方法的实施例允许指定精度阈值，然后产生具有大于该阈值的精度的学习记录匹配包以及接近最佳可能召回的召回。 系统和方法的实施例使用阻塞技术来限制所考虑的记录匹配包的空间并将其缩放到大的输入。 学习方法考虑了几个记录匹配包，估计包的精度和调用，并且识别具有大于等于给定精度阈值的精度的最大召回的包。 人类领域专家将包的输出中的记录对的样本标记为匹配或不匹配，并且该标签用于估计包的精度。

公开(公告)号：US08200640B2

公开(公告)日：2012-06-12

申请号：US12484406

申请日：2009-06-15

申请人： Arvind Arasu ,  Christopher Re ,  Dan Suciu

发明人： Arvind Arasu ,  Christopher Re ,  Dan Suciu

IPC分类号： G06F7/00 ,  G06F17/00

CPC分类号： G06F17/30303 ,  G06F17/30489

摘要： A system, framework, and algorithms for data deduplication are described. A declarative language, such as a Datalog-type logic language, is provided. Programs in the language describe data to be deduplicated and soft and hard constraints that must/should be satisfied by data deduplicated according to the program. To execute the programs, algorithms for performing graph clustering are described.

摘要翻译： 描述了用于重复数据删除的系统，框架和算法。 提供了一种声明性语言，例如Datalog类型的逻辑语言。 该语言中的程序描述了要重复数据删除的数据，以及根据程序重复数据删除的数据必须/应该满足的软和硬限制。 为了执行程序，描述了执行图形聚类的算法。

公开(公告)号：US20090210418A1

公开(公告)日：2009-08-20

申请号：US12031715

申请日：2008-02-15

申请人： Arvind Arasu ,  Surajit Chaudhuri ,  Shriraghav Kaushik

发明人： Arvind Arasu ,  Surajit Chaudhuri ,  Shriraghav Kaushik

IPC分类号： G06F17/30

CPC分类号： G06F17/30569 ,  G06F17/30675 ,  G06F17/30985

摘要： A transformation-based record matching technique. The technique provides a flexible way to account for synonyms and more general forms of string equivalences when performing record matching by taking as explicit input user-defined transformation rules (such as, for example, the fact that “Robert” and “Bob” that are synonymous). The input string and user-defined transformation rules are used to generate a larger set of strings which are used when performing record matching. Both the input string and data elements in a database can be transformed using the user-defined transformation rules in order to generate a larger set of potential record matches. These potential record matches can then be subjected to a threshold test in order to determine one or more best matches. Additionally, signature-based similarity functions are used to improve the computational efficiency of the technique.

摘要翻译： 基于变换的记录匹配技术。 当通过采用显式输入用户定义的转换规则（例如，“Robert”和“Bob”）这样的事实来执行记录匹配时，该技术提供了一种灵活的方式来解释同义词和更一般的字符串等同形式 同义词）。 输入字符串和用户定义的转换规则用于生成在执行记录匹配时使用的较大的一组字符串。 可以使用用户定义的变换规则来转换数据库中的输入字符串和数据元素，以便生成更大的潜在记录匹配集合。 然后可以对这些潜在的记录匹配进行阈值测试，以确定一个或多个最佳匹配。 另外，使用基于签名的相似度函数来提高该技术的计算效率。