Frequency Moments in Noisy Streaming and Distributed Data under Mismatch Ambiguity
Proceedings of the ACM on Management of Data · 12.05.2026 · 4 (2) · 1-24
DOI: 10.1145/3801901 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 14.05.2026. Verfasst von Kaiwen Liu und 1 weiteren Autor:innen. Die Arbeit nennt 40 Literaturangaben. Gefördert von: NSF.
Abstract (Originalsprache)
We propose a novel framework for statistical estimation on noisy datasets. Within this framework, we focus on the frequency moments ( F p ) problem and demonstrate that it is possible to approximate F p of the unknown ground-truth dataset using sublinear space in the data stream model and sublinear communication in the coordinator model, provided that the approximation ratio is parameterized by a data-dependent quantity, which we call the F p -mismatch-ambiguity. We also establish a set of lower bounds, which are tight in terms of the input size. Our results yield several interesting insights: -In the data stream model, the F p problem is inherently more difficult in the noisy setting than in the noiseless one. In particular, while F 2 can be approximated in logarithmic space in terms of the input size in the noiseless setting, any algorithm for F 2 in the noisy setting requires polynomial space. -In the coordinator model, in sharp contrast to the noiseless case, achieving polylogarithmic communication in the input size is generally impossible for F p under noise. However, when the F p mismatch ambiguity falls below a certain threshold, it becomes possible to achieve communication that is entirely independent of the input size.
Förderung
- NSF
Zitieren
APA
Liu, K., & Zhang, Q. (2026). Frequency Moments in Noisy Streaming and Distributed Data under Mismatch Ambiguity. Proceedings of the ACM on Management of Data, 4(2), 1-24. https://doi.org/10.1145/3801901
Vancouver
Liu K, Zhang Q. Frequency Moments in Noisy Streaming and Distributed Data under Mismatch Ambiguity. Proceedings of the ACM on Management of Data. 2026;4(2):1-24. doi:10.1145/3801901
BibTeX
@article{Liu2026,
author = {Liu, Kaiwen and Zhang, Qin},
title = {Frequency Moments in Noisy Streaming and Distributed Data under Mismatch Ambiguity},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {2},
pages = {1--24},
doi = {10.1145/3801901}
}
EUVIMED