对，我是从哪里看到的来着，这里的大数据处理，我们用的是商业化分布式框架结构，而不是用的专门的那种很昂贵的分布式超级计算机

第一章，讲概念

第二章，讲分布式结构技术栈

第三章，文档处理，是把文档变成K-shingles，是把文档变大了，然后变成0-1矩阵，对行压缩用的是最小哈希，对列的压缩是用的位置敏感哈希

第四章，流式结构数据，抽样问题，转变成对用户的抽样，且也用的哈希；如果及使用10比1的方法抽样，还是超过了存储空间怎么办？书上有说。有固定比例抽样，还有什么抽样的方法：水塘抽样

s/n，针对水来说n是变化的。

又讲到了随机过程，噪声服从高斯分布，大多数都是服从高斯分布的，很少服从均匀分布

4.6窗口内计数

窗口不动，数据在流动；想把N存起来，但是N又是存不起来的，怎么样在

DGIM这个base算法可以让冲口内1的数量的估计误差可以不超过50%，其他优化算法还可以进一步的降低这个误差，在这方便，能给出一个误差边界就很不错了，或者说能够给出某一个解释。

分块操作，记数据流的块，记了两个值，起始位置（时间戳）<=N，用什么方法记下来了时间戳？二进制，用的比特位数是log2N，

每个块中的1的个数用2的幂来记。

相同大小的块是不超过2个

这个过程0，1是不断变化的，如果新来的一个数是0，则不断；如果新来的一个数是1，就划分为块，这里记两个数，时间戳还有啥；

DGIM过程中，整个窗口时N，因为相同大小的块是不超过2个，又每次对把最新出现的1划分为一个块，所以就把把旧的2个块进行合并，这个方法的一个问题，就是最原始最大的那个块可能会超出边界。这种不断合并不断合并的思想还是非常巧妙的，

如何做查询？

把之前所有的块加起来，对最后一个块，可能是超过边界的，时间戳在N里面，但是长度大于滑动窗口(边界)，就比较粗暴，对这个最后一个块就只取一半；针对时间戳不在N里面的块，就舍弃了

这种舍弃的操作就会导致误差，怎么计算这个误差？这里算的时最差的一种情况

用黄色框除以紫色框算出来的误差，这肯定是＜50%的

怎么提高这个精度，进一步减少这个误差？分析本质很简单，那就是只有最后一个块才是有误差的，其他的块都是精确的，这个解决方法就是如下图所示：

关于这个的证明自己看，老师米有讲~

又有问题：如果这个流不是Bit流，是一个整数流，应该怎么计算k个因素的和？也很简单，就转换成比特流呗

4.3流过滤

布隆过滤器：做商品推荐会用到

tuple：元组

因为S可能太大了？所以就又会做一个近似，用hash tabel做映射，但是这个table的长度时小于S的，所以这是一个近似 ，就会出现，原本是垃圾邮件，但是因为HASH里面没有这个地址，所以就把这个邮件可能映射为正常邮件（false positive）这就会出现误差，怎么计算这个误差呢？

粗略的计算方法：1/8

精确的计算方法：e那个公式

优化的计算方法：布隆过滤（前面都是铺垫，这才是重点）

映射为0的结果都扔掉的想法，投了k次要保证每次都有一个1，相当于在哪抓漏网之鱼？以前检查一次，现在检查多次，这个提升之后的精度时多少？

把正常邮件判别为垃圾邮件，不是布隆过滤不好，而是S集合没有统计完全，没有完备。哈希函数的计算非常快，甚至可以直接用硬件设备都能处理，

4.4流中独立元素的数目统计

听起来与之前的计数有点像，但是这里不一样啦；这里没有了窗口的概念，就是对一整个流的统计

想做到既可以存储，又可以计算，还误差可控的方法：即FM

2^R是接近一个平均数的,为什么FM是有用的？

窗口里的计数、布隆过滤、FM；这前面都是在工程实践中想出来的算法，做相似项的计算偏多。

考试和平时做的题差不多，做什么词频的原理什么的。一开始学代码的时候，最好看一个源代码，别掉包，最好能自己写一下更好。