问如何对分布式数据的算术均值进行排序和限制？

EN

键和数据库节点的基数是什么？假设您有数十亿个密钥和数十个数据库节点。让我们调用节点数'n‘。现在，要解决这个问题，我们需要三个步骤：

1. 找到前1000名候选键的子集。
2. 通过聚集所有节点计算它们的平均值。
3. 从结果中选择前1000个值。

让我们看看每个步骤的最佳可能算法。

查找候选密钥：

1. 每个节点计算每个密钥的本地平均值和本地出现数。
2. 现在每个节点都有每个密钥的(键、均值、出现次数)。
3. 每个节点都选择本地顶部k，其中1
4. 每个节点在本地顶级k中找到最小平均值。

H 117第4步中的值是选择顶级k键的本地截断。H 218H 119H 119现在从所有节点中选择最小的本地截断。H 220h 121/code>步骤6中的值是全局截断。只有较高的键才意味着在下一步中会考虑这个全局关机。。

计算全局平均值并选择前1000：

每个节点向公共节点发送平均值高于全局截止值的所有键的本地值(键、均值、出现项)。公共节点通过每个节点的平均值和出现次数来计算每个键的平均值。公共节点选择顶部1000。如果k低于1000，则步骤3可能找不到1000个唯一键，然后我们需要运行另一轮排除selected.

• Local平均计算不需要重复的键，只需要更改全局截断。G 235

对于最优的解决方案，您需要根据节点数目、密钥和节点间的密钥复制来优化算法。