网络数据流方法-第五章

数据流概述

海量数据

测量要求：

1. 一次机会
2. 空间小
3. 处理和更新快
4. 查询准确度

测量方式：

1. 专用硬件
2. 抽样技术（部分流量数据）
3. 数据流（所有流量数据）

数据流定义：高速传输的数据

数据流适用任务场景：

1. 熵估计
2. 流量与流矩阵估计
3. 连接度估计
4. 大流估计
5. 活跃流的计数

Bitmap

naive bitmap：bitset[n][m]

direct bitmap：对流标识进行hash，映射到bitmap的某个位

virtual bitmap：hash(流标识)若在virtual bitmap中则置位，相当于抽样

multiple bitmap

multiresolution bitmap

Bloom Filter

标准布隆过滤器：一个元素计算多次hash，若各个hash位置为1则说明元素在集合中

仅支持插入和查找，不支持删除

由于hash碰撞，存在误判的可能性

误判分析

k=7时有最小误判率

计数布隆过滤器：标准布隆计数器+可删除；每个元素一个计数器，当元素被删除时对应计数器减少

计数器4位够用

Sketch

count-min sketch：mxn的二维矩阵，每行对应一个hash函数，n为mod的大小；计算元素的各个hash值，mod n后每行对应位置加1

用于计数

返回不准确的结果