\( \def\vector#1{\boldsymbol{#1}} \)

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

Takami Torao 2007年の論文 #HyperLogLog #BigData
  • このエントリーをはてなブックマークに追加
Philippe Flajolet 1 and Éric Fusy 1 and Olivier Gandouet 2 and Frédéric Meunier 1
1 Algorithms Project, INRIA–Rocquencourt, F78153 Le Chesnay (France)
2 LIRMM, 161 rue Ada, 34392 Montpellier (France)

概要

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

  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 年の論文。