Efficient Processing of Multiple DTW Queries in Time Series Databases

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

Standard

Efficient Processing of Multiple DTW Queries in Time Series Databases. / Kremer, Hardy; Günnemann, Stephan; Ivanescu, Anca-Maria; Assent, Ira; Seidl, Thomas.

In: Lecture Notes in Computer Science, Vol. 6809, 2011, p. 150-167.

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

Harvard

Kremer, H, Günnemann, S, Ivanescu, A-M, Assent, I & Seidl, T 2011, 'Efficient Processing of Multiple DTW Queries in Time Series Databases', Lecture Notes in Computer Science, vol. 6809, pp. 150-167. https://doi.org/10.1007/978-3-642-22351-8_9

APA

Kremer, H., Günnemann, S., Ivanescu, A-M., Assent, I., & Seidl, T. (2011). Efficient Processing of Multiple DTW Queries in Time Series Databases. Lecture Notes in Computer Science, 6809, 150-167. https://doi.org/10.1007/978-3-642-22351-8_9

CBE

Kremer H, Günnemann S, Ivanescu A-M, Assent I, Seidl T. 2011. Efficient Processing of Multiple DTW Queries in Time Series Databases. Lecture Notes in Computer Science. 6809:150-167. https://doi.org/10.1007/978-3-642-22351-8_9

MLA

Kremer, Hardy et al. "Efficient Processing of Multiple DTW Queries in Time Series Databases". Lecture Notes in Computer Science. 2011, 6809. 150-167. https://doi.org/10.1007/978-3-642-22351-8_9

Vancouver

Kremer H, Günnemann S, Ivanescu A-M, Assent I, Seidl T. Efficient Processing of Multiple DTW Queries in Time Series Databases. Lecture Notes in Computer Science. 2011;6809:150-167. https://doi.org/10.1007/978-3-642-22351-8_9

Author

Kremer, Hardy ; Günnemann, Stephan ; Ivanescu, Anca-Maria ; Assent, Ira ; Seidl, Thomas. / Efficient Processing of Multiple DTW Queries in Time Series Databases. In: Lecture Notes in Computer Science. 2011 ; Vol. 6809. pp. 150-167.

Bibtex

@inproceedings{f4e625337ce743a9b74f91caadc8fdc9,
title = "Efficient Processing of Multiple DTW Queries in Time Series Databases",
abstract = "Dynamic Time Warping (DTW) is a widely used distance measure for time series that has been successfully used in science and many other application domains. As DTW is computationally expensive, there is a strong need for efficient query processing algorithms. Such algorithms exist for single queries. In many of today{\textquoteright}s applications, however, large numbers of queries arise at any given time. Existing DTW techniques do not process multiple DTW queries simultaneously, a serious limitation which slows down overall processing. In this paper, we propose an efficient processing approach for multiple DTW queries. We base our approach on the observation that algorithms in areas such as data mining and interactive visualization incur many queries that share certain characteristics. Our solution exploits these shared characteristics by pruning database time series with respect to sets of queries, and we prove a lower-bounding property that guarantees no false dismissals. Our technique can be flexibly combined with existing DTW lower bounds or other single DTW query speed-up techniques for further runtime reduction. Our thorough experimental evaluation demonstrates substantial performance gains for multiple DTW queries. ",
author = "Hardy Kremer and Stephan G{\"u}nnemann and Anca-Maria Ivanescu and Ira Assent and Thomas Seidl",
note = "Title of the vol.: Scientific and Statistical Database Management. Proceedings / Judith Bayard Cushing, James French and Shawn Bowers (eds.) ISBN: 978-3-642-22350-1; 23rd Scientific and Statistical Database Management Conference. SSDBM 2011 ; Conference date: 20-07-2011 Through 22-07-2011",
year = "2011",
doi = "10.1007/978-3-642-22351-8_9",
language = "English",
volume = "6809",
pages = "150--167",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Springer",

}

RIS

TY - GEN

T1 - Efficient Processing of Multiple DTW Queries in Time Series Databases

AU - Kremer, Hardy

AU - Günnemann, Stephan

AU - Ivanescu, Anca-Maria

AU - Assent, Ira

AU - Seidl, Thomas

N1 - Title of the vol.: Scientific and Statistical Database Management. Proceedings / Judith Bayard Cushing, James French and Shawn Bowers (eds.) ISBN: 978-3-642-22350-1

PY - 2011

Y1 - 2011

N2 - Dynamic Time Warping (DTW) is a widely used distance measure for time series that has been successfully used in science and many other application domains. As DTW is computationally expensive, there is a strong need for efficient query processing algorithms. Such algorithms exist for single queries. In many of today’s applications, however, large numbers of queries arise at any given time. Existing DTW techniques do not process multiple DTW queries simultaneously, a serious limitation which slows down overall processing. In this paper, we propose an efficient processing approach for multiple DTW queries. We base our approach on the observation that algorithms in areas such as data mining and interactive visualization incur many queries that share certain characteristics. Our solution exploits these shared characteristics by pruning database time series with respect to sets of queries, and we prove a lower-bounding property that guarantees no false dismissals. Our technique can be flexibly combined with existing DTW lower bounds or other single DTW query speed-up techniques for further runtime reduction. Our thorough experimental evaluation demonstrates substantial performance gains for multiple DTW queries.

AB - Dynamic Time Warping (DTW) is a widely used distance measure for time series that has been successfully used in science and many other application domains. As DTW is computationally expensive, there is a strong need for efficient query processing algorithms. Such algorithms exist for single queries. In many of today’s applications, however, large numbers of queries arise at any given time. Existing DTW techniques do not process multiple DTW queries simultaneously, a serious limitation which slows down overall processing. In this paper, we propose an efficient processing approach for multiple DTW queries. We base our approach on the observation that algorithms in areas such as data mining and interactive visualization incur many queries that share certain characteristics. Our solution exploits these shared characteristics by pruning database time series with respect to sets of queries, and we prove a lower-bounding property that guarantees no false dismissals. Our technique can be flexibly combined with existing DTW lower bounds or other single DTW query speed-up techniques for further runtime reduction. Our thorough experimental evaluation demonstrates substantial performance gains for multiple DTW queries.

U2 - 10.1007/978-3-642-22351-8_9

DO - 10.1007/978-3-642-22351-8_9

M3 - Conference article

VL - 6809

SP - 150

EP - 167

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

T2 - 23rd Scientific and Statistical Database Management Conference. SSDBM 2011

Y2 - 20 July 2011 through 22 July 2011

ER -