mit*_*hya 9 algorithm system trend
我试图找出谷歌趋势背后的系统设计(或任何其他像Twitter这样的大规模趋势功能).
挑战:
需要处理大量数据来计算趋势.
过滤支持 - 按时间,地区,类别等
需要一种存储进行存档/离线处理的方法.过滤支持可能需要多维存储.
这就是我的假设(我对MapReduce/NoSQL技术没有实际经验)
来自用户的每个搜索项将维护将被存储并最终处理的一组属性.
以及按时间戳,搜索区域,类别等维护搜索列表.
例:
搜索Kurt Cobain术语:
Kurt-> (Time stamp, Region of search origin, category ,etc.)
Cobain-> (Time stamp, Region of search origin, category ,etc.)
题:
他们如何有效地计算搜索词的频率？
换句话说,给定一个大型数据集,他们如何以分布式可扩展方式找到前10个频繁项目？
嗯...找出前K个术语并不是一个大问题.该领域的关键思想之一是"流处理"的概念,即,在单次传递数据中执行操作并牺牲一些准确性来获得概率答案.因此,假设您获得如下数据流:
ABKACABBCDFGABFHIBACF IUXAC
你想要的是前K项.天真地,人们会为每个项目维护一个计数器,最后按每个项目的计数排序.这需要O(U)空间和O(max(U*log(U), N))时间,其中U是唯一项目N的数量,并且是列表中的项目数.
如果U很小,这不是一个大问题.但是,一旦您进入具有数十亿或数万亿独特搜索的搜索日志域,空间消耗就开始成为问题.
所以,人们提出了"计算草图"的想法(你可以在这里阅读更多内容:在维基百科上计算最小草图页面).在这里,您维护一个长度为哈希的表A,n并为每个项创建两个哈希:
h1(x) = 0 ... n-1 具有统一概率
h2(x) = 0/1 每个概率为0.5
然后你这样做A[h1[x]] += h2[x].关键的观察是,由于每个值随机哈希到+/- 1,E[ A[h1[x]] * h2[x] ] = count(x)其中E是表达式的期望值,count是流中出现的次数x.
当然,这种方法的问题在于每个估计仍然具有很大的方差,但是可以通过维护大量的散列计数器并从每个集合中获取平均值或最小值来处理.
使用此草图数据结构,您可以获得每个项目的近似频率.现在,您只需维护一份包含迄今为止频率估算值最高的10个项目的列表,最后您将获得列表.