给定键值对的多个数据库节点(其中key是非唯一的(,如何通过key计算前1000个算术平均数?
由于数据量太大,计算所有算术平均值并对其进行排序不是一种选择。
可行的方法可能会以某种方式限制关键的处理空间,但如何呢?
键和数据库节点的基数是多少?假设您拥有数十亿个密钥和数十个数据库节点。让我们把节点的数量称为"n"。现在,要解决这个问题,我们需要三个步骤:
- 查找前1000个候选键的子集
- 通过聚合所有节点来计算它们的平均值
- 从结果中选取前1000个值
让我们看看每一步的最佳算法。
查找候选密钥:
- 每个节点计算每个键的局部平均值和局部出现次数
- 现在,每个节点为每个关键点都有(关键点、平均值、出现次数(
- 每个节点选取局部顶部k,其中1<k<=1000
- 每个节点在局部顶部k中找到最低的平均值
- 步骤4中的值是选择前k个键的本地截止值
- 现在,在所有节点上选择最小局部截断
- 步骤6中的值是全局截止值。只有具有更高值的键意味着在下一步中会考虑此全局截止
计算全局平均值并选择前1000名:
- 每个节点将平均值高于全局截止值的所有关键帧的局部(关键帧、平均值、出现次数(发送到公共节点
- 公共节点使用每个节点的平均值和出现次数来计算每个关键字的平均值
- 公共节点选择前1000个
- 如果k低于1000,步骤3可能找不到1000个唯一密钥,那么我们需要运行另一轮,排除我们选择的密钥
- 局部平均值计算不需要在下一轮中重复,只需要更改全局截止值
为了获得最佳解决方案,您需要根据节点数量、密钥和跨节点的密钥重复来调整算法。