lnu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Efficient Dynamic Time Warping for Big Data Streams
Linnaeus University, Faculty of Technology, Department of computer science and media technology (CM). (ISOVIS)ORCID iD: 0000-0002-2901-935X
Linnaeus University, Faculty of Technology, Department of computer science and media technology (CM). (ISOVIS, DISA, VAESS)ORCID iD: 0000-0002-0519-2537
2019 (English)In: Proceedings of the IEEE International Conference on Big Data (Big Data '18): Workshop on Real-time & Stream Analytics in Big Data & Stream Data Management / [ed] Abe, N; Liu, H; Pu, C; Hu, X; Ahmed, N; Qiao, M; Song, Y; Kossmann, D; Liu, B; Lee, K; Tang, J; He, J; Saltz, J, IEEE, 2019, p. 2924-2929Conference paper, Published paper (Refereed)
Abstract [en]

Many common data analysis and machine learning algorithms for time series, such as classification, clustering, or dimensionality reduction, require a distance measurement between pairs of time series in order to determine their similarity. A variety of measures can be found in the literature, each with their own strengths and weaknesses, but the Dynamic Time Warping (DTW) distance measure has occupied an important place since its early applications for the analysis and recognition of spoken word. The main disadvantage of the DTW algorithm is, however, its quadratic time and space complexity, which limits its practical use to relatively small time series. This issue is even more problematic when dealing with streaming time series that are continuously updated, since the analysis must be re-executed regularly and with strict running time constraints. In this paper, we describe enhancements to the DTW algorithm that allow it to be used efficiently in a streaming scenario by supporting an append operation for new time steps with a linear complexity when an exact, error-free DTW is needed, and even better performance when either a Sakoe-Chiba band is used, or when a sliding window is the desired range for the data. Our experiments with one synthetic and four natural data sets have shown that it outperforms other DTW implementations and the potential errors are, in general, much lower than another state-of-the-art approximated DTW technique.

Place, publisher, year, edition, pages
IEEE, 2019. p. 2924-2929
Series
IEEE International Conference on Big Data, ISSN 2639-1589
Keywords [en]
time series, dynamic time warping, streaming
National Category
Computer Sciences
Research subject
Computer Science, Information and software visualization
Identifiers
URN: urn:nbn:se:lnu:diva-78735DOI: 10.1109/BigData.2018.8621878ISI: 000468499303001Scopus ID: 2-s2.0-85062589330ISBN: 978-1-5386-5035-6 (electronic)ISBN: 978-1-5386-5036-3 (print)OAI: oai:DiVA.org:lnu-78735DiVA, id: diva2:1261634
Conference
3rd Workshop on Real-time & Stream Analytics in Big Data & Stream Data Management at IEEE Big Data '18, 10-13 December, 2018, Seattle, USA
Available from: 2018-11-08 Created: 2018-11-08 Last updated: 2019-08-29Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Martins, Rafael MessiasKerren, Andreas

Search in DiVA

By author/editor
Martins, Rafael MessiasKerren, Andreas
By organisation
Department of computer science and media technology (CM)
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 123 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf