A unified framework for string similarity search with edit-distance constraint
A unified framework for string similarity search with edit-distance constraint
复制标题
具有编辑距离约束的字符串相似性搜索的统一框架
DOI：
10.1007/s00778-016-0449-y
复制
发表时间：
2017-04
期刊：
影响因子：
--
通讯作者：
Yong Zhang
中科院分区：
文献类型：
--
作者：
Minghe Yu;Jin Wang;Guoliang Li;Yong Zhang
字符串相似性搜索是数据清洗和集成的基本操作。它有两种变体：基于阈值的字符串相似性搜索和顶级字符串相似性搜索。现有的算法是有效的，无论是前者或后者，他们中的大多数不能同时支持这两个变种。为了解决这个问题，我们提出了一个统一的框架。我们首先递归地将字符串划分为不相交的段，并在段的顶部构建一个分层段树索引（）。然后，我们利用该算法来支持相似性搜索.对于基于阈值的搜索，我们确定适当的树节点的阈值的基础上回答查询，并设计了一个有效的算法（HS-Search）。对于顶部搜索，我们确定有前途的字符串有很大的可能性是类似的查询，利用这些字符串估计的上限，这是用来修剪不相似的字符串，并提出了一个算法（HS-Topk）。我们开发有效的修剪技术，以进一步提高性能。为了支持大型数据集，我们扩展我们的技术，以支持基于磁盘的设置。在真实数据集上的实验结果表明，我们的方法在这两个问题上都取得了很高的性能，比现有算法的性能提高了5-10倍。
String similarity search is a fundamental operation in data cleaning and integration. It has two variants: threshold-based string similarity search and top-string similarity search. Existing algorithms are efficient for either the former or the latter; most of them cannot support both two variants. To address this limitation, we propose a unified framework. We first recursively partition strings into disjoint segments and build a hierarchical segment tree index () on top of the segments. Then, we utilize theto support similarity search. For threshold-based search, we identify appropriate tree nodes based on the threshold to answer the query and devise an efficient algorithm (HS-Search). For top-search, we identify promising strings with large possibility to be similar to the query, utilize these strings to estimate an upper bound which is used to prune dissimilar strings and propose an algorithm (HS-Topk). We develop effective pruning techniques to further improve the performance. To support large data sets, we extend our techniques to support the disk-based setting. Experimental results on real-world data sets show that our method achieves high performance on the two problems and outperforms state-of-the-art algorithms by 5–10 times.
登录
查看更多内容
DOI：
10.1145/2588555.2593675
发表时间：
2014-06
期刊：
Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data
影响因子：
--
作者：
Dong Deng;Guoliang Li;Jianhua Feng
通讯作者：
Dong Deng;Guoliang Li;Jianhua Feng
影响因子：
2.5
作者：
Wang, Jiannan;Feng, Jianhua;Li, Guoliang
通讯作者：
Li, Guoliang
DOI：
10.1145/2457317.2457385
发表时间：
2013-03
期刊：
--
影响因子：
--
作者：
Stefan Gerdjikov;S. Mihov;Petar Mitankin;K. Schulz
通讯作者：
Stefan Gerdjikov;S. Mihov;Petar Mitankin;K. Schulz
DOI：
10.1145/2463676.2465324
发表时间：
2013-06
期刊：
--
影响因子：
--
作者：
Younghoon Kim;Kyuseok Shim
通讯作者：
Younghoon Kim;Kyuseok Shim
DOI：
--
发表时间：
2015
期刊：
--
影响因子：
--
作者：
通讯作者：
--