Arithmetic Variable LogLog: Advancing the Memory-Variance Frontier
本文介绍了算术变量 LogLog (AVLL)，这是一种新的基数估计算法，它通过利用算术编码和早期退出机制，在所有测试规模上都实现了更优的内存-方差乘积，从而在准确性和速度上均超越了最先进的 ExaLogLog。
原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
想象一下，你正在经营一场规模宏大的派对，数以百万计的宾客正涌入大门，而你手里只有一个小小的笔记本来记录谁来了。你无法写下每一个人的名字——否则你的笔记本会瞬间填满。相反，你需要一种聪明的技巧，在不逐一计数的情况下，就能猜出有多少个“独特”的人已经到场。这就是“基数估计”（cardinality estimation）的问题，这个谜题几十年来一直令计算机科学家们着迷。目标是在尽可能少的内存空间内，榨取出最准确的猜测。
长期以来，最好的方法就像拥有一排储物柜，每个储物柜的大小各不相同。你会根据一个随机代码将宾客的名字投进某个储物柜，如果储物柜是空的，你就做一个标记。如果它已经被填满了，你会检查新来的宾客是否比原有的宾客更“独特”。你拥有的储物柜越多，你的猜测就越准确。但有一个问题：为了获得超高的准确度，你必须要么拥有更多的储物柜（这会占用更多空间），要么拥有更大的储物柜（能存储关于每个宾客的更详细信息）。多年来，争论一直在于：是拥有一些巨大的、细节丰富的储物柜更好，还是拥有一大群微小的、简单的储物柜更好？
一位名为 AVLL（算术可变 LogLog） 的新竞争者登场了。把它想象成一个魔术师，他意识到旧有的打包方式太浪费了。AVLL 没有使用那些固定大小的槽位，而是使用了一种灵活的、“算术式”的打包方法，能在同样的空间里塞进更多的微型储物柜。论文指出，通过挤进 5.5 倍于以往的微型储物柜，即使每个单独的储物柜承载的信息较少，该系统也能做出比之前的冠军更好的猜测。这就像是意识到，拥有 1,000 个微型、快速观察的摄像头，比拥有 200 个巨型、慢动作的摄像头能拍到更清晰的人群画面。
论文的核心发现
作者 Brian Bushnell 将 AVLL 描述为一种计算数据流中唯一元素数量的新方法。他们发现，通过使用一种被称为“基数-56 算术编码”（base-56 arithmetic encoding）的巧妙数学技巧，他们可以将 11 个寄存器（即数字储物柜）打包进单个 64 位字（64-bit word）的计算机内存中。在过去，标准方法在试图将这些寄存器放入固定槽位时会浪费大量的比特，但 AVLL 利用了每一个比特，实现了零浪费。
这种打包技巧让 AVLL 获得了巨大的优势：在 1 KB 的内存大小下（这在计算机术语中非常微小），AVLL 可以存储 1,408 个寄存器，而之前的最先进方法——名为 ExaLogLog 的方法——在同样的空间内只能容纳 256 个寄存器。这带来了 5.5 倍 的观测数量优势。
论文表明，这种“多即是好”的方法效果极佳。在使用了 128,000 次独立模拟 的测试中，AVLL 在 1 KB 内存下的宽度加权平均绝对误差（width-weighted mean absolute error）为 1.63%。相比之下，ExaLogLog 的误差为 1.71%。虽然这看起来差距不大，但在高精度计数的领域，这是一个显著的胜利。作者计算出，AVLL 的“内存-方差乘积”（衡量内存使用效率的分数）约为 3.4，这比 ExaLogLog 的实际得分 3.78 以及它的理论最佳值 3.67 都要低（因此表现更好）。
加速计数
但 AVLL 不仅仅是更准确，它还出奇地快，尤其是在计算机繁忙的时候。论文描述了一种称为“提前退出”（early exit）的机制。想象一下派对门口的一名保安，他无需查看名单，就能立刻判断出某位宾客是否是已经见过的人。AVLL 通过将宾客的代码与一个全局“底限”（floor）值进行比较来实现这一点。如果代码低于该底限，该宾客会被立即忽略，系统甚至不会去触碰存储储物柜的内存。
在模拟数千个此类计数系统同时运行（模拟拥挤的计算机缓存）的测试中，AVLL 比 ExaLogLog 快了 2.7 到 4.5 倍。这是因为 ExaLogLog 必须为每一个项目检查其内存，即使是重复项也是如此；而 AVLL 在重复项到达寄存器之前，就通过过滤掉绝大多数重复数据，让它们无法触及内存。在高唯一值数量的情况下，AVLL 会拒绝大约 96% 的输入数据而不触碰寄存器，从而保持系统平稳运行。
这意味着什么（以及并不意味着什么）
论文明确排除了“更丰富”的寄存器（例如 ExaLogLog 那种存储详细历史记录的 32 位大型储物柜）总是更好的这一观点。结果表明，对于这类特定类型的计数问题，拥有更多独立的观测值（更多的寄存器）比拥有单次观测中更丰富的数据更有价值。
然而，作者也谨慎地指出，AVLL 在严格意义上并不是“幂等的”（idempotent）。这意味着，如果你将完全相同的重复数据喂给系统两次，它的行为可能与只喂一次时略有不同，尽管论文显示在处理大量重复数据的实际测试中，其准确度并未下降。他们也承认，他们的“HLDLC”估计器是一个通过大规模模拟得出的不同数学公式的巧妙结合体，而不是像 ExaLogLog 那样拥有经过数学证明的“完美”极大似然估计器。
论文最后总结道，AVLL 是一个自包含的工具（以单个 Java 类形式编写），已准备好投入使用。它能够处理海量数据而不会耗尽用于计数器的内存空间，并且无论数据是混乱的唯一项混合还是重复的流式数据，它都能同样出色地工作。其核心信息是一种理念的转变：在内存效率的战斗中，密度胜过丰富度。通过在同样的空间内打包更多简单的、独立的计数器，我们可以得到更清晰、更快、更准确的数据流图景。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。