Online piece-wise linear approximation of numerical streams with precision guarantees

Hazem Elmeleegy*, Ahmed K. Elmagarmid, Emmanuel Cecchet, Walid G. Aref, Willy Zwaenepoel

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

71 Citations (Scopus)

Abstract

Continuous "always-on" monitoring is beneficial for a number of applications, but potentially imposes a high load in terms of communication, storage and power consumption when a large number of variables need to be monitored. We introduce two new filtering techniques, swing filters and slide filters, that represent within a prescribed precision a time-varying numerical signal by a piecewise linear function, consisting of connected line segments for swing filters and (mostly) disconnected line segments for slide filters. We demonstrate the effectiveness of swing and slide filters in terms of their compression power by applying them to a reallife data set plus a variety of synthetic data sets. For nearly all combinations of signal behavior and precision requirements, the proposed techniques outperform the earlier approaches for online filtering in terms of data reduction. The slide filter, in particular, consistently dominates all other filters, with up to twofold improvement over the best of the previous techniques.

Original languageEnglish
Pages (from-to)145-156
Number of pages12
JournalProceedings of the VLDB Endowment
Volume2
Issue number1
DOIs
Publication statusPublished - 2009
Externally publishedYes

Fingerprint

Dive into the research topics of 'Online piece-wise linear approximation of numerical streams with precision guarantees'. Together they form a unique fingerprint.

Cite this