EUVIMEDOpdag EUVIMED
Crossref

Frequency Moments in Noisy Streaming and Distributed Data under Mismatch Ambiguity

Kaiwen Liu, Qin Zhang

Proceedings of the ACM on Management of Data · 2026-05-12 · 4 (2) · 1-24

DOI: 10.1145/3801901 ↗

At a glance

Journal article in Proceedings of the ACM on Management of Data, published online on 2026-05-14. Written by Kaiwen Liu and 1 co-authors. 40 references. Funded by: NSF.

AbstractBibliografiske oplysningerCiteRelated studies

Abstract (original language)

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.

Funding

  • NSF

Cite

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}
}
Start for free →