Skip to the content

Improving similarity search in time series using wavelets

Liabotis, I, Theodoulidis, B and Saraee, M 2006, 'Improving similarity search in time series using wavelets' , International Journal of Data Warehousing and Mining, 2 (2) , pp. 1116-1137.

[img] PDF - Published Version
Restricted to Repository staff only

Download (1116kB) | Request a copy

    Abstract

    Sequences constitute a large portion of data stored in databases. Data mining applications require the ability to process similarity queries over a large amount of time series data. The query processing performance is an important factor that needs to be taken into consideration. This article proposes a similarity retrieval algorithm for time series. The proposed approach utilizes wavelet transformation in order to reduce the dimensionality of the time series. The transformed series are indexed using X-Trees, which is a spatial indexing technique able to efficiently index high-dimensional data. The article proves that this technique outperforms the usage of the Fourier transformation, since the wavelet transformation provides better approximation of the time series. Through the experiments, it can be concluded that the optimum performance is obtained using 16 to 20 wavelet coefficients. Furthermore, a novel mechanism for reducing the complexity of the calculation for the false alarms removal is proposed. Storing the approximation coefficients of the penultimate level of the decomposition tree, the Euclidean distance between the two sequences is calculated, thus reducing further the number of false alarms before calculating the actual Euclidean distance using the complete time series. The article concludes with a detailed performance evaluation of the proposed similarity retrieval algorithm using data from the Greek stock market and the temperature measurements from Athens. The comparison is done with techniques that use the Haar transform and the R*-Tree, and the proposed algorithm is shown to outperform them.

    Item Type: Article
    Themes: Memory, Text and Place
    Schools: Colleges and Schools > College of Science & Technology > School of Computing, Science and Engineering > Data Mining and Pattern Recognition Research Centre
    Journal or Publication Title: International Journal of Data Warehousing and Mining
    Publisher: IGI Global
    Refereed: Yes
    ISSN: 1548-3924
    Related URLs:
    Depositing User: Dr Mo Saraee
    Date Deposited: 21 Oct 2011 12:25
    Last Modified: 20 Aug 2013 18:15
    URI: http://usir.salford.ac.uk/id/eprint/18598

    Actions (login required)

    Edit record (repository staff only)

    Downloads per month over past year

    View more statistics