An Efficient Algorithm for Finding the Most Similar Sequence on the Manhattan Distance Model
Hsiu-Chieh Hung, Chang‐Biau Yang, Kuo-Si Huang · 2019
Since the similarity (such as LCS, DTW) calculation of two given sequences usually requires quadratic time, sequential search is time-consuming for finding the most similar sequence in a database. This paper discusses the searching probability of a sequence and proposes a method for determining the searching order to reduce the searching time. On the Manhattan distance model, the searching probability of a query sequence is calculated for selecting the next compared sequence. Accordingly, the third and the subsequent compared sequences can be determined. Hence, a searching strategy of parameter ⟨0.81, 1⟩ is proposed for finding the most similar sequence, where 0.81 and 1 indicate the multipliers of the edit distance between the reference sequence and the query sequence, respectively. Our searching strategy considers the triangle inequality of the edit distance for accelerating the searching efficiency by pruning some unnecessary sequences away.