Towards Online Multi-model Approximation of Time Series

• Main Authors: Papaioannou, T. G., Riahi, M., Aberer, K.
• Format: Conference Proceeding
• Language: English
• Subjects: Approximation algorithms; Data models; efficient data management; error norm; Least squares approximation; Linear approximation; lossy compression; Piecewise linear approximation; regression; storage scheme; Time series analysis
• ISSN: 1551-6245; 2375-0324
• DOI: 10.1109/MDM.2011.57

The increasing use of sensor technology for various monitoring applications (e.g. air-pollution, traffic, climate-change, etc.) has led to an unprecedented volume of streaming data that has to be efficiently aggregated, stored and retrieved. Real-time model-based data approximation and filtering is a common solution for reducing the storage (and communication) overhead. However, the selection of the most efficient model depends on the characteristics of the data stream, namely rate, burstiness, data range, etc., which cannot be always known a priori for (mobile) sensors and they can even dynamically change. In this paper, we investigate the innovative concept of efficiently combining multiple approximation models in real-time. Our approach dynamically adapts to the properties of the data stream and approximates each data segment with the most suitable model. As experimentally proved, our multi-model approximation approach always produces fewer or equal data segments than those of the best individual model, and thus provably achieves higher data compression ratio than individual linear models.