Multi-resolution approach to time series retrieval

Muhammad Marwan Muhammad Fuad, Pierre François Marteau

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

1 Citation (Scopus)

Abstract

We propose a new multi-resolution indexing and retrieval method of the similarity search problem in time series databases. The proposed method is based on a fast-and-dirty filtering scheme that iteratively reduces the search space using several resolution levels. For each resolution level the time series are approximated by an appropriate function. The distance between the time series and the approximating function is computed and stored at indexing-time. At query-time, assigned filters use these precomputed distances to exclude wide regions of the search space, which do not contain answers to the query, using the least number of query-time distance computations. The resolution level is progressively increased to converge towards higher resolution levels where the exclusion power rises, but the cost of query-time distance computations also increases. The proposed method uses lower bounding distances, so there are no false dismissals, and the search process returns all the possible answers to the query. A post-processing scanning on the candidate response set is performed to filter out any false alarms and return the final response set. We present experimentations that compare our method with sequential scanning on different datasets, using different threshold values and different approximating functions. The experiments show that our new method is faster than sequential scanning by an order of magnitude.

Original languageEnglish
Title of host publicationProceedings of the 14th International Database Engineering and Applications Symposium, IDEAS '10
PublisherACM
Pages136-142
Number of pages7
ISBN (Print)9781605589008
DOIs
Publication statusPublished - 15 Dec 2010
Externally publishedYes
Event14th International Database Engineering and Applications Symposium, IDEAS '10 - Montreal, QC, Canada
Duration: 16 Aug 201018 Aug 2010

Publication series

NameACM International Conference Proceeding Series

Conference

Conference14th International Database Engineering and Applications Symposium, IDEAS '10
CountryCanada
CityMontreal, QC
Period16/08/1018/08/10

Fingerprint

Time series
Scanning
Processing
Costs
Experiments

Keywords

  • Metric spaces
  • MIR
  • Multi-resolution
  • Sequential scanning
  • Time series information retrieval

ASJC Scopus subject areas

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications

Cite this

Fuad, M. M. M., & Marteau, P. F. (2010). Multi-resolution approach to time series retrieval. In Proceedings of the 14th International Database Engineering and Applications Symposium, IDEAS '10 (pp. 136-142). (ACM International Conference Proceeding Series). ACM. https://doi.org/10.1145/1866480.1866501

Multi-resolution approach to time series retrieval. / Fuad, Muhammad Marwan Muhammad; Marteau, Pierre François.

Proceedings of the 14th International Database Engineering and Applications Symposium, IDEAS '10. ACM, 2010. p. 136-142 (ACM International Conference Proceeding Series).

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

Fuad, MMM & Marteau, PF 2010, Multi-resolution approach to time series retrieval. in Proceedings of the 14th International Database Engineering and Applications Symposium, IDEAS '10. ACM International Conference Proceeding Series, ACM, pp. 136-142, 14th International Database Engineering and Applications Symposium, IDEAS '10, Montreal, QC, Canada, 16/08/10. https://doi.org/10.1145/1866480.1866501
Fuad MMM, Marteau PF. Multi-resolution approach to time series retrieval. In Proceedings of the 14th International Database Engineering and Applications Symposium, IDEAS '10. ACM. 2010. p. 136-142. (ACM International Conference Proceeding Series). https://doi.org/10.1145/1866480.1866501
Fuad, Muhammad Marwan Muhammad ; Marteau, Pierre François. / Multi-resolution approach to time series retrieval. Proceedings of the 14th International Database Engineering and Applications Symposium, IDEAS '10. ACM, 2010. pp. 136-142 (ACM International Conference Proceeding Series).
@inproceedings{35a7145bb1184140a778ace1b5791609,
title = "Multi-resolution approach to time series retrieval",
abstract = "We propose a new multi-resolution indexing and retrieval method of the similarity search problem in time series databases. The proposed method is based on a fast-and-dirty filtering scheme that iteratively reduces the search space using several resolution levels. For each resolution level the time series are approximated by an appropriate function. The distance between the time series and the approximating function is computed and stored at indexing-time. At query-time, assigned filters use these precomputed distances to exclude wide regions of the search space, which do not contain answers to the query, using the least number of query-time distance computations. The resolution level is progressively increased to converge towards higher resolution levels where the exclusion power rises, but the cost of query-time distance computations also increases. The proposed method uses lower bounding distances, so there are no false dismissals, and the search process returns all the possible answers to the query. A post-processing scanning on the candidate response set is performed to filter out any false alarms and return the final response set. We present experimentations that compare our method with sequential scanning on different datasets, using different threshold values and different approximating functions. The experiments show that our new method is faster than sequential scanning by an order of magnitude.",
keywords = "Metric spaces, MIR, Multi-resolution, Sequential scanning, Time series information retrieval",
author = "Fuad, {Muhammad Marwan Muhammad} and Marteau, {Pierre Fran{\cc}ois}",
year = "2010",
month = "12",
day = "15",
doi = "10.1145/1866480.1866501",
language = "English",
isbn = "9781605589008",
series = "ACM International Conference Proceeding Series",
publisher = "ACM",
pages = "136--142",
booktitle = "Proceedings of the 14th International Database Engineering and Applications Symposium, IDEAS '10",
address = "United States",

}

TY - GEN

T1 - Multi-resolution approach to time series retrieval

AU - Fuad, Muhammad Marwan Muhammad

AU - Marteau, Pierre François

PY - 2010/12/15

Y1 - 2010/12/15

N2 - We propose a new multi-resolution indexing and retrieval method of the similarity search problem in time series databases. The proposed method is based on a fast-and-dirty filtering scheme that iteratively reduces the search space using several resolution levels. For each resolution level the time series are approximated by an appropriate function. The distance between the time series and the approximating function is computed and stored at indexing-time. At query-time, assigned filters use these precomputed distances to exclude wide regions of the search space, which do not contain answers to the query, using the least number of query-time distance computations. The resolution level is progressively increased to converge towards higher resolution levels where the exclusion power rises, but the cost of query-time distance computations also increases. The proposed method uses lower bounding distances, so there are no false dismissals, and the search process returns all the possible answers to the query. A post-processing scanning on the candidate response set is performed to filter out any false alarms and return the final response set. We present experimentations that compare our method with sequential scanning on different datasets, using different threshold values and different approximating functions. The experiments show that our new method is faster than sequential scanning by an order of magnitude.

AB - We propose a new multi-resolution indexing and retrieval method of the similarity search problem in time series databases. The proposed method is based on a fast-and-dirty filtering scheme that iteratively reduces the search space using several resolution levels. For each resolution level the time series are approximated by an appropriate function. The distance between the time series and the approximating function is computed and stored at indexing-time. At query-time, assigned filters use these precomputed distances to exclude wide regions of the search space, which do not contain answers to the query, using the least number of query-time distance computations. The resolution level is progressively increased to converge towards higher resolution levels where the exclusion power rises, but the cost of query-time distance computations also increases. The proposed method uses lower bounding distances, so there are no false dismissals, and the search process returns all the possible answers to the query. A post-processing scanning on the candidate response set is performed to filter out any false alarms and return the final response set. We present experimentations that compare our method with sequential scanning on different datasets, using different threshold values and different approximating functions. The experiments show that our new method is faster than sequential scanning by an order of magnitude.

KW - Metric spaces

KW - MIR

KW - Multi-resolution

KW - Sequential scanning

KW - Time series information retrieval

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

U2 - 10.1145/1866480.1866501

DO - 10.1145/1866480.1866501

M3 - Conference proceeding

SN - 9781605589008

T3 - ACM International Conference Proceeding Series

SP - 136

EP - 142

BT - Proceedings of the 14th International Database Engineering and Applications Symposium, IDEAS '10

PB - ACM

ER -