Abstract
This paper introduces the first coreset construction specifically designed for fitting sine waves and discretizing data. A coreset is a small, weighted summary of a massive dataset that maintains theoretical guarantees on approximation error. By proving that a dataset of $n$ points can be reduced to a subset of size $O(\text{polylog}(N))$, the authors enable high-accuracy anomaly detection and signal processing on massive data streams using negligible memory.
Introduction
In modern monitoring scenarios—ranging from medical ECG tracking to GPS telemetry—data often arrives as an unbounded stream. Fitting a sine wave to this data is a fundamental task for identifying underlying signals or detecting anomalies. However, as datasets scale to billions of points, traditional processing becomes computationally prohibitive, particularly on edge devices. Standard uniform sampling often fails to capture the "important" points that define a signal's periodic structure. This work addresses the challenge by creating a coreset: a representative subset ensuring that the cost of fitting a sine wave to the summary is nearly identical to the cost for the full dataset across any possible frequency.
Methodology: Sensitivity Sampling for Trigonometric Functions
The authors employ the Sensitivity Sampling Framework, which assigns an "importance" score (sensitivity) to each data point and samples accordingly. The primary technical innovation lies in bounding the total sensitivity and the VC dimension for non-linear, periodic trigonometric cost functions.
- Trigonometric Bounding: Unlike linear or polynomial functions, sine waves are periodic. The authors utilized arithmetic modulo and trigonometric identities to demonstrate that a point's sensitivity is inversely proportional to the density of nearby points in a cyclic sense.
- Graph Theoretic Reductions: To prove that total sensitivity remains small, the problem was reduced to finding the size of an independent set in a directed graph.
- Complexity Bounds: The authors proved that for a bounded query space (integers up to $N$), the VC dimension—a measure of problem complexity—is $O(\log(nN))$.
The resulting coreset size is polylogarithmic in the data range ($N$) and logarithmic in the number of points ($n$), allowing the summary to remain compact even as the stream grows indefinitely.
Data Discretization via Sine Fitting
Beyond signal processing, the authors demonstrate that sine fitting is a powerful tool for data discretization (quantization). By fitting a wave and projecting points to its nearest "root," they can reduce data bit-width while preserving structural integrity more effectively than naive methods.
Empirical Results
The method was evaluated on diverse real-world datasets, including Air Quality sensor data, Single Neuron recordings, Dog Heart ECGs, and Bat Echolocation pulses.
Across all benchmarks, the coreset consistently outperformed uniform sampling. A notable result occurred with the Dog Heart ECG dataset: the coreset captured the periodic structure so efficiently that the approximation error dropped to nearly zero even with minimal sample sizes, whereas uniform sampling required significantly more points to achieve comparable accuracy.
Conclusion
This work provides a robust theoretical and empirical foundation for using coresets in periodic signal analysis. By leveraging the "Merge-and-Reduce" hierarchy, these coresets can process infinite streams with $O(\text{polylog}(n))$ memory. Future work includes extending the framework to higher-dimensional data and exploring more complex periodic functions for applications in deep learning quantization.
Summary updated