Efficiently Supporting Edit Distance Based String Similarity Search Using B+-Trees
Efficiently Supporting Edit Distance Based String Similarity Search Using B+-Trees
复制标题
使用 B 树有效支持基于编辑距离的字符串相似性搜索
DOI：
10.1109/tkde.2014.2309131
复制
发表时间：
2014-12-01
影响因子：
8.9
通讯作者：
Ooi, Beng Chin
中科院分区：
文献类型：
--
作者：
Lu, Wei;Du, Xiaoyong;Ooi, Beng Chin
编辑距离被广泛用于度量两个字符串之间的相似性。基于编辑距离的字符串相似性搜索作为一种基本操作，是利用编辑距离在集合中查找与给定查询字符串相似的字符串。现有的方法回答这样的字符串相似性查询遵循过滤和验证框架，通过使用各种索引。通常，大多数方法都假设索引和数据集在主存中维护。为了克服这一限制，在本文中，我们提出了B+树为基础的方法来回答基于编辑距离的字符串相似性查询，因此，我们的方法可以很容易地集成到现有的RDBMS。在一般情况下，我们回答字符串相似性搜索使用修剪技术在度量空间中，编辑距离是一个度量。首先，我们根据一组引用字符串将字符串集合拆分为多个分区。然后，我们使用单个B+树根据这些字符串到其对应的参考字符串的距离来索引所有分区中的字符串。最后，基于B+-树，提出了两种分别有效回答范围查询和KNN查询的方法.我们证明了数据集的最优划分是一个NP-难问题，因此提出了一种启发式方法来选择参考字符串greetings，并提出了一个最优的分区分配策略，以尽量减少预期的字符串数量，需要验证在查询评估。通过对各种真实的数据集进行广泛的实验，我们证明了我们的B+树为基础的方法提供了上级性能超过国家的最先进的技术范围和KNN查询在大多数情况下。
Edit distance is widely used for measuring the similarity between two strings. As a primitive operation, edit distance based string similarity search is to find strings in a collection that are similar to a given query string using edit distance. Existing approaches for answering such string similarity queries follow the filter-and-verify framework by using various indexes. Typically, most approaches assume that indexes and data sets are maintained in main memory. To overcome this limitation, in this paper, we propose B+-tree based approaches to answer edit distance based string similarity queries, and hence, our approaches can be easily integrated into existing RDBMSs. In general, we answer string similarity search using pruning techniques employed in the metric space in that edit distance is a metric. First, we split the string collection into partitions according to a set of reference strings. Then, we index strings in all partitions using a single B+-tree based on the distances of these strings to their corresponding reference strings. Finally, we propose two approaches to efficiently answer range and KNN queries, respectively, based on the B+-tree. We prove that the optimal partitioning of the data set is an NP-hard problem, and therefore propose a heuristic approach for selecting the reference strings greedily and present an optimal partition assignment strategy to minimize the expected number of strings that need to be verified during the query evaluation. Through extensive experiments over a variety of real data sets, we demonstrate that our B+-tree based approaches provide superior performance over state-of-the-art techniques on both range and KNN queries in most cases.