我正在尝试找出 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 个频繁项？
嗯...找出前 K 项并不是一个大问题。该领域的关键思想之一是“流处理”的思想，即在单次数据传递中执行操作并牺牲一些准确性以获得概率性答案。因此，假设您获得如下数据流：
ABKACABBCDFGABFHIBACF IUXAC
你想要的是前 K 项。天真地，人们会为每个项目维护一个计数器，最后按每个项目的计数进行排序。这需要O(U)空间和O(max(U*log(U), N))时间，其中U是唯一项N的数量， 是列表中的项数。
如果情况U很小，这并不是一个大问题。但是，一旦您进入具有数十亿或数万亿次唯一搜索的搜索日志领域，空间消耗就开始成为一个问题。
因此，人们提出了“计数草图”的想法（您可以在此处阅读更多内容：count min sketch page on wikipedia）。在这里，您维护一个长度为 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 个项目的列表，最后您将获得您的列表。