A Research On Finding The Conjunct Motif Of Series

The conjunct motif of series has many important applications in modern life. The conjunct motif of discrete series is applied in the applications like information retrieval, genetic sequences matching and so on. The conjunct motif of continuous series is applied in the applications like stock prediction, audio recognition and so on. The conjunct motif of series has wide applications so that more and more researchers pay attention to it.Computing the conjunct motif of discrete series is always referred to the multiple longest common subsequence problem. It is a famous NP-hard problem. Although some exact algorithms have reduced the computing complexity as much as possible, getting the exact solutions still cost much more time with the increasing of data scale. The approximate algorithms have low computing complexity but the amount of solutions is small. The loss of information is large.Computing the conjunct motif of continuous series is always referred to computing the center average of time series. The Dynamic Time Warping (DTW) is applied to judge the similarity degree between two time series. But with the amount of the series increasing, the computing complexity is increasing in exponential growth. Thus it is also a NP-hard problem.In this paper, we review some related works from others and introduce the main ideas of some algorithms. In the aspect of the conjunct motif of discrete series, we present a new algorithm for computing the conjunct lattice among several discrete series by applying lattice data structure. Furthermore, the algorithm can also be applied to compute the longest common subsequence approximately. The algorithm apply a local merging strategy and use lattice to store the information through the merging process. And verify the solutions gotten from our algorithm have the advantages in accuracy and amount through the experiment. In the aspect of the conjunct motif of continuous series, we present a new algorithm based on DTW Barycenter Averaging (DBA) algorithm to obtain a center average. Our algorithm apply a several initial series method and a hierarchical merge strategy with nearest neighbor principle and min-max principle to make the solution more similar with the known series. Through the experiment data, our algorithm has a better performance on the series similarity.