Dimensionality Reduction in Time Series: A PLA-Block-Sorting Method

Bachir Boucheham

Department of Informatics, University of Skikda , Algeria

Abstract: We address the data reduction in time series problem through a combination of two newly developed algorithms. The first is a modified version of the Douglas-Peucker Algorithm (DPA) for short-term redundancy reduction. The second is an alternative to the classical statistic methods for long-term redundancy reduction and is based on block sorting. The block sorting technique is inspired from the quite recent Burrows and Wheeler Algorithm (BWA). The novel reduction scheme was applied to the ECG time series using the MITBIH public ECG database. Results show that the novel scheme is highly competitive with respect to the most performant existing techniques (SPIHT, TSVD, CCSP-ORD-VLC and others).

Keywords: Data reduction, time series, long-term compression,Douglas-Peucker algorithm, block sorting.

Received February 2, 2006; accepted April 16, 2006