问题标签 [count-min-sketch]

我有一个值不断增加的大数组 - 像这样：

我想在上面使用插值搜索算法。数组的大小是可变的，新元素被添加到数组的末尾。

我需要找到某个元素的索引，我们称它为 X。

Y 必须是数组中元素的索引，这样 array[Y] >= X find可以使用二进制搜索来实现，但由于某些复杂的原因，我想使用插值搜索来实现它。插值搜索试图通过查看数组的边界来猜测 X 的正确位置。如果第一个数组值是 0，最后一个是 100，我想找到值 25 的位置，如果数组长度是 1000，我需要先查看索引 250 处的值。如果数组的值是均匀分布的，这很有吸引力。但如果它们分布不均匀，插值搜索的工作速度可能比二分搜索慢（可能有一些优化）。

在这种情况下，我正在尝试使用Count-Min Sketch数据结构来加快搜索速度。当我将新元素附加到数组时，我只是将一些数据添加到 count-min 草图数据结构中。

使用这种方法，我可以大致猜测搜索到的元素 X 的位置。如果猜测正确，这可能会导致搜索速度加快，但我遇到了一些问题。

1. 我不知道 X 是否在数组中并且我count_min_sketch已经看到了这个值。如果是这种情况，我可以从数据结构中获得正确的值count_min_sketch。如果不是 - 我将得到 0 或其他值（最坏的情况）。

2. 碰撞。如果我的对象已经看到了值 X，那么count_min_sketch我会得到正确的值或更大的值。如果 count min sketch 用于计算文档中的单词出现次数 - 这不是问题，因为碰撞很少见并且错误小于或等于碰撞次数（它通常像这样使用：count_min_sketch.add(Z, 1)）。就我而言，每次碰撞都可能导致大错误，因为我通常为每个键添加大量数字。

是否可以以这种方式使用 count-min 草图（每次添加大量条目）？

我的集合中的元素数量超过十亿 2 ³⁰。我打算计算集合中每个元素的出现次数。为此，我想使用 count-min 草图。请建议如何选择散列函数。我的申请最多可以容忍5%的误报率。

Count-Min 草图的宽度（桶数）和深度（哈希函数数）决定了检索到的频率估计的准确性。

来自Count-Min 原作者2005 年的论文：

参数 w 和 d 可以通过设置 w=⌈e/ε⌉ 和 d=⌈ln1/δ⌉ 来选择，其中回答查询的误差在 ε 的因子内，概率为 δ。

如上所述：

来自Count-Min 原作者2011 年的论文：

假设我们希望误差最多为 0.1（所有频率之和），确定性为 99.9。那么我们要2/w=1/1000，我们设w=2000，且(1/2)^d=0.001，即d=log0.001/log0.5 ≤ 10。

导致：

然而，误差必须取决于存储在草图中的元素总数 N。元素越多，错误和错误概率就越大。为了创建初始草图，什么是合适的功能？

我通过阅读论文研究了 count min sketch (CMS)：http: //dimacs.rutgers.edu/~graham/pubs/papers/cmsoft.pdf

但是我没有阅读算法的经验，所以有些混乱。有人可以帮忙回答一些关于count min sketch的问题。

• 假设深度为 d，w 为 w，那么我最多可以向 CMS 添加多少元素，这样就不会影响错误率
• 我想通过向 CMS 添加大量元素然后查询放入 CMS 的所有键来对 CMS 进行测试。如何计算误差和评估误差？
• 如果我将 CMS 用作 web 服务的重击者，并且我的 web 服务每天都在运行，那么有一天，计数器会溢出。那么我应该每天创建然后删除 CMS 吗？

谢谢！

Count min sketch 使用不同的散列函数将流中的元素映射到散列函数。如何从草图映射回来以找到最常见的项目？考虑到已经传递了足够多的元素（数百万）并且我们不知道这些元素。

所以Count-Min Sketch的重点是根据提供的哈希函数的结果更新某些计数器。但是，这些计数器在内存中是有限的，并且在运行相当长的一段时间后，它们可能会溢出，从 MAX 值下降到 MIN 值（就像整数一样）。假设我需要的是草图中最常见的 N 个值，除了每隔一段时间重新启动草图之外，有没有办法避免这种情况？

我爱上了概率数据结构。对于我目前的问题，似乎 count-min-sketch 结构几乎是正确的候选者。我想使用 count-min-sketch 来存储每个 ID 的事件。

假设我确实有以下

如果我使用 count-min-sketch，我可以通过 ID 查询数据结构并检索 ~counts。

问题

实际上，我对所有 ID 的平均出现次数感兴趣，在上面的示例中为：12,33。如果我使用的是 count-min，那么似乎我需要存储一组 ID，然后遍历该组并查询每个 ID 的 count-min 并计算平均值。有没有不存储所有 ID 的改进方法？理想情况下，我只想立即检索平均值而不记住所有 ID。

希望有道理！？

我需要在流中存储前 k 个最常见的元素。为了估计频率，我使用 count-min-sketch 算法。我的流由键（作为字符串）组成。所以基本上每次我在我的流中遇到一个新键时，我都会通过查看 count-min-sketch 数据结构来计算当前键的频率。但是我无法存储前 k 个最常用的键。

我的第一个想法是将它们存储在一个固定大小为 k 的最小堆中。我用比较器比较频率将 [频率，键] 存储在这个最小堆内。所以每次我得到一个密钥的频率时，我都会尝试查看堆大小是否超过 k，如果是，那么我将当前密钥的频率与最小堆中的顶部（最小）频率进行比较，如果我当前的密钥是频率大于我弹出顶部，然后将我的密钥插入堆中。

但是我意识到最小堆不是一个集合，这意味着它允许重复。假设我有一个非常热的键，并且我一直在流中对其进行计数，所以每次我将此 [频率，键] 插入堆时，最终我的堆将充满相同的键，只是频率不同。

所以我想知道是否有一种好方法可以将前 k 个不同的更频繁的元素存储在 count-min-sketch 中。

我正在阅读 Count-Min Sketch 数据结构，它根据错误概率参数和容差参数为点和范围查询提供概率答案。例如，CM 可以回答“项目 x 以 10% 的概率出现在数据流中的次数”这个问题。

重击者的相关问题也出现了。在为 HH 问题实现最小堆时，我注意到各种研究论文指出，只有当草图中项目的最小计数大于阈值时，我们才插入堆中。

我的问题是，这是否意味着我们正在概率性地回答重击手问题？相应的问题会是“有 10% 的概率，哪个项目是数据流中第二频繁的？”

我正在尝试用 JavaScript 实现 count-min 草图。由于我需要一些哈希函数，我无法弄清楚我可以/应该/必须使用哪些。有什么建议么？

如果这个问题很愚蠢，我将不胜感激。谢谢