algorithm - 如何高效获取分布在N台电脑上的top K词？

Question

假设我们有很多词分布在 N 台计算机上，我们想要前 10 个频繁出现的词。 我可以想到三种方法:

1. 分别统计每台N台电脑上的单词，我们可以得到每台电脑上排名前20(这个数字可以讨论)的单词。将这些结果合并在一起。

   这种方法的缺点是有些词可能会被忽略。这些词在每台计算机上均匀分布，但不可能在每台计算机上都排在前20位，但这些词的总频率可能在前10位。

2. 它和第一个几乎一样。不同之处在于在每台计算机上获取所有计数结果并将它们合并。然后计算TOP 10。

   缺点是合并时间和传输时间比较大。

3. 使用良好的散列函数重新分配单词。不同的计算机不会有相同的单词。然后我们可以在每台计算机上获取 TOP 10 并将它们合并。

   缺点是每个单词都会被散列并传输到另一台计算机。这将花费很多传输时间。

你有更好的方法吗？或者我的哪种方法最好？

Answer 1

您在 #1 中的想法很好，但需要更好的执行。如果 F 是单台计算机上第 K 个最常见的词的频率，那么所有 N 台计算机上频率小于 F/N 的词都可以忽略。如果将机器分成 G 组，则应用阈值 F'/G，其中 F' 是单个组内计算机上第 K 个最常见单词的频率。

在两轮中，计算机可以确定 F 的最佳值，然后聚合一个小的 Bloom 过滤器，该过滤器命中所有频繁出现的单词，并对其他一些单词给出误报，用于减少与方法 #2 合并的数据量和#3。