MinSearch: An Efficient Algorithm for Similarity Search under Edit Distance - CrossMinds.ai
MinSearch: An Efficient Algorithm for Similarity Search under Edit Distance
Aug 13, 20209 views
Haoyu Zhang
We study a fundamental problem in data analytics: similarity search,under edit distance (or,,edit similarity search,for short). In this problem we try to build an index on a set of,n,strings,S,=,{,s,1,,...,,s,n,},,,with the goal of answering the following two types of queries: (1),the,threshold,query: given a query string,t,and a threshold,K,, output,all,s,i,∈,S,such that the edit distance between,s,i,and,t,is at most,K,; (2) the,topk,query: given a query string,t,, output the,k,strings,in,S,that are closest to,t,in terms of edit distance. Edit similarity,search has numerous applications in bioinformatics, databases, data,mining, information retrieval, etc., and has been studied extensively,in the literature.,In this paper we propose a novel algorithm for edit similarity,search named,MinSearch,. The algorithm is randomized, and we,can show mathematically that it outputs the correct answer with,high probability for both types of queries. We have conducted an,extensive set of experiments on,MinSearch,, and compared it with,the best existing algorithms for edit similarity search. Our experiments show that,MinSearch,has a clear advantage (often in orders,of magnitudes) against the best previous algorithms in query time,,and,MinSearch,is always one of the best among all competitors,in the indexing time and space usage. Finally,,MinSearch,achieves,perfect accuracy for both types of queries on all datasets that we,have tested.