A Comparison of DFT and DWT Based Similarity Search in Time-SeriesDatabases

Report ID: 
2000-08
Authors: 
Y. Wu, D. Agrawal, and A. El Abbadi
Date: 
2000-05-01 05:00:00

Abstract

Similarity search in time-series databases has received significant attentionlately. Popular techniques for efficient retrieval of time sequences intime-series databases has been to use Discrete Fourier Transform (DFT).Recently, the Discrete Wavelet Transform (DWT) has gained popular interest indatabase domain and several proposals have been made to replace DFT by DWT forsimilarity search over time-series databases. In this paper, we explore thefeasibility of replacing DFT by DWT with a comprehensive analysis of the DFTand DWT as matching functions in time-series databases. Our results show thatalthough the DWT based technique has several advantages, e.g., the DWT hascomplexity of O(N) whereas DFT is O(N log N), DWT does not reduce relativematching error and does not increase query precision in similarity search assuggested by previous works. We conclude that, by exploring the conjugateproperty of DFT in real domain, the DFT-based and DWT-based techniques yieldcomparable results on similarity search in time-series databases.

Document

File 2000-08.ps