Abstract
In the monitoring problem, the input is an unbounded stream $P={p_1,p_2\cdots}$ of integers in $[N]:=\{1,\cdots,N\}$, obtained from sensors such as GPS or heart rate monitors. The objective is to approximate the $n$ points received so far by a single frequency $\sin$, specifically $\min_{c\in C}cost(P,c)+\lambda(c)$, where $cost(P,c)=\sum_{i=1}^n \sin^2(\frac{2\pi}{N} p_ic)$, $C\subseteq [N]$ is a feasible set of solutions, and $\lambda$ is a regularization function. For any approximation error $\varepsilon>0$, we prove that every set $P$ of $n$ integers has a weighted subset $S\subseteq P$ (a coreset) of cardinality $|S|\in O(\log(N)^{O(1)})$ that approximates $cost(P,c)$ for every $c\in [N]$ up to a multiplicative factor of $1\pm\varepsilon$. This implies streaming algorithms using only $O((\log(N)\log(n))^{O(1)})$ memory.
Introduction
Modern sensor networks—ranging from GPS trackers to medical ECG monitors—generate massive, unbounded streams of data that often exhibit periodic or wave-like patterns. Analyzing these streams typically requires "sine fitting," a process of identifying the frequency that best represents the observed data points. This is a foundational task for anomaly detection (identifying heart arrhythmias or sensor failures) and data discretization (mapping high-precision data to lower-precision grids without losing structural integrity).
However, fitting sine waves to millions of points in real-time is computationally prohibitive for edge devices. Standard uniform sampling often fails because it treats all data points as equally important, frequently missing the critical "anchor points" that define a wave's shape. This paper introduces the first coreset framework for sine wave fitting, providing a method to compress massive periodic datasets into tiny, mathematically provable representative subsets.
The Coreset Framework
A coreset is a small, weighted subset of the original data that approximates the loss function of the entire dataset for any possible query—in this case, any possible sine wave frequency. The authors utilize a sensitivity sampling approach, where points are sampled based on their "importance" to the total cost.
Theoretical Innovations
- Bounding Total Sensitivity: The core theoretical contribution is the proof that for sine fitting, the total sensitivity is small, specifically $O(\log^4 N)$. This ensures that the resulting coreset remains tiny regardless of the total number of points $n$.
- VC Dimension Analysis: The authors prove the VC dimension for this problem is $O(\log(nN))$, providing a theoretical guarantee that the coreset will generalize accurately to any frequency in the search space.
- Cross-Disciplinary Proofs: To bound sensitivity, the research bridges trigonometry with graph theory, utilizing the properties of independent sets in directed graphs to handle the cyclic nature of the cost function.
Experimental Evaluation
The framework was evaluated against uniform sampling across several real-world periodic datasets:
- Air Quality Data: Hourly responses from chemical sensors used for gas leak detection.
- Single Neuron Recordings: Auditory-nerve fiber signals from a cat, used to infer cyclic neural properties.
- Dog Heart ECG: Electrocardiogram recordings used to detect heart rate distribution.
- Bat Echoes: High-frequency digitized echolocation pulses.
Key Results
In every experimental scenario, coreset-based sampling consistently yielded lower approximation errors than uniform sampling for the same sample size. On highly periodic data, such as the Dog Heart ECG, the coreset encapsulated the underlying structure so effectively that the optimal solution error dropped to nearly zero even with very small sample sizes. Because the coreset size is polylogarithmic ($O(\text{poly} \log N)$), the algorithm is uniquely suited for streaming applications on devices with extremely limited memory.
Discussion and Future Work
The most significant insight of this work is that coreset size does not need to grow linearly with the number of data points ($n$); it only needs to grow logarithmically with the range of the data ($N$). This allows a billion points to be summarized by just a few hundred.
While the paper provides a theoretical extension for high-dimensional data (points on a $d$-dimensional grid), practical performance in high-dimensional spaces remains an area for future exploration. Additionally, while the current sensitivity calculation is $O(Nn)$, future work may focus on faster approximation heuristics to reduce computational overhead. Finally, these coresets show promise as a preprocessing step for quantization-aware training in deep neural networks.
Summary updated