論文翻訳: HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm

概要

この Extended Abstract は、非常に大きなデータアンサンブルの一意な要素の数 (基数) を推定することに貢献する、ほぼ最適な確率的アルゴリズムである HYPERLOGLOG を詳述し分析する。HYPERLOGLOG は、\(m\) 単位 (通常は "小さなバイト数”) の補助メモリを使用し、データを一度捜査して相対精度 (標準誤差) が通常約 \(1.04/\sqrt{m}\) となるように基数の見積もりを生成する。これにより既知のカーディナリ推定値である LOGLOG を改善し、元のメモリの 64% しか消費せずに精度を一致させることができる。例えばこの新しいアルゴリズムはわずか 1.5 キロバイトのメモリを使用しながら、一般的に 2% の精度で 109 を超えるカーディナリを見積もることを可能にする。アルゴリズムは適切に並列化され、スライディングウィンドウモデルに適応する。

Table of Contents

1. 概要
2. Introduction [under construction]
3. 1 The HyperLogLog algorithm
4. 2 Mean value analysis
   1. 2.1 Exact expressions
   2. 2.2 Asymptotic analysis under the Poisson model
   3. 2.3 Analysis under the fixed-size model (depoissonization)
5. 3 Variance and other stories
   1. 3.1 Valiance analysis
   2. 3.2 Constants
6. Discussion
7. References
8. 翻訳抄

Introduction

1 The HyperLogLog algorithm

2 Mean value analysis

2.1 Exact expressions

2.2 Asymptotic analysis under the Poisson model

2.3 Analysis under the fixed-size model (depoissonization)

3 Variance and other stories

3.1 Valiance analysis

3.2 Constants

Discussion

References

翻訳抄

大量のデータから要素数を推定するアルゴリズム HyperLogLog に関する 2007 年の論文。

• 原文: HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm