2005 | OriginalPaper | Buchkapitel
Incremental DFT Based Search Algorithm for Similar Sequence
verfasst von : Quan Zheng, Zhikai Feng, Ming Zhu
Erschienen in: Fuzzy Systems and Knowledge Discovery
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This paper begins with a new algorithm for computing time sequence data expansion distance on the time domain that, with a time complexity of O(n×m), solves the problem of retained similarity after the shifting and scaling of time sequence on the Y axis. After this, another algorithm is proposed for computing time sequence data expansion distance on frequency domain and searching similar subsequence in long time sequence, with a time complexity of merely O(n×fc), suitable for online implementation for its high efficiency, and adaptable to the extended definition of time sequence data expansion distance. An incremental DFT algorithm is also provided for time sequence data and linear weighted time sequence data, which allows dimension reduction on each window of a long sequence, simplifying the traditional O(n×m×fc) to O(n×fc).