Abstract
As processing capabilities increase, more and more data is gathered every day everywhere on earth. While machines are becoming more and more capable of dealing with these large amounts of data, humans cannot keep up with the amount of data generated every day. They need small and comprehensive representative samples of data, which capture all the informative parts of the data, in other words: a data summary. Formally, we formulate the data summarization problem as a function maximization problem with a cardinality constraint in which we seek to maximize a utility function $f$ while selecting up to $K$ elements in total. Due to their compelling theoretical properties, submodular functions have been widely adopted as a utility function for data summarization. Submodular functions are set functions that reward adding a new element to a smaller set more than adding the same element to a larger set and thereby naturally lead to small and comprehensive summaries. This fits the restricted resources of small devices. We want to do a step further and model the summarization as a streaming algorithm. Streaming algorithms evaluate each data item once and decide immediately, on-the-fly with a limited memory budget, if an item should be added to the summary or not. These algorithms can be run on small, embedded devices while data is generated and thereby provide a data summary anytime with minimal computational costs. In this contribution, we discuss the framework of submodular functions in more detail and survey the current state of the art for streaming submodular function maximization. We analyze each algorithm for performance guarantees as well as runtime and memory consumption. We end the contribution with a comprehensive comparison between algorithms for real-world summarization tasks over data streams with and without concept drift. Coresets and sketches are small data summaries for a given computational problem such as regression or clustering. They preserve the cost function for any possible solution up to little distortion and thus serve as a proxy for the original massive dataset during optimization or inference. They have strong aggregation properties such as linearity or mergeability and thus facilitate their construction for data streams as well as for distributed data. Once the data summary is computed, it can be analyzed using a classical algorithm and the result will be provably close to an optimal solution. In summary, this improves the efficiency and scalability and enables streaming and distributed computation using standard offline algorithms. We show how linear sketching enables streaming and distributed data processing and show how even static off-line coreset constructions can be extended to those flexible computational settings via the Merge & Reduce principle. Next we survey classic sketching and coreset results for ordinary linear regression and show how those can be extended to more sophisticated models, such as Bayesian regression, generalized linear models, and dependency networks. We also show the limitations of data summarization via complementing lower bounds and how natural assumptions and parameterized beyond-worst-case analysis help to overcome those limitations.
Introduction
We live in an era of sensor-driven "Big Data," yet much of this data is generated by "Small Devices"—embedded systems, IoT sensors, and cyber-physical systems with strictly limited energy, memory, and computational power. The core challenge is data summarization: how do we select a small, representative subset of data from a continuous stream without storing the entire dataset?
Traditional algorithms often require multiple passes or assume the dataset fits in memory. In a streaming context, each item is viewed once, and a decision to keep or discard it must be made immediately. Existing streaming algorithms often suffer from "worst-case" design, leading to memory overheads that are still too high for the tiniest devices. This research presents strategies for summarizing massive datasets on-the-fly, focusing on submodular maximization and advanced coreset/sketching techniques.
Algorithmic Methods for Data Summarization
The research explores several sophisticated algorithmic approaches to address resource constraints:
- ThreeSieves Algorithm: Designed for submodular maximization (selecting a diverse, informative subset). Unlike previous "Sieve" algorithms that maintain dozens of parallel summaries with different thresholds, ThreeSieves uses a single summary. It employs the statistical "Rule of Three" to estimate the probability of finding a better data item later in the stream. If the probability of finding a "better" item drops below a certain threshold, the algorithm lowers its standards to fill the summary.
- Coresets: These are small, weighted versions of the original dataset that act as a proxy. Running a regression on the coreset yields nearly the same result as running it on the full dataset.
- Sketches: These use random linear projections (dimensionality reduction) to compress data. A novel "stacked sparse random matrix" sketch is introduced specifically for logistic regression.
- Merge & Reduce: A framework that allows offline coreset constructions to be used in streaming or distributed environments by organizing them into a binary tree structure.
Comparative Analysis of Streaming Algorithms
To understand the landscape of streaming submodular maximization, it is essential to compare the performance and resource requirements of various algorithms.
As shown in the table above, ThreeSieves achieves a competitive approximation ratio of $(1 - \epsilon)(1 - 1/e)$ with high probability, while maintaining constant query complexity $O(1)$ and linear memory $O(K)$ relative to the summary size. This is a significant improvement over previous methods like SieveStreaming, which requires $O(K \log(K)/\epsilon)$ memory and $O(\log(K)/\epsilon)$ queries.
Key Insights and Theoretical Contributions
- Beyond the Worst Case: While theoretical "worst-case" scenarios exist where streaming is nearly impossible, real-world data is usually "well-behaved" (i.e., i.i.d.). Designing for the average case while allowing for concept drift detection achieves massive efficiency gains.
- Logistic Regression Complexity: Compressing data for logistic regression is difficult. The authors introduce a parameter, $\mu(Z)$, measuring dataset balance. They show that "$\mu$-complex" datasets can be compressed into sublinear coresets.
- Bayesian Summarization: Sketching can approximate an entire posterior distribution. Using Wasserstein distance, the authors prove that Bayesian analysis on a sketch yields results remarkably close to analysis on the full data.
Experimental Results
The methods were evaluated using benchmarks like ForestCover, Creditfraud, and Highway Sensor Data (Cologne).
- Efficiency: ThreeSieves uses orders of magnitude less memory and fewer function queries than previous state-of-the-art streaming algorithms.
- Speed: ThreeSieves and random sampling were the fastest methods, significantly outperforming SieveStreaming and Salsa.
- Performance: On the Creditfraud dataset, ThreeSieves outperformed the standard non-streaming Greedy algorithm, suggesting its probabilistic approach can avoid some local optima.
- Novelty: The work presents the first provably sublinear coreset constructions for logistic regression and the first linear sketch for "turnstile" streams.
Limitations and Future Work
The high-probability guarantees for ThreeSieves rely on the assumption that data is i.i.d. Sudden changes in data nature (concept drift) require external detection mechanisms. Additionally, ThreeSieves requires tuning the target summary size ($K$) and sensitivity parameter ($T$). Future research aims to extend these coreset and sketching techniques to the highly challenging domain of neural networks.
Summary updated