Speeding-up the similarity search in time series databases by coupling dimensionality reduction techniques with a fast-and-dirty filter

Muhammad Marwan Muhammad Fuad, Pierre François Marteau

Research output: Chapter in Book/Report/Conference proceedingConference proceeding

7 Citations (Scopus)

Abstract

In this paper we present a new generic frame that boosts the performance of different time series dimensionality reduction techniques by using a fast-and-dirty filter that we combine with the lower bounding condition of the dimensionality reduction technique to increase the pruning power. This fast-and-dirty filter is based on an optimal approximation of the segmented time series. The distances between these segmented time series and their approximating functions are computed and stored at indexing-time. This step is repeated using different resolution levels which correspond to different lengths of the segments. At query-time these pre-computed distances are utilized to prune those time series which are not similar to the given pattern using the least number of query-time distance computations. We conduct experiments that validate the theoretical basis of our proposed method.

Original languageEnglish
Title of host publicationProceedings - 2010 IEEE 4th International Conference on Semantic Computing, ICSC 2010
PublisherIEEE
Pages101-104
Number of pages4
ISBN (Print)9780769541549
DOIs
Publication statusPublished - 11 Nov 2010
Externally publishedYes
Event4th IEEE International Conference on Semantic Computing, ICSC 2010 - Pittsburgh, PA, United States
Duration: 22 Sep 201024 Sep 2010

Publication series

NameProceedings - 2010 IEEE 4th International Conference on Semantic Computing, ICSC 2010

Conference

Conference4th IEEE International Conference on Semantic Computing, ICSC 2010
CountryUnited States
CityPittsburgh, PA
Period22/09/1024/09/10

Fingerprint

Similarity Search
Dimensionality Reduction
Time series
Filter
Query
Optimal Approximation
Pruning
Indexing
Experiment
Experiments

Keywords

  • Dimensionality reduction techniques
  • Multi-resolution
  • Similarity search
  • Time series data mining

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Theoretical Computer Science

Cite this

Muhammad Fuad, M. M., & Marteau, P. F. (2010). Speeding-up the similarity search in time series databases by coupling dimensionality reduction techniques with a fast-and-dirty filter. In Proceedings - 2010 IEEE 4th International Conference on Semantic Computing, ICSC 2010 (pp. 101-104). [5628900] (Proceedings - 2010 IEEE 4th International Conference on Semantic Computing, ICSC 2010). IEEE. https://doi.org/10.1109/ICSC.2010.34

Speeding-up the similarity search in time series databases by coupling dimensionality reduction techniques with a fast-and-dirty filter. / Muhammad Fuad, Muhammad Marwan; Marteau, Pierre François.

Proceedings - 2010 IEEE 4th International Conference on Semantic Computing, ICSC 2010. IEEE, 2010. p. 101-104 5628900 (Proceedings - 2010 IEEE 4th International Conference on Semantic Computing, ICSC 2010).

Research output: Chapter in Book/Report/Conference proceedingConference proceeding

Muhammad Fuad, MM & Marteau, PF 2010, Speeding-up the similarity search in time series databases by coupling dimensionality reduction techniques with a fast-and-dirty filter. in Proceedings - 2010 IEEE 4th International Conference on Semantic Computing, ICSC 2010., 5628900, Proceedings - 2010 IEEE 4th International Conference on Semantic Computing, ICSC 2010, IEEE, pp. 101-104, 4th IEEE International Conference on Semantic Computing, ICSC 2010, Pittsburgh, PA, United States, 22/09/10. https://doi.org/10.1109/ICSC.2010.34
Muhammad Fuad MM, Marteau PF. Speeding-up the similarity search in time series databases by coupling dimensionality reduction techniques with a fast-and-dirty filter. In Proceedings - 2010 IEEE 4th International Conference on Semantic Computing, ICSC 2010. IEEE. 2010. p. 101-104. 5628900. (Proceedings - 2010 IEEE 4th International Conference on Semantic Computing, ICSC 2010). https://doi.org/10.1109/ICSC.2010.34
Muhammad Fuad, Muhammad Marwan ; Marteau, Pierre François. / Speeding-up the similarity search in time series databases by coupling dimensionality reduction techniques with a fast-and-dirty filter. Proceedings - 2010 IEEE 4th International Conference on Semantic Computing, ICSC 2010. IEEE, 2010. pp. 101-104 (Proceedings - 2010 IEEE 4th International Conference on Semantic Computing, ICSC 2010).
@inproceedings{a7d702b713e74b418dff07084a342834,
title = "Speeding-up the similarity search in time series databases by coupling dimensionality reduction techniques with a fast-and-dirty filter",
abstract = "In this paper we present a new generic frame that boosts the performance of different time series dimensionality reduction techniques by using a fast-and-dirty filter that we combine with the lower bounding condition of the dimensionality reduction technique to increase the pruning power. This fast-and-dirty filter is based on an optimal approximation of the segmented time series. The distances between these segmented time series and their approximating functions are computed and stored at indexing-time. This step is repeated using different resolution levels which correspond to different lengths of the segments. At query-time these pre-computed distances are utilized to prune those time series which are not similar to the given pattern using the least number of query-time distance computations. We conduct experiments that validate the theoretical basis of our proposed method.",
keywords = "Dimensionality reduction techniques, Multi-resolution, Similarity search, Time series data mining",
author = "{Muhammad Fuad}, {Muhammad Marwan} and Marteau, {Pierre Fran{\cc}ois}",
year = "2010",
month = "11",
day = "11",
doi = "10.1109/ICSC.2010.34",
language = "English",
isbn = "9780769541549",
series = "Proceedings - 2010 IEEE 4th International Conference on Semantic Computing, ICSC 2010",
publisher = "IEEE",
pages = "101--104",
booktitle = "Proceedings - 2010 IEEE 4th International Conference on Semantic Computing, ICSC 2010",

}

TY - GEN

T1 - Speeding-up the similarity search in time series databases by coupling dimensionality reduction techniques with a fast-and-dirty filter

AU - Muhammad Fuad, Muhammad Marwan

AU - Marteau, Pierre François

PY - 2010/11/11

Y1 - 2010/11/11

N2 - In this paper we present a new generic frame that boosts the performance of different time series dimensionality reduction techniques by using a fast-and-dirty filter that we combine with the lower bounding condition of the dimensionality reduction technique to increase the pruning power. This fast-and-dirty filter is based on an optimal approximation of the segmented time series. The distances between these segmented time series and their approximating functions are computed and stored at indexing-time. This step is repeated using different resolution levels which correspond to different lengths of the segments. At query-time these pre-computed distances are utilized to prune those time series which are not similar to the given pattern using the least number of query-time distance computations. We conduct experiments that validate the theoretical basis of our proposed method.

AB - In this paper we present a new generic frame that boosts the performance of different time series dimensionality reduction techniques by using a fast-and-dirty filter that we combine with the lower bounding condition of the dimensionality reduction technique to increase the pruning power. This fast-and-dirty filter is based on an optimal approximation of the segmented time series. The distances between these segmented time series and their approximating functions are computed and stored at indexing-time. This step is repeated using different resolution levels which correspond to different lengths of the segments. At query-time these pre-computed distances are utilized to prune those time series which are not similar to the given pattern using the least number of query-time distance computations. We conduct experiments that validate the theoretical basis of our proposed method.

KW - Dimensionality reduction techniques

KW - Multi-resolution

KW - Similarity search

KW - Time series data mining

UR - http://www.scopus.com/inward/record.url?scp=79952062506&partnerID=8YFLogxK

U2 - 10.1109/ICSC.2010.34

DO - 10.1109/ICSC.2010.34

M3 - Conference proceeding

SN - 9780769541549

T3 - Proceedings - 2010 IEEE 4th International Conference on Semantic Computing, ICSC 2010

SP - 101

EP - 104

BT - Proceedings - 2010 IEEE 4th International Conference on Semantic Computing, ICSC 2010

PB - IEEE

ER -