Trie-join: a trie-based method for efficient string similarity joins
Trie-join: a trie-based method for efficient string similarity joins
复制标题
Trie-join：一种基于 trie 的高效字符串相似性连接方法
DOI：
10.1007/s00778-011-0252-8
复制
发表时间：
2012-08-01
期刊：
影响因子：
4.2
通讯作者：
Li, Guoliang
中科院分区：
文献类型：
--
作者：
Feng, Jianhua;Wang, Jiannan;Li, Guoliang
字符串相似性连接可查找两个字符串集合之间的相似对。许多应用程序（例如数据集成和清理）可以从高效的字符串相似性连接算法中受益匪浅。在本文中，我们研究具有编辑距离约束的字符串相似性连接。现有方法通常采用filter-and-refine框架，但存在以下局限性：（1）对于短字符串（平均字符串长度不大于30）的数据集效率低下； （二）涉及指标较大的； (3)它们支持数据集的动态更新是昂贵的。为了解决这些问题，我们提出了一种称为trie-join的新方法，它可以使用小索引有效地生成结果。我们使用 trie 结构来索引字符串，并利用 trie 结构基于 subtrie 剪枝有效地找到相似的字符串对。我们设计了高效的 trie 连接算法和修剪技术来实现高性能。我们的方法可以轻松扩展以有效支持数据集的动态更新。我们对四个真实数据集进行了广泛的实验。实验结果表明，我们的算法在短字符串数据集上的性能优于最先进的方法一个数量级。
A string similarity join finds similar pairs between two collections of strings. Many applications, e.g., data integration and cleaning, can significantly benefit from an efficient string-similarity-join algorithm. In this paper, we study string similarity joins with edit-distance constraints. Existing methods usually employ afilter-and-refineframework and suffer from the following limitations: (1) They are inefficient for the data sets with short strings (the average string length is not 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 method calledtrie-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 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. We conducted extensive experiments on four real data sets. Experimental results show that our algorithms outperform state-of-the-art methods by an order of magnitude on the data sets with short strings.