Learning-Based Sketches for Frequency Estimation in Data Streams Without Ground Truth
IEEE Transactions on Knowledge and Data Engineering · 2026-06 · 38 (6) · 3722-3736
DOI: 10.1109/tkde.2026.3675012 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Knowledge and Data Engineering, 2026-06. Verfasst von Xinyu Yuan und 6 weiteren Autor:innen. Die Arbeit nennt 44 Literaturangaben. Gefördert von: National Natural Science Foundation of China, Anhui Provincial Natural Science Fund, Key Laboratory of Knowledge Engineering with Big Data.
Abstract (Originalsprache)
Estimating the frequency of items on the high-volume, fast data stream has been extensively studied in many areas, such as database and network measurement. Traditional sketches provide only coarse estimates under strict memory constraints. Although some learning-augmented methods have emerged recently, they typically rely on offline training with real frequencies or/and labels, which are often unavailable. Moreover, these methods suffer from slow update speeds, limiting their suitability for real-time processing despite offering only marginal accuracy improvements. To overcome these challenges, we propose UCL-sketch, a practical learning-based paradigm for per-key frequency estimation. Our design introduces two key innovations: (i) an online training mechanism based on equivalent learning that requires no ground truth (GT), and (ii) a highly scalable architecture leveraging logically structured estimation buckets to scale to real-world data stream. The UCL-sketch, which utilizes compressive sensing (CS), converges to an estimator that provably yields an error bound far lower than that of prior works, without sacrificing the speed of processing. Extensive experiments on both real-world and synthetic datasets demonstrate that our approach outperforms previously proposed approaches regarding per-key accuracy and distribution. Notably, under extremely tight memory budgets, its quality almost matches that of an (infeasible) omniscient oracle. Moreover, compared to the existing equation-based sketch, UCL-sketch achieves an average decoding speedup of nearly 500 times.
Förderung
- National Natural Science Foundation of China
- Anhui Provincial Natural Science Fund
- Key Laboratory of Knowledge Engineering with Big Data
- Ministry of Education of the People's Republic of China
- Key Research and Development Program of Zhejiang Province
Zitieren
APA
Yuan, X., Qiao, Y., Li, M., Wei, Z., Feng, C., Wang, Z., & Chen, W. (2026). Learning-Based Sketches for Frequency Estimation in Data Streams Without Ground Truth. IEEE Transactions on Knowledge and Data Engineering, 38(6), 3722-3736. https://doi.org/10.1109/tkde.2026.3675012
Vancouver
Yuan X, Qiao Y, Li M, Wei Z, Feng C, Wang Z, et al. Learning-Based Sketches for Frequency Estimation in Data Streams Without Ground Truth. IEEE Transactions on Knowledge and Data Engineering. 2026;38(6):3722-3736. doi:10.1109/tkde.2026.3675012
BibTeX
@article{Yuan2026,
author = {Yuan, Xinyu and Qiao, Yan and Li, Meng and Wei, Zhenchun and Feng, Cuiying and Wang, Zonghui and Chen, Wenzhi},
title = {Learning-Based Sketches for Frequency Estimation in Data Streams Without Ground Truth},
journal = {IEEE Transactions on Knowledge and Data Engineering},
year = {2026},
volume = {38},
number = {6},
pages = {3722--3736},
doi = {10.1109/tkde.2026.3675012}
}
EUVIMED