问题标签 [hyperloglog]

如果哈希的位模式中有 k 个前导零，为什么估计大小被认为是 2 ^k+1？不应该是^2k吗？k 前导零的概率应该是 1/(2 ^k )，因此大小应该是 2 ^k

在我的代码中，当我使用 k+1 而不是 k 时，我总是得到正确的大小估计。但我无法理解这背后的逻辑。

假设我在 redis 中有一个超级日志，它计算消息是否有任何规定，我可以在某种程度上说明删除消息？

Hyperlog 日志是一种概率算法根据 redis HLL 文档，我们可能会得到 0.81% 的错误，但我会得到 17-20% 的错误

我认为有问题.. 这是我的简单 perl 测试脚本。是不是有什么错误

我们有一个用例，我们希望在任何时间范围（小时粒度）内报告应用中的唯一身份访问者。

示例：假设在第 0 小时我们有以下访客 {A, B, C, D} 并且在第 1 小时我们有 {C, D, E, F} ，在第 2 小时我们有 {E, F, A, B} 和在第 3 小时，我们有 {A, C}。我们需要回答在第 1 小时和第 3 小时之间有多少唯一身份访问者，同时应该能够回答在第 0 小时到第 3 小时之间有多少唯一身份访问者等？

当然，我们不能保存所有唯一访问者 ID，但我们可以保存给定小时的 BloomFilter。

我打算使用包含-排除属性来计算联合，但想看看是否有任何框架或某个框架有一个好的解决方案。

大数据技术：我们有 hdfs 设置、hive 以及 Spark、Kafka。

首先让我先说我读过这个问题。

所以当我在互联网上闲逛时，我遇到了那个算法，我想知道它是如何工作的。在阅读了它之后，我确实理解了它是如何通过散列和使用位来计算视图的。

我还不太明白，如何才能确保避免再次计算相同的视图。我们是否存储了我们遇到的每个散列值，并且在增加计数之前检查它是否已经存在于我们的数组中或其他什么？

如果我们有 1000k+ 个项目，这不会降低效率吗？

我们可以使用 AggregatedMergeTree 表引擎，它可用于聚合行。

通常在聚合数据中，我们对存储所有唯一标识符不感兴趣，并且仍然希望进行不同的计数。我们仍然希望能够进行另一个聚合以在之后获得这些行的唯一计数（通过选择查询中的分组行）。这就是 HyperLogLog 派上用场的地方，它被实现为 clickhouse 中的 uniqState 函数。

我想通过插入查询直接存储一个超级日志，并从我的客户端应用程序将其提供给 clickhouse 表。这可能吗？

我正在评估分布式查询引擎，用于对大规模数据（~100GB）进行分析查询（交互式查询和批处理查询）。要求之一是计数不同的查询的低延迟（<= 1s），其中近似结果（最多 5% 的错误）是可以接受的。

Presto 似乎通过它的 approx_distinct() 来支持这一点。据我了解，它为此使用了 HyperLogLog。但是，除非数据以汇总形式与 HyperLogLog 值一起保存，否则必须动态计算。对于大型数据集，我认为我的查询不会在一秒钟内完成。

它是否支持在摄取时使用 HyperLogLog 计算汇总（类似于 Druid）？鉴于与 Druid 不同，Presto 从外部存储（Hive/Cassandra/RDBMS 等）查询数据，我不确定是否支持摄取时间汇总，除非 Presto 的本机存储支持它们。有人可以确认吗？

我对 Redis HyperLogLog 如何工作以及何时使用它有一些基本的想法。
在使用它之前，我做了一个测试：我pfadd在 HLL 条目中添加了一些连续的数字（以模仿用户 ID），Redis 很快给出了误报结果。确切地说，如果您将pfadd193 编号到 HLL 条目，则将报告编号 202 已存在于该条目中。你可以在 redis-cli 中测试它：

我知道 HyperLogLog 是一种概率数据结构，但是 HLL 不会太容易给出这样的误报吗？我是不是误会了什么？

我遇到过多种算法，例如 Flajolet-Martin 算法、HyperLogLog 来从元素列表中找出唯一元素，突然好奇 Java 是如何计算它的？在每种情况下存储和查找唯一值的时间复杂度是多少？

我正在研究 Redis 支持的数据结构，但找不到可以让我理解 HyperLogLog 是什么的解释。

我如何使用它，为什么这有好处？