EUVIMEDEUVIMED entdecken
Crossref

On Sketching Trimmed Statistics

Honghao Lin, Hoai-An Nguyen, David P. Woodruff

Proceedings of the ACM on Management of Data · 12.05.2026 · 4 (2) · 1-27

DOI: 10.1145/3801907 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 14.05.2026. Verfasst von Honghao Lin und 2 weiteren Autor:innen. Die Arbeit nennt 48 Literaturangaben. Gefördert von: NSF GRFP, Office of Naval Research.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study sketching trimmed statistics of a frequency vector, including the F p moment of the top- k coordinates and of the trimmed- k vector. Despite their natural role in robust analytics, this is the first time these problems have been studied in any sublinear space setting. For p ? [0,2], we obtain poly(log n /?)-space algorithms for both tasks when k is moderately large, and for general k we identify a sharp structural threshold that characterizes exactly when sublinear space is possible: in particular, it is actually determined by the ratio between a 2 k and ? x - k ? 2 2 / k . We extend these results to p > 2 and present several applications including algorithms for thresholded F p estimation and generalized impact indices. Notably, we improve the space bounds of Govindan, Monemizadeh, and Muthukrishnan (PODS '17) for computing the h -index.

Förderung

  • NSF GRFP
  • Office of Naval Research

Zitieren

APA

Lin, H., Nguyen, H., & Woodruff, D. P. (2026). On Sketching Trimmed Statistics. Proceedings of the ACM on Management of Data, 4(2), 1-27. https://doi.org/10.1145/3801907

Vancouver

Lin H, Nguyen H, Woodruff DP. On Sketching Trimmed Statistics. Proceedings of the ACM on Management of Data. 2026;4(2):1-27. doi:10.1145/3801907

BibTeX
@article{Lin2026,
  author = {Lin, Honghao and Nguyen, Hoai-An and Woodruff, David P.},
  title = {On Sketching Trimmed Statistics},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {2},
  pages = {1--27},
  doi = {10.1145/3801907}
}
Kostenlos starten →