课程相关

李荣华 lironghuabit@126.com
主页 ronghuali.github.io
课程考核 大作业（综述）

推荐书籍

• 王宏志，大数据算法，机械工业出版社，2015
• Jure Leskovec, Anand Rajaraman, Mining of Massive Datasets edition
• 中文版：大数据-互联网大规模数据挖掘与分布式处理，王斌 译，人民邮电出版社

在n个数中查找出现次数超过一半的数字

使用一个桶，数据按顺序进桶，如果桶中无数字，该数据进桶，且计数1；如果桶中有数字，且与当前数字不同，计数器减一；如果桶中有数字，且与当前数字相同，计数器加一。当计数器为零时，桶清空。最终，桶中留下的数字即为最频繁的数字。

在n个数中寻找出现次数最多的k个数字

• Misra-Gries算法
  对于每个元素x：①若存在统计x的计数器，该计数器加一；②若不存在统计x的计数器，且计数器个数小于k，新建统计x的计数器且初始化为1；③若不存在统计x的计数器，且计数器个数为k，所有计数器数值减一，删除数值为零的计数器。最终，k个计数器统计的x则为出现次数最多的数字，且计数器的值可作为对应数字的出现次数的估计值。

估计n个数中出现次数最多的k个数字的出现次数

在Misra-Gries算法中，执行步骤③会丢弃k+1个数字（k个计数器减一，且当前数字没有加入计数）。我们可以计算最终得到的k个计数器内值的和，并记为n‘。则，最多进行了(n-n‘)/(k+1)次步骤③。因此，元素出现次数的估计值比真实值最多小(n-n‘)/(k+1)

布隆过滤器

作用：查询一个数据是否在数据集中。