比较网络是允许同时进行很多比较的一种算法

排序网络总是能对其他输入进行排序的比较网络,比较网络仅由线路和比较器构成

0-1原理认为，对于属于集合{0,1}的每个输入值,排序网络都能正确运行,则对任意输入值,它也能正确运行

要构造有效的排序网络，第一步是构造一个能对任意双调序列(bitonic sequence)进行的比较网络

合并网络就是指能把两个已排序的输入序列合并为一个有序的输出序列的网络

排序网络SORTER[n]运用合并网络，实现对合并排序算法的并行化

数据以流的方式到来，如果不对数据进行及时地处理或存储，数据会永远丢失，数据到来的速度太快，以至于将数据全部存起来再处理不太可能

流汇总

数据窗口

• 获得问题的近似解比精确解要高效的多
• 一系列与哈希相关的技术被证明十分有用

• 固定查询
• Ad-Hoc查询

• 布隆过滤：假设有1GB的内存，在一种称为布隆过滤的技术当中，内存会被当成位数据使用，这样1个字节代表有8位，所以1GB内存可以容纳80亿个位。可以设计一个哈希函数，将邮件地址映射到80亿个桶中。这时，将S中的每个元素映射到某位并将该位置为1，而数组中所有其他的位仍为0。当一个流元素到达时，对其邮件地址进行哈希操作，如果该邮件地址哈希后对应位位1，那么就让邮件通过，但若对应位为0，则丢弃

• n个位组成的数组，每个位的初始值都为0

• 一系列哈希函数h1,h2,...,hk组成的集合.每个哈希函数将键值映射到上述的n个桶中

• m个键值组成的集合S

• 内存中存储当前已有的所有元素列表
• 多个机器同时进行存储
• 将搜索结构的大部分存到一个二级存储器中，对流元素分批处理
• 利用FM算法进行估计

• 矩计算：将上述独立流元素技术推广到更一般的问题，包括不同流元素出现频率的分布的计算

流的0阶矩的所有元素中不为0的元素mi的数目，流的1阶矩是所有元素mi之和，即整个流的长度，因此，一阶矩的计算非常容易，流的2阶矩是所有mi的平方和

如长度为100的流，其中10个元素出现9次，1个元素出现10次，奇异数为10 * 9^2 + 1 * 9^2 = 910

二阶矩估计中，计算一定数量的变量，对于每个变量X，保存一下内容

• 全集当中的一个特定元素，记为X.element
• 一个整数，记为X.value,它是变量X的值。为确定该值，在流中均匀随机地选择1到n之间的一个位置。将X.elemen置为该位置上的元素，将X.value的初始值置为1，在流读取过程中，每再看到一个X.element时，就将其对应的X.value加1

2x-1 k阶矩： x^k - (x - 1)^k

DGIM算法使用O(log^2N)位表示大小为N的窗口,同时能保证窗口内1数目的估计错误率不高于50%，算法空间复杂度为：O(log2N)^2

将整个窗口划分为多个桶，每个桶中包含以下信息:

• 桶最右部的时间戳(即最近的时间戳)
• 桶中1的数目，该数目必须是2的幂，将该数称为桶的大小

6条规则

• 桶的最右部的位置上总是1
• 每个1的位置都在某个桶中；
• 一个位置智能属于一个桶
• 桶的大小从最小一直变化到某个最大值，相同大小的桶只可能有一到两个
• 所有桶的大小必须都是2的次幂
• 从右到左扫描（即从远到近扫描），桶的大小不会减小

DGIM算法会寻找具有最低时间戳的桶b，它至少包含k个最近位中的一部分，最后的估计值为桶b右部（最近）所有桶的大小加上桶b的一半大小

• 如果新来的位是0，不需要做任何改动，如果新来的位是1，则基于当前时间戳建立一个新的大小为1的桶，如果大小为1的桶数量超过2个，则合并，依次向时间戳较早的地方陆续合并桶

当整数流中包含整数又包含负数时，不太可能利用DGIM算法来处理

擦除代码告诉您如何创建n个值为数据+编码的磁盘，这样当磁盘发生故障时，您仍然可以获取数据。

• Erasure coding: k个数据磁盘，总共n个磁盘，n=k+m，叫做 (n, k) MDS 编码 MDS（最大距离可分离）代码可以从任何k个失败重建数据。

用生成矩阵编码和解码

• (16, 12)-MSR
• (16, 12)-MBR
• (12,2,2)-LRC
• ReedSolomon
• 3-replication

Github Code