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 proceedingpeer-review

8 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, United States
Duration: 22 Sept 201024 Sept 2010

Publication series

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

Conference

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

Keywords

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

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Theoretical Computer Science

Fingerprint

Dive into the research topics of 'Speeding-up the similarity search in time series databases by coupling dimensionality reduction techniques with a fast-and-dirty filter'. Together they form a unique fingerprint.

Cite this