Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints
Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints
复制标题
DOI：
10.14778/1920841.1920992
复制
发表时间：
2010-09-01
影响因子：
2.5
通讯作者：
Li, Guoliang
中科院分区：
文献类型：
--
作者：
Wang, Jiannan;Feng, Jianhua;Li, Guoliang
字符串相似性连接可查找两个字符串集合之间的相似对。它是许多应用程序中必不可少的操作，例如数据集成和清理，并且最近引起了极大的关注。在本文中，我们研究具有编辑距离约束的字符串相似性连接。现有方法通常采用过滤和优化框架，存在以下缺点：（1）对于短字符串（平均字符串长度不大于30）的数据集效率低下； （二）涉及指标较大的； (3)它们支持数据集的动态更新是昂贵的。为了解决这些问题，我们提出了一种名为 trie-join 的新颖框架，它可以使用小索引有效地生成结果。我们使用 trie 结构来索引字符串，并利用 trie 结构基于 subtrie 剪枝有效地找到相似的字符串对。我们设计了高效的 trie 连接算法和修剪技术来实现高性能。我们的方法可以轻松扩展以有效支持数据集的动态更新。实验结果表明，我们的算法在三个具有短字符串的真实数据集上优于最先进的方法一个数量级。
A string similarity join finds similar pairs between two collections of strings. It is an essential operation in many applications, such as data integration and cleaning, and has attracted significant attention recently. In this paper, we study string similarity joins with edit-distance constraints. Existing methods usually employ a filter-and-refine framework and have the following disadvantages: (1) They are inefficient for the data sets with short strings (the average string length is no larger than 30); (2) They involve large indexes; (3) They are expensive to support dynamic update of data sets. To address these problems, we propose a novel framework called trie-join, which can generate results efficiently with small indexes. We use a trie structure to index the strings and utilize the trie structure to efficiently find the similar string pairs based on subtrie pruning. We devise efficient trie-join algorithms and pruning techniques to achieve high performance. Our method can be easily extended to support dynamic update of data sets efficiently. Experimental results show that our algorithms outperform state-of-the-art methods by an order of magnitude on three real data sets with short strings.