问题标签 [hyperloglog]

我目前正在尝试为我在 BigQuery 中的自定义 Firebase 事件计算唯一用户。虽然我已经能够通过使用 APPROX_COUNT_DISTINCT 函数获得聚合中的数字，但在 SELECTING 并向表中添加多个不同维度时，我仍然无法获得正确的（唯一）计数。

以下关于使用 HLL_COUNT.INIT 的资源让我更近了一步，但我还没有弄清楚如何在同一个表中使用 HLL_COUNT.MERGE 函数，因此我可以通过在 datastudio 中应用过滤器来获取事件 + 唯一用户计数

到目前为止我使用的查询：

有没有人对我如何达到重点有任何想法，该表格允许我回答以下问题 - 过去 x 天内有多少来自德国的独立用户触发了事件？- 在过去的 x 天内，有多少独立用户触发了难度级别为 5 的事件？- 在过去的 x 天内，有多少独立用户请求了以下资源？</p>

谢谢

如果我想在可以添加和删除的元素列表中获取唯一计数，有没有办法做到这一点？

例如

应该给出一个唯一的计数 1

但是如果我有一个 2 hll 一个用于删除和一个用于添加的天真方法，它返回 0？

有没有办法可以在 hll 中删除密钥？

在 redis 中，我们将hyperLogLog视为设置为不同的元素。

众所周知，对于每个键，HLL 仅消耗 12kb 内存，并产生标准误差为 0.81% 的近似值

因为我要计算的元素太多了。所以在这里我想通过将元素存储到多个 hll 键中来降低错误发生率（例如 "hll_key_%d" % (Element mod 1024) ）

实际上这是降低错误的有效方法吗？或者任何其他方式来实现？

根据这个 StackOverflow 问题，概率数据结构是给出近似而非精确答案的数据结构。特别是，它们的时间和空间复杂性非常低，并且易于并行化，这使得它们的使用效率非常高。提供的示例包括 Bloom Filters、Count-Min Sketch 和 HyperLogLog。

然而，所有这些数据结构也被称为“草图”数据结构——通过紧凑表示来近似一个大集合的结构，以实现更有效（但不太精确）的操作。

我看不出“草图”和“概率”数据结构之间的区别。

我有一个有点大的表（1.3 亿行），我能够在 10 分钟内在同一台服务器上处理它，并生成一个精简的预聚合表，它工作得很好，每个人都乐于使用它.

该表由大约 6 列分组，其余列与HLL优化的SUM()或各种聚合。COUNT(DISTINCT myColumn)

使用这个小结果表的人可以仅按原始列的 1 或 2 个进行分组，以获得更广泛的摘要。只有在最后一步才会产生实际计数

结果以毫秒为单位产生。

问题是将其作为 Hyper 中的提取物移至Tableau，因为人们想在那里使用它。Tableau 不了解 HLL，它希望自己进行非重复计数。然而，推送所有这些原始数据非常慢（比如慢了 5 小时）。

我愿意在速度上妥协，但不会从 10 分钟缩短到 5 小时。有没有办法将当前表示为 HLL 的集合作为一整列传输？像数组或 JSON 之类的？

我在这里发现了一个类似的问题，但更多的是关于 Cassandra，而不是关于 Tableau 数据提取。

使用 Tableau 从 cassandra 列中查找不同计数

总结一下：
我如何将预先聚合的行传递给 Tableau，并且仍然能够COUNT(DISTINCT x)在 Tableau 端产生有效的计算？

从这个stackoverflow帖子

The main trick behind this algorithm is that if you, observing a stream of random integers, see an integer which binary representation starts with some known prefix, there is a higher chance that the cardinality of the stream is 2^(size of the prefix).

Hyperloglog 使用散列来实现随机性，但是如何证明散列一个值会产生随机输出呢？或者更严格地说，哈希是否保证像均匀输出一样的伪随机？

如果散列不能保证均匀输出，有没有办法可以对散列函数的非均匀性进行上限和量化？

示例相关表架构：

我需要在滚动时间段（90 天）内对大型数据集上的活跃不同用户进行计数，并且由于数据集的大小而遇到问题。

起初，我尝试使用窗口函数，类似于这里的答案。 https://stackoverflow.com/a/27574474

然而，这导致每天获得不同数量的用户，然后将它们相加 - 但如果它们出现多次，则不同可能会在窗口内重复。因此，这并不是对 90 天内不同用户的真正准确衡量。

我尝试的下一件事是使用以下解决方案 https://stackoverflow.com/a/47659590 - 将每个窗口的所有不同 user_ids 连接到一个数组，然后计算其中的不同点。

然而，这很快就用完了任何大的内存。

接下来是使用 HLL 草图以小得多的值来表示不同的 ID，因此内存问题就不那么重要了。我以为我的问题已经解决了，但是在运行以下命令时出现错误：错误只是“不支持函数 MERGE_PARTIAL”。我也尝试了 MERGE 并得到了同样的错误。它仅在使用窗口功能时发生。为每天的价值创建草图效果很好。

我通读了 BigQuery Standard SQL 文档，没有看到任何关于 HLL_COUNT.MERGE_PARTIAL 和 HLL_COUNT.MERGE 的窗口函数。大概这应该取 90 个草图并将它们组合成一个 HLL 草图，代表 90 个原始草图之间的不同值？

“错误图像 - 不支持函数 MERGE_PARTIAL”

任何想法为什么会发生此错误或如何调整？

我想在 Redis 数据库之上为分布式爬虫系统实现 URL 过滤（例如，不要两次访问同一个 URL，所以我需要以某种方式以最小的内存指纹跟踪所有这些，不需要存储完整的URL，只需检查是否访问过某个特定的 URL）。在这种情况下，布隆过滤器听起来很合适，我看到了一个用于 Redis 的本机模块，用于实现布隆过滤器。但它也有内置的 HyperLogLog 数据结构，所以我想知道在我的场景中哪个是更好的选择。

在 redis 主从 4.0.9 中使用超日志键时，我们有一个pfcount.52161862

现在，当我们通过它添加一个独特的项目时，pfadd它返回零并且 count 仍然是52161862。

知道为什么我们不能向这个键添加更多独特的项目吗？

我目前正在使用 hyperloglog 来估计集合的基数（唯一项目的数量）

计算 2 个集合的并集的基数和 2 个集合的交集的基数 ( |A intersect B| = |A| + |B| - |A union B|)非常简单

但是我找不到一种方法将联合和交集的运算符链接在一起（注意：只允许计算基数而不是交集的超对数的方法，即可以通过A union B而不是得到一个新的超对数A intersect B）。

是否有替代算法可以估计链式联合和交集结果的基数？