数据流挖掘
我们通常所理解的数据挖掘都假定是从数据库中进行挖掘，也就是说，如果真的需要数据的时候，所有的数据都可用。
但是还存在另一种假设：数据以一个或多个流的方式到来，如果不对数据进行及时的处理或者存储，数据将会永远丢失。此外，我们假定数据到来的速度实在是太快，以致将全部数据存在传统数据库并在我们选定的时间进行交互是不可能的。
数据流处理的每个算法都在某种程度上包含流的汇总过程，也即从流中抽取有用样本，过滤大部分不想要的元素。
一种很常见的对流进行汇总的方法是只观察一个定长的窗口，该窗口由最近的n个元素组成，其中n是某个给定值，通常较大。
流数据看起来很抽象，这里举几个例子，比如传感器数据，我们有100万个传感器，每个传感器都以每秒10次的速率传回数据；比如图像数据，卫星往往每天会给地球传回多个太字节的图像流数据；比如互联网及Web流量，互联网中的交换节点，Web网站收到的请求。
流查询
对流进行查询主要有两种方式，其中的一种称为固定查询。固定查询永远不变的执行并在适当的时候产生输出结果。比如对于温度传感器，当温度超过25摄氏度时输出警报，该查询只依赖最近的那个流元素。又或者，输出最近24次读数的平均值，这样只固定查询最近24个元素。
另一种查询被称为ad hoc查询，它对于当前某个或多个流仅提交一次。什么是ad hoc查询呢，ad hoc 允许终端用户自己去建立特定的、自定义的查询请求，通常是临时的，有特殊目的的，与之对应的是参数化的查询，参数化查询生成的执行计划可以重用，而ad hoc 生成的执行计划不能重用，每次都需要compile一次，消耗相当多的CPU资源。
通常应对的方式是在工作存储器上保存每个流的滑动窗口。一个滑动窗口可以是最近到达的n个流元素，也可以是在最近t个时间单位中到达的所有元素。
流抽样
一个需要解决的一般性问题是从流中选择一个子集，以便能够对它进行查询并给出统计性上对整个流具有代表性的结果。
考虑这样一个问题，如果我们要回答查询：在过去一个月中典型用户所提交的重复查询的比例是多少？，并假设我们只希望存储大概1/10的流元素。
一种很显然的做法就是对每个搜索查询产生一个随机数，抽取1/10的查询问句，然后计算其中重复的比例，但这是有问题的。可以证明，以这种方法，无论如何都得不到正确的结果，因为出现次数不同的查询语句，被抽取到的概率也不同。
为了得到正确答案，我们必须要挑出1/10的用户并将他们的所有搜索查询放入样本中。我们可以将用户哈希到编号为0~9的10个桶中的一个去，取这一个桶的用户作为样本，当然桶中并不真正保存用户，实际上，桶中没有任何数据，对任何用户也不需要存储对其的结果，只要当该用户新的查询到来时，即时对其进行哈希，就可以判定该用户是否在指定的用户列表中，也即该条查询是否该被抽样出来。
更一般化的，我们的流由一系列n字段构成，这些字段的一个子集称为关键字段，我们对样本的选择也基于它来进行。假定抽样之后的样本规模为a/b，那么就可以将每个元组的关键字段哈希到b个桶中的一个，然后将其中a个桶中的元组放入样本中，就得到了a/b的样本。
还有另一个问题，如果我们选定了1/10的用户，那么随着事件的推移，他们的数据也会越来越多，而且一些新的用户也会进入到用户列表中，而存储空间是有限的，所以我们选择的比例要随事件的推移而降低。
流过滤
一个常见的流数据处理方式是选择，或称为过滤，这里主要会讲布隆过滤。
还是先举一个例子，如果我们会接收邮件流数据，但只有10亿个白名单的邮箱的邮件才对我们有价值，其他邮箱的邮件被认为是垃圾邮件，那我们怎样才能过滤掉这些邮件呢。难道每封邮件过来都要先进行10亿次比较？
我们先考虑只有一封邮件的情况，我们知道，哈希结果的比较要比直接比较字符串要快的多，所以，在只有一封邮件的情况下，我们有两种方式可以选择：一是，直接与10亿个邮箱地址比较；二是将这封邮件和10亿个邮箱地址哈希，然后比较。第一种方法主要时间花在比较上，而第二种方法主要时间花在哈希上，这样看来谁优谁劣可能还不好讲，但是考虑这样一个问题，我们不止有一封邮件，我们要处理的是一个邮件流，如果采用第一种方法，每次都要将10亿邮箱与新邮件的所属邮箱比较，但是如果采用第二种方法，那10亿邮箱其实每个只用哈希一次，后面只需要哈希新邮箱就可以了，效率要远远高于第一种。由此可以引出布隆过滤器的思想。我认为布隆过滤器的思想在于通过利用过去的计算结果来提高效率。
接下来详细介绍一下布隆过滤器，还是刚才的问题，我们有10亿白名单邮箱，要用其来过滤邮件流数据，为了便于讨论，我们假定有1GB的可用内存，1GB就是80亿个位，也就是80亿个桶，我们将这10亿个邮箱哈希到80亿个桶中，将对应的位置为1，依照上面的思想，如果新邮件进来，将其邮箱哈希，如果哈希到的桶为0，那必定不属于10亿个白名单邮箱中，但如果其对应的位置为1，也不能一定保证其就在白名单当中，但这也已经过滤掉了绝大多数不需要的邮件了。
为了降低布隆过滤器的假阳率，我们可以选用多个哈希函数（比如M个），把这10亿个邮件每个都用着M个哈希函数哈希到这80亿个桶中，只要有一个哈希函数将其哈希到了某个特定的桶中，就将对应的位置置1。这样当新的邮件到来时，我们也将其邮箱用M个哈希函数哈希，只有这个邮箱经由M个哈希函数哈希到的M位全部为1的时候，我们才会认定其可能存在于白名单中。
