A fast projection algorithm for sequence data searching

摘要

In real life, data often appear in the form of sequences and this form of data is called sequence data. In this paper, a new definition on sequence similarity and a novel algorithm, Projection Algorithm, for sequence data searching are proposed. This algorithm is not required to access every datum in a sequence database. However, it guarantees that no qualified subsequence is falsely rejected. Moreover, the projection algorithm can be extended to match subsequences with different scales. With careful selection of parameters, most of the similar subsequences with different scales can be retrieved. We also show by experiments that the proposed algorithm can outperform the traditional sequential searching algorithm up to 96 times in terms of speed up.