One Sketch to Rule Them All: Rethinking Network Flow Monitoring with UnivMon阅读笔记

作者：空白诗007 | 2024-08-08 15:16:38

踩

one sketch to rule them all: rethinking network flow monitoring with univmon

$D (m, n)$ 是一个长度为 $m$ , 包含 $n$ 个不同元素的信息流 (stream). 假设这些元素分别为 $\cdots, n]$ , $f_i$ 是元素在信息流中 $i$ 的频数. 假设 $g ()$ 是任意一个函数, 则我们将 $\sum_{i=1}^ng(f_i)$ 称为频数向量的 $g - s u m$ .

如果 $g ()$ 是单调函数并且 $g(f_i)\le O(f_i^2)$ , 则用于估计 $G - s u m$ 的具有多重对数型空间复杂度的信息流算法(streaming algorithm)是存在的.

$S t r e a m - P o l y L o g$ 是所有存在对应的多重对数型空间复杂度的信息流算法的 $G - s u m$ 的集合.

对于元素 $\in [1, 2, \cdots, n]$ , 如果 $g(f_i) > \gamma\sum_jg(f_j)$ , 其中

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/空白诗007/article/detail/948845