EUVIMEDEUVIMED entdecken
Crossref

Frequency Moments in Noisy Streaming and Distributed Data under Mismatch Ambiguity

Kaiwen Liu, Qin Zhang

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →