大数据存储与处理-数据流挖掘(64页).ppt

1、大数据存储与应用数据流挖掘,课程主页：http:/ learning,模型,两种查询固定查询：Standing query从不停止例：历史最高温度事先写好Ad-hoc查询不全存，但还是存一些内容根据这些存储的内容应答,问题,取样：随机取样（Sampling）过滤（白名单）：选取特定属性的元素（Filtering）计数（一定窗口内）有多少个不同的元素？（distinct elements)各元素的Popularity？特征：各阶矩谁最流行?,应用,Google：查询流发现最流行的查询关键字Yahoo：发现最流行的页面微博：发现最热的话题找人传感器网络电话记录美国，棱镜门网络交换机流量统计，优化路

2、由检测DDoS攻击,抽样,Sampling,抽样,两种抽样固定比率抽样1 in 10固定Size抽样总是保持s个元素,固定比率抽样,应用场合搜索引擎，一个用户的搜索中，重复的有多少？存不了全部，可以存1/10最明显的办法每来一个query生成一个随机整数：09如果是0，就存起来1/10的采样然后统计其中的用户重复搜索比例对吗？,有问题,假设：一个用户所有搜索字符串中，x个查询了一次，d个查询了两次，没有其他查询。重复查询占比：d/(x+d)随机采样10%后，重复查询占比是怎样的？采样后，获得(x+2d)/10个查询，其中x/10个查询是属于x，肯定只出现一次针对d的2d/10个查询d中任一查询

3、，两次都被抽中的概率为1/101/10=1/100所以，平均有d/100个查询会被抽中两次，占2d/100个查询剩下2d/10 2d/100=18d/100次查询，也只出现一次。结果不等于d/(x+d)。错误,正确方法：按用户采样,挑1/10的用户，观察它们的全部查询采样方法Hash(User ID)mod 10，把用户分到十个桶中选第一个桶的用户（hash后结果为0）挑2/10的用户怎么办？选前面两个桶,固定Size抽样,总是保持s个元素这s个元素，是对过去所有元素的均匀取样即：过去所有元素，进入这s个元素的概率相同直观方案：全存起来，然后从中随机挑s个大数据下，因为存储空间的限制，不可行流

4、方案进来一个新元素时，新元素以概率p进入s原有的s个元素按一定的概率从s中剔除,新元素进入S的概率p,假设已到达n个元素，它们以s/n的概率被采样，组成s个元素的集合新进来一个元素，一共到达了n+1个元素。这n+1元素，以相同概率进入s这个概率：s/(n+1)所以，这个新元素以s/(n+1)的概率进入sp=s/(n+1),S中原元素的剔除策略,原来在s个元素集合中的元素，随机剔除一个不被剔除的概率原先，这n个元素，是以s/n概率进入s的。这一轮过后，任一元素留在s中的概率和新到元素的留下概率s/(n+1)相等结果：所有n+1个元素，以s/(n+1)的概率留下,新元素不进s的概率,新元素进s，但

5、在s中不被剔除的概率,滑动窗口内计数,Sliding windows 滑动窗另一种取样方式,示例,N=6,应用：统计滑动窗中1的个数,频率简单方案FIFO，窗口大小：N存起来然后统计但是：N太大(Billion)/流太多(Billion)，存不下。怎么办？近似方案,统计滑动窗中1的个数,如果1均匀分布，容易估计从流开始时刻，统计1/0个数：S/Z估计窗口N内1的个数：如果1的分布不均匀呢？,DGIM方法,每个流，存储 比特结果误差不超过正确结果的50%可以进一步减少,DGIM,Datar,Gionis,Indyk,Motwani 指数窗口每个窗口中包括 i 个1，i:2的幂（指数增长）同样i的窗口最多可以有两个窗口不重叠，可以不连续（中间可以隔0）,16 8 8 4 4 2 2 1,DGIM需要的存储空间,每个子窗（Bucket）有一个时标，记录结束时间取值范围 1 N需要 比特存储空间每个bucket记录自己包含的1的个数取值范围：1lo