1

我有很多分类分布。分类分布是描述从一组 k 事件中抽取的事件的概率。我需要能够非常快速地访问事件的概率。

存储分类分布的一种方法是在 Redis 中使用排序集。每个键索引一个单独的分布，排序集的每个成员都是一个特定事件，每个分数是您看到该事件的次数。对于每个键（分布），您还将存储该分布中每个事件的计数总和，以便您可以正确规范化。

我想问的问题是：如果概率随时间变化，那么存储这些数据的好方法是什么？我基本上希望能够忘记旧的观察结果 - 即以某个固定间隔减少每个键的分数和归一化常数。

使用上面的 redis 方法，我可以每 d 分钟运行一次 cron 作业，迭代每个分布并减少 zscore 和标准化常数中的每个计数。但是，这似乎有点错误（我确定我妈妈告诉我永远不要迭代 KEYS *），所以我想知道是否有其他人更全面地解决了这个问题？

4

1 回答 1

1

我猜你感觉不对是以下几种组合：

  1. 每次运行 cron 作业时都需要访问每个分布、每个 ZSET 的每个成员以及规范化常数
  2. 随着时间的推移，无条件递减操作将偏斜分布以支持每个 cron 周期多次发生的事件的方式

我以前没有做过这样的事情，但是如果你能够腾出更多的存储空间，我会想到一个解决方案。

这个想法是定期存储带有时间戳的快照队列。每个快照代表该时间间隔内分布中的事件计数。当您想要使分发中的旧概率过期时，您可以将过期的快照从列表中弹出并相应地减少 ZSET。

更具体地说，您需要：

  1. 跟踪在区间 [ t k - t k-1 ) 期间发生的事件以及每个事件发生的次数——一组 (event, count) 对。这是对您当前所做的 ZSET 分数和归一化因子的（大概）实时更新的补充。
  2. 在每个滴答t k，存储快照：
    1. 创建一个唯一的密钥S k来表示t k处的快照——比如 UUID 或类似的
    2. 对于快照中的每个事件E，创建一个唯一的哈希键q(E)。选择允许您恢复该事件的分发 (ZSET) 密钥和事件（成员）密钥的密钥编码。
    3. 使用事件键q(E)和事件计数E调用HSET S k以存储事件数据。对快照中的所有事件重复此操作。||
    4. RPUSH SNAPSHOTS <timestamp>:SK _
  3. 在每个到期时间 t m，使旧快照到期：
    1. LPOPSNAPSHOTS 列表，解码时间戳并验证是否过期。
    2. 如果没有过期，LPUSH它会回到 SNAPSHOTS 列表中，直到下一个过期滴答为止。否则...
    3. 解码快照密钥S k
    4. 使用HKEYS S k的结果，解码每个事件密钥q(E)，获得相应的计数，然后将相应的 ZSET 和归一化因子减少该数量。
    5. 在 SNAPSHOTS 列表中仍然存在过期快照时重复。

所需的额外存储量将取决于快照和到期间隔的长度以及每个快照间隔内发生的不同事件的数量。

在最坏的情况下，每个分布和事件都将在每个快照中表示，因此这对错误因素 #1 没有帮助。乐观地说，任何快照中都将表示适当比例的分布和/或事件，并且到期过程的效率将提高。但这将解决错误因素 #2，即使在最坏的情况下，因为最近发生的事件不会在每次到期 cron 作业运行时在您的分布中无条件地减少。

于 2012-09-05T22:38:30.733 回答