Coresets for Data Discretization and Sine Wave Fitting

Abstract

In the monitoring problem, the input is an unbounded stream P=p_1,p_2 of integers in [N]:=\1,,N\, that are obtained from a sensor (such as GPS or heart beats of a human). The goal (e.g., for anomaly detection) is to approximate the n points received so far in P by a single frequency , e.g. _c Ccost(P,c)+(c), where cost(P,c)=_i=1^n ^2(2N p_ic), C [N] is a feasible set of solutions, and is a given regularization function. For any approximation error >0, we prove that every set P of n integers has a weighted subset S P (sometimes called core-set) of cardinality |S| O((N)^O(1)) that approximates cost(P,c) (for every c [N]) up to a multiplicative factor of 1. Using known coreset techniques, this implies streaming algorithms using only O(((N)(n))^O(1)) memory. Our results hold for a large family of functions. Experimental results and open source code are provided.

Tasks

Reproductions