Efficient algorithms for similarity search
The problem of our interest takes as input a database of m sequences from an alphabet Sigma and an integer k. The goal is to report all the pairs of sequences that have a matching subsequence of length at least k. We employ two algorithms to solve this problem. The first algorithm is based on sorting and the second is based on generalized suffix trees. We provide experimental data comparing the performances of these algorithms. The generalized suffix tree based algorithm performs better than the sorting based algorithm.
generalized suffix tree (gst) color set size (css) quick sort radix sort