cs.LGMar 15, 2026
SaveOn the (Generative) Linear Sketching Problem
Organizations: College of Computer Science and Technology, Zhejiang University, Hangzhou, China · School of Computer Science and Information Engineering, Hefei University of Technology, Hefei, China
Abstract
Sketch techniques have been extensively studied in recent years and are especially well-suited to data streaming scenarios, where the sketch summary is updated quickly and compactly. However, it is challenging to recover the current state from these summaries in a way that is accurate, fast, and real. In this paper, we seek a solution that reconciles this tension, aiming for near-perfect recovery with lightweight computational procedures. Focusing on linear sketching problems of the form , our study proceeds in three stages. First, we dissect existing techniques and show the root cause of the sketching dilemma: an orthogonal information loss. Second, we examine how generative priors can be leveraged to bridge the information gap. Third, we propose FLORE, a novel generative sketching framework that embraces these analyses to achieve the best of all worlds. More importantly, FLORE can be trained without access to ground-truth data. Comprehensive evaluations demonstrate FLORE's ability to provide high-quality recovery, and support summary with low computing overhead, outperforming previous methods by up to 1000 times in error reduction and 100 times in processing speed compared to learning-based solutions.
Figures & tables
Figure 1: Comparison of our generative solution and existing solutions. From (a) to (c), we present an overview of the full pipelines of three sketching paradigms. In (d), our proposal achieves the best trade-off among accuracy, fidelity and speed under a 1MB sketch memory budget on the CAIDA-2018 dataset.
Figure 2: Matrix formulation of Count-Min. The linear sketching problem can be analyzed via simple matrix operations.
Figure 3: Overview of four types of GMs considered in this work.
| Symbol | Description | Symbol | Description |
|---|---|---|---|
| Ground-truth (frequency) vector | Linear sketching matrix | ||
| Measurement (counters) vector | Number of hash functions in sketch | ||
| Prior (Gaussian) vector | Number of distinct items | ||
| Key set of data stream | Number of total counters in sketch | ||
| -th invertible transformation function | Coefficient & error probability of sketch | ||
| Error introduced by missing elements | Number of bits in Bloom Filter |
Table 1: List of Main Symbols
Figure 4: Compare compressive sensing with sketch techniques.
Figure 5: Illustration of our insights. (a) The GT cannot be recovered due to orthogonal information loss in the null space. (b) We leverage GMs to generate the null-space component which is in harmony with the range-space component.
Figure 6: Visualization of Streaming data distribution fitting. The first row shows results on Gaussian distributions, while the second row shows results on Zipfian distributions. From left to right, the scale of the data stream increases.
Figure 7: Performance comparison of different generative models under Gaussian and Zipfian distributions. For better visualization, metrics across different dimensions are normalized by the best result (higher the better).
| GM (# of steps) | ARE | WMRE | Gen. Time (s) |
|---|---|---|---|
| DDPM (500) | 7.58 | ||
| Flow Matching (15) | 0.92 | ||
| FGM (1) | 0.001 |
Table 2: Additional comparison with flow matching on Zipfian-100K.
Figure 8: Performance overview across different GMs. FGM achieves the most favorable trade-off in sketching tasks.
Figure 9: System overview of FLORE . (a) illustrates the control-plane recovery procedure, where flow-based generators are trained. (b) depicts the process of online tuning and scaling. The data-plane structure details are explained in (c).
Figure 10: The architecture of FLORE . FLORE is modeled as an invertible mapping in the latent space.
Figure 11: Scalable flow-based generative model for online learning in one-pass data streams.
Figure 12: The underlying cINN architecture used in FLORE .
| Method (256KB) | ARE | WMRE | Training Iters |
|---|---|---|---|
| FLORE w/ Jac. | |||
| FLORE w/o Jac. |
Table 3: Ablation of the Jacobian Loss Term
Figure 13: Ablation comparing Count-Min Sketch and Count-Min Sketch + EM refinement (with ten steps).
| # of EM Steps | 1 | 3 | 5 | 10 | 20 | 50 |
|---|---|---|---|---|---|---|
| Total Time (s) | 0.54 | 1.72 | 3.22 | 6.85 | 13.91 | 31.05 |
| Normal. ARE | 9.71 | 2.04 | 1.55 | 1.41 | 1.40 | 1.39 |
Table 4: Time-accuracy Trade-off of the EM Algorithm
Figure 14: Data structures used in FLORE : a Bloom Filter for key tracking, a Count-Min Sketch for store infrequent items, and an augmented filter for saving frequent items as key-value pairs.
| Real-World | # of Keys | # of Items | Skewness | Synthetic | # of Keys | # of Items | Skewness |
|---|---|---|---|---|---|---|---|
| CAIDA | 291.56 | Zipf-icml | 24.27 | ||||
| Webdocs | 25.42 | Zipf | 125.93 | ||||
| MAWI | 92.67 | Pareto | 10.24 | ||||
| Kosarak | 89.56 | Exponential | 3.81 | ||||
| Retail | 71.27 | Log-Normal | 5.64 |
Table 5: Statistics of Real-world and Synthetic Data Streams Used in the Evaluation
Figure 16: Sketching performance on five real-world datasets.
Figure 17: Sketching performance on five synthetic datasets.
Figure 18: Comparison of stream processing speed on CAIDA with 1MB memory ( Green means better than CM).
Figure 19: Training loss curves of FLORE on the CAIDA dataset.
| Memory Fluctuation Factor 0.2 0.5 1.0 2.0 128KB average 0.0% -1.0% -1.8% 2.7% 90th Pct. 0.4% -0.2% -2.1% 5.9% 256KB average -0.0% -1.1% -1.8% 1.9% 90th Pct. 0.2% -0.3% -1.4% 2.8% 512KB average 0.2% 0.0% -1.0% 1.0% 90th Pct. 0.3% -0.0% 1.1% 1.3% 1MB average 0.0% -1.9% 0.2% -0.3% 90th Pct. 1.1% -0.8% 0.2% -0.5% | Memory Training stream time windows 0%-25% 25%-50% 50%-75% 128KB average 5.4% 3.6% 4.4% 90th Pct. 9.6% 7.8% 8.7% 256KB average 2.6% 3.2% 2.1% 90th Pct. 4.0% 5.7% 4.6% 512KB average 0.2% 1.8% 0.5% 90th Pct. 0.9% 0.2% 1.0% 1MB average 0.5% 1.6% -1.5% 90th Pct. 0.0% 1.0% 1.6% | Memory Proportion Factor 0.9 0.5 0.25 0.1 128KB average 0.3% 0.7% 1.8% 2.3% 90th Pct. 1.7% 1.0% 3.1% 6.5% 256KB average 0.2% 0.6% 1.5% 2.6% 90th Pct. 0.4% 0.7% -0.4% 2.4% 512KB average 0.0% -0.6% 1.7% 1.3% 90th Pct. 0.2% 0.4% 1.4% 0.6% 1MB average 0.5% 0.7% -1.0% -1.6% 90th Pct. 0.0% -0.6% -0.4% 1.4% |
| Table 6: ARE Performance decline with increased CAIDA network traffic fluctuation. Negative values indicate no degradation. | Table 7: ARE Performance decline with natural drift in CAIDA network traffic. Negative values indicate no degradation. | Table 8: ARE Performance decline with spatial shift in CAIDA network traffic. Negative values indicate no degradation. |
Table 6: ARE Performance decline with increased CAIDA network traffic fluctuation. Negative values indicate no degradation.
Figure 20: Comparing FLORE with the Count-Min and SOTA compressive sensing algorithms by replacing the FGM.
Figure 21: Comparison of computation times for recovery procedure.
Figure 22: CDFs for the AAE and ARE of FLORE and its variants on the real-world Kosarak dataset.
Figure 23: CDFs for the AAE and ARE of FLORE and its variants on the synthetic Zipf dataset.
Figure 24: Ablation comparing FLORE and FLORE without the stream filtering mechanism or separation design, where at the bottom indicates that the data stream has skewness .
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 25: Visualizations of the learned flow-based mapping during training.
Figure 26: Visualizations of sketch recovery under a fixed 32KB memory budget. From left to right, we present the recovery results of FLORE , CM, CS, NZE, LCM, and LCS, compared against the ground-truth sample distribution. To enhance readability, every 100 consecutive keys are aggregated in the x-axis.
Figure 27: Visualizations of sketch recovery under a fixed 128KB memory budget. From left to right, we present the recovery results of FLORE , CM, CS, NZE, LCM, and LCS, compared against the ground-truth sample distribution. To enhance readability, every 100 consecutive keys are aggregated in the x-axis.
Figure 28: Visualizations of sketch recovery under a fixed 256KB memory budget. From left to right, we present the recovery results of FLORE , CM, CS, NZE, LCM, and LCS, compared against the ground-truth sample distribution. To enhance readability, every 100 consecutive keys are aggregated in the x-axis.