我最近在闲暇时间学习了不同的算法,而我遇到的似乎非常有趣的算法叫做HyperLogLog算法 - 它可以估算列表中有多少独特的项目.

这对我来说特别有趣,因为它让我回到了我的MySQL时代,当我看到"基数"值时(我总是假设它直到最近计算得不是估计的).

所以我知道如何在O(n)中编写一个算法来计算数组中有多少个唯一项.我用JavaScript写了这个:

function countUniqueAlgo1(arr) {
    var Table = {};
    var numUnique = 0;
    var numDataPoints = arr.length;
    for (var j = 0; j < numDataPoints; j++) {
        var val = arr[j];
        if (Table[val] != null) {
            continue;
        }
        Table[val] = 1;
        numUnique++;
    }
    return numUnique;
}

但问题是我的算法,而O(n),使用了大量的内存(存储值Table).

我一直在阅读这篇论文,关于如何在O(n)时间内使用最少的内存来计算列表中的重复项.

它解释了通过散列和计数比特或某事物,可以在一定概率内(假设列表均匀分布)估计列表中的唯一项目的数量.

我读过这篇论文,但我似乎无法理解它.有人能给出更多非专业人士的解释吗？我知道什么是哈希,但我不明白它们如何在这个HyperLogLog算法中使用.

哪里可以找到LogLog算法的有效实现？试图自己实现它,但我的草案实现产生了奇怪的结果.

这是:

function LogLog(max_error, max_count)
{
    function log2(x)
    {
         return Math.log(x) / Math.LN2;
    }

    var m = 1.30 / max_error;
    var k = Math.ceil(log2(m * m));
    m = Math.pow(2, k);

    var k_comp = 32 - k;

    var l = log2(log2(max_count / m));
    if (isNaN(l)) l = 1; else l = Math.ceil(l);
    var l_mask = ((1 << l) - 1) >>> 0;

    var M = [];
    for (var i = 0; i < m; ++i) M[i] = 0; …

Flajolet 等人的HyperLogLog算法描述了一种仅使用少量内存来估计集合基数的巧妙方法.但是,它确实考虑了计算中原始集合的所有N个元素.如果我们只能获得原始N的一小部分随机样本(比方说,10%)怎么办？有没有关于HyperLogLog或类似算法如何适应这种情况的研究？

我知道这基本上是描述为不同价值估计的问题,对此存在大量研究(例如参见本文的概述).然而,我所知道的关于独特价值估计的研究使用了许多与HyperLogLog使用的方法截然不同的特别估计.因此,我想知道是否有人已经考虑过将HyperLogLog调整为不同的价值估计问题.

问题很简单:我需要根据Redis的表示找到最佳策略来实现准确的HyperLogLog联合 - 这包括在导出数据结构以供其他地方使用时处理它们的稀疏/密集表示.

两个策略

有两种策略,其中一种似乎要简单得多.我已经看过实际的Redis源代码了,我遇到了一些麻烦(在我自己的C中并不大),从精确和高效的角度来看,使用内置的结构/例程或开发自己的内容是否更好.对于它的价值,我愿意牺牲空间和某种程度上的错误(stdev + -2%)以追求效率与极大的集合.

1.包容性原则

到目前为止,两者中最简单的 - 基本上我只是将无损联合(PFMERGE)与此原理结合使用来计算重叠的估计.在许多情况下,测试似乎表明这种运行是可靠的,尽管我无法准确处理非常高的效率和准确性(某些情况下会产生20-40%的错误,这在这个用例中是不可接受的).

基本上:

aCardinality + bCardinality - intersectionCardinality

或者,在多组情况下......

aCardinality + (bCardinality x cCardinality) - intersectionCardinality

似乎在许多情况下都能很好地准确地工作,但我不知道我是否相信它.虽然Redis有许多内置的低基数修饰符,旨在规避已知的HLL问题,但我不知道野生不准确(使用包含/排除)的问题是否仍然存在大量差异很大的问题......

2. Jaccard Index Intersection/MinHash

这种方式似乎更有趣,但我的一部分感觉它可能与Redis的一些现有优化计算重叠(即,我没有从头开始实现我自己的HLL算法).

通过这种方法,我将使用MinHash算法的随机抽样箱(我不认为LSH实现值得麻烦).这将是一个单独的结构,但通过使用minhash获取集合的Jaccard索引,您可以有效地将union基数乘以该索引以获得更准确的计数.

问题是,我不太熟悉HLL,虽然我很想深入研究Google论文,但我需要在短期内实现可行的实施.有可能我忽略了Redis现有优化的一些基本考虑因素,或者在算法本身中,它允许计算上便宜的交叉点估计具有相当宽松的置信区间.

因此,我的问题:

如果我愿意牺牲空间(并且在很小程度上,精确度),如何使用redis最有效地获得N个巨大(数十亿)集的计算上便宜的交叉估计？

我们正在使用Twitter在Algebird中实现HyperLogLog.给定N和我们的系统中的检查,使用HyperLogLog估计逐渐增长的集合的当前大小并测试它是否多于或少于N,我们如何编写测试此检查的集成或系统测试,如果我们调用HyperLogLog的代码是正确的,几乎可以保证通过？被测系统是非确定性的,因为,一方面,它是多线程的.

我的第一个想法是,编写一个对这个用例可靠的集成测试的正确方法是"放弃我们的标准".那么,什么是足够数量的项目(M)发布到端点,以确保HyperLogLog将估计项目的总数超过N,概率,例如,> = 0.999999？

还是有更好的方法？

标准误差界限是可配置的,但这并不直接告诉我们偶尔可能看到的最大误差界限 - 这是我关心的,以避免随机失败的CI构建在主人身上造成浪费的时间和头发-pulling!

我还担心我们在测试中生成随机数据的方式可能不会在相关方面生成均匀分布的随机数据,这可能会对概率计算产生重大影响.

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

例如

add key1
delete key1
add key1

应该给出1的唯一计数

但如果我有一个简单的2 hll方法用于删除,一个用于添加,它返回0？

有没有办法可以在hll中重复键入？

假设我在redis中有一个超级日志，该超级日志记录邮件的数量，是否有任何规定可以在某种程度上解释删除邮件？

我自己实现了HyperLogLog algorithm.它运作良好,但有时我必须获取很多(大约10k-100k)的HLL结构并合并它们.

我将它们中的每一个存储为一个位串,所以首先我必须将每个位串转换为桶.由于有很多HLL,它需要的时间比我想要的多.

目前大约80%的运行时为每个HLL调用一行代码:

my @buckets = map { oct '0b'.$_ } unpack('(a5)1024', $bitstring);

有没有办法更快地做到这一点？

如果我们留下HyperLogLog的定义,那么任务可以这样解释:假设$bitstring由1024个5位计数器组成(因此每个计数器的值最多为32),我们必须将其转换为1024个整数的数组.

示例相关表架构：

+---------------------------+-------------------+
| activity_date - TIMESTAMP | user_id - STRING  |
+---------------------------+-------------------+
| 2017-02-22 17:36:08 UTC   | fake_id_i24385787 |
+---------------------------+-------------------+
| 2017-02-22 04:27:08 UTC   | fake_id_234885747 |
+---------------------------+-------------------+
| 2017-02-22 08:36:08 UTC   | fake_id_i24385787 |
+---------------------------+-------------------+

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

起初，我尝试使用窗口函数，类似于这里的答案。 /sf/answers/1930213211/

WITH
  daily AS (
  SELECT
    DATE(activity_date) day,
    user_id
  FROM
    `fake-table`)
SELECT
  day,
  SUM(APPROX_COUNT_DISTINCT(user_id)) OVER (ORDER BY day ROWS BETWEEN 89 PRECEDING AND CURRENT ROW) ninty_day_window_apprx
FROM
  daily
GROUP BY
  1
ORDER BY
  1 DESC

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

我尝试的下一件事是使用以下解决方案 …

我正在研究Redis支持的数据结构,我无法找到可以让我理解HyperLogLog是什么的解释.

我如何使用它,为什么这有用？

I\xe2\x80\x99m 设计一种算法，基于 60 分钟的滑动比例来计算一组页面上的唯一用户数

因此，它需要找到访问特定页面的唯一 IP（或令牌），并将过去 60 分钟内的点击次数总计起来

我需要它在规模上非常快（主要是为了写作，但阅读是一个额外的好处）。每个页面可以有 10,000 个用户乘以 1000 个页面。

我的研究表明我将 Redis 与 HyperLogLog 结合使用

我\xe2\x80\x99m 来自 Memcache 背景，刚接触 Redis。有人能给我任何指点吗？

谢谢

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

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

#!/usr/bin/perl -w                                                                                                                                                       
use Redis;
my $redis = Redis->new(server=>'192.168.50.166:6379') or die;
my $fp=0;
my $HLL="HLL";

$redis->del($HLL);
foreach my $i (1..10000) {
  my $s1 = $redis->pfadd($HLL,$i);
  if($s1 == 0){ 
    print "False positive on $i\n";
    $fp++;
  }
}
print "count of false positives $fp\n";

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