algorithm - Google Trends的系统设计？

Question

我正在尝试找出 Google 趋势背后的系统设计(或任何其他此类大规模趋势功能，如 Twitter)。

挑战:

• 需要处理大量数据来计算趋势。

• 过滤支持 - 按时间、地区、类别等

• 需要一种存储归档/离线处理的方法。过滤支持可能需要多维存储。

这就是我的假设(我对 MapReduce/NoSQL 技术的实践经验为零)

用户的每个搜索项都将维护一组将被存储并最终被处理的属性。

以及按时间戳、搜索区域、类别等维护搜索列表。

示例:

正在搜索 Kurt Cobain 术语:

Kurt-> (Time stamp, Region of search origin, category ,etc.)

Cobain-> (Time stamp, Region of search origin, category ,etc.)

问题:

• 他们如何有效地计算搜索词的频率？

• 换句话说，给定一个大数据集，他们如何以分布式可扩展的方式找到前 10 个频繁项？

Answer 1

好吧...找出 HitTest 门的 K 个术语并不是什么大问题。该领域的一个关键思想是“流处理”的思想，即在单次数据传递中执行操作并牺牲一些准确性以获得概率答案。因此，假设您获得如下数据流:

A B K A C A B B C D F G A B F H I B A C F I U X A C

你想要的是前K项。天真地，人们会为每个项目维护一个计数器，并在最后按每个项目的计数排序。这需要 O(U) 空间和 O(max(U*log(U), N)) 时间，其中 U 是数字唯一项的数量，N 是列表中的项数。

如果 U 很小，这并不是什么大问题。但是，一旦您进入具有数十亿或数万亿次唯一搜索的搜索日志领域，空间消耗就开始成为一个问题。

因此，人们想出了“计数草图”的想法(您可以在此处阅读更多信息:count min sketch page on wikipedia)。在这里，您维护一个长度为 n 的哈希表 A 并为每个项目创建两个哈希:

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 个具有最大频率估计的项目的列表，最后您将得到您的列表。