$30 off During Our Annual Pro Sale. View Details »

確率的データ構造を使って巨大な集合を定数メモリで近似しよう

 確率的データ構造を使って巨大な集合を定数メモリで近似しよう

巨大な集合に対して、定数メモリ&定数時間で近似値を計算できる、確率的データ構造の紹介スライドです。

本スライドは、株式会社エフ・コードの社内勉強会(2018/08/30)にて使用されたものです。

Shingo Omura

August 30, 2018
Tweet

More Decks by Shingo Omura

Other Decks in Technology

Transcript

  1. 大村伸吾 おおむら しんご ✘ Software Engineer at Preferred Networks ✘

    Technical Consultant at f-code, ChatWork ✘ twitter/github: everpeace ✘ facebook: shingo.omura 2
  2. 本日の流れ ✘ 確率的データ構造が解決したい課題 ✘ 確率的データ構造を使うとどう嬉しいのか ✘ 今回紹介するデータ構造の紹介 ✘ Bloom Filter

    (集合の所属確認) ✘ Count Min-Sketch (ヒストグラム, 分位数, レンジクエリ) ✘ HyperLogLog (集合異なり数) ✘ 利用可能なライブラリ・ソフトウェア 4
  3. 確率的データ構造が解決したい課題 ✘ 超巨大な集合がメモリに乗り切らない ✗ 例: ドキュメントの集合(単語のmulti set) ✗ メモリに乗らないので処理が遅い ✗

    ストリーム処理でたくさんディスク読んでると 追いつかない ✘ 分析系でUnique Countするだけでもキーの数が多すぎ・・・ ✗ 軸が増えれば増えるほどサイズは掛け算で増えていく ▪ 例: 全ドキュメントの単語の種類 各ユーザのtweet数の時系列データ 6
  4. 確率的データ構造を使うと何が嬉しいのか ✘ 超巨大なサイズの集合を 定数メモリ の領域に保存 ✗ 特定の操作のみしかできない ✗ 多くの処理が定数時間で処理可能 ✗

    近似値のみしか得られない 超巨大な集合 ????? (賢い仕組み) サイズが増えれば 保存領域が増える サイズが増えても 領域が増えない! 近似値 (でもO(1)時間 !) 8
  5. 今回紹介する確率的データ構造 ✘ Bloom Filter ➔ 集合の所属確認 ✘ Count-Min Sketch ➔

    ヒストグラム,レンジクエリ, 分位数 ✘ HyperLogLog ➔ 集合異なり数 ✘ Q-Digest ➔ 分位数 10
  6. Bloom Filter ✘ Burton H. Bloom 氏によって 1970年 に考案 ✘

    任意サイズの集合の所属確認が 定数メモリ, 定数時間 ✘ Cassandra, HBase, Google BigTable等で普通に使われている 定数メモリ で表現された 集合 x x は含まれるか? true false 確率的に嘘を含む 絶対正しい 偽陽性 O(1) 時間 12
  7. え ✘ 一枚の紙(定数サイズ!) に文字に重ね書きしていくイメージ ✗ 実際は文字の影(ハッシュ値!)みたいなものを書きます ✘ 紙の大きさが定数なので追加も所属確認も O(1) 時間!

    Bloom Filterのアイデア ふ え ふ x x は含まれるか? true false • x の形が通ったら true ◦ ただしx以外の複数の形 でたまたま通ったのかも しれない • x の形が通らないなら false ゼッタイ! O(1) 時間 O(1) 時間 13
  8. Bloom Filter ✘ 準備 ✗ m bitの配列 ✗ k 個のランダムなハッシュ関数

    hi : KEY → {1, … m} ✘ 処理 ✗ x の追加 ➔ h1(x), h2(x), … hk(x)の位置のbitを1にする ✗ x の所属確認➔ h1(x), h2(x),...hk(x)のbitを見て1個でも0があればfalse 1 1 1 1 1 1 … 0 1 2 m-1 x h1(x) h2(x) hk(x) 14 y h1(y) h2(y) hk(y)
  9. Bloom Filter の 偽陽性 はどのくらいか? ✘ 偽陽性: メンバーでない要素 x が

    trueになってしまう確率 ✗ Hash関数 = n 個の要素を m個のbucket にランダムに入れる ✗ k = 1 のとき ▪ 入るbucketの値が 1 である 確率 = n 個の要素を追加したときその bitが 1 である確率 = 1 - (n個要素追加されてまだ 0の確率) = 1 - (1 - 1/m)^n ✗ k のとき ▪ n 個追加したときにある bitが 1 である確率 = (1- 1/m)^kn ▪ チェック時にk個のhashで全部 1 だと偽陽 ▪ m, n を固定したときに確率を最小化できる k = m が大きい ➔ 小さくなる, n が大きい ➔ 大きくなる ref: ブルームフィルタ - Wikipedia 15
  10. Bloom Filter の 偽陽性 はどのくらいか? ✘ k が最適だとすると偽陽性は ✘ 2^30個(signed

    int空間の1/2)を偽陽率10%で所属確認するためには1〜2GBくらい 16 横軸: 要素数のlog, 縦軸: filterサイズ[GB], 色: 偽陽確率
  11. Bloom Filterの応用 ✘ 集合演算 (同じhashである前提) ✗ 和集合 ➔ filterのOR でOK

    ✗ 積集合 ➔ filter のANDでOK. (偽陽性が高くなるので注意) ✗ SQLの処理でJOINの前処理とかに便利 ✘ 要素の削除への対応 ➔ Counting Bloom Filter (1998) ✗ 配列をbitじゃなくてカウンタにする(0以上で所属) ✗ 要素を取り除くときはdecrementする ✘ 他にも亜種がいっぱいある ✗ Quotient Filter (2011): Bloom Filterより空間効率良い ✗ Bloomier Filter (2003): keyに紐づく値 (ハッシュテーブル) ✗ Scalable Bloom Filter (2007): サイズを動的に増やせる 17
  12. Count Min Sketch 19 ✘ Graham Cormode and S. Muthu

    Muthukrishnan (2003) ✘ 要素ごとの頻度(ヒストグラム)を定数メモリで保持できる ✗ x は何個あるか? ✘ 少し工夫すると 要素の頻度 だけでなく下記も実現可 ✗ レンジクエリ: a <= x <= b には何個? ✗ パーセンタイル: 90% tileはいくつ?
  13. … … … … c1 c2 c3 c4 Count Min

    Sketch の アルゴリズム ✘ d 個のhash: h1, h2, …, hd: KEY_SPACE => {0, w-1} ✗ 追加 ➔ 各ハッシュ列のハッシュ値indexの値を +1 ✗ xは何個? ➔ テーブルの該当セルの最小値 20 x w d O(1)時間 出力: min{ T[1, h1(x)], …, T[d, hd(x)] } x は何個? x を追加 +1 +1 +1 +1
  14. Count Min Sketch の アルゴリズム ✘ 欲しい誤差上限ε, 誤差逸脱確率δ から w,

    dが計算できる ✘ 1 GBあればungined int全体(10桁)くらいのサイズの集合でも 99% の確率で3桁誤差以内を達成 21 multisetの全要素数
  15. レンジクエリ( l〜r までの頻度の和 )対応版 ✘ アイデア: [1, n] 内の任意のrangeは 高々

    2 log n 個 の dyadic range coverに分割可 ✗ dyadic range = [ g*2^h + 1, (g+1)*2^h ] 22 1 2 3 4 [1,2] [3,4] [1,4] 5 6 7 8 [5,6] [7,8] [5,8] [1,8] N = 3のとき 例: [2, 6] → [2, 2], [3, 4], [5, 6] g=0 g=1 g=2 g=3 h=1
  16. レンジクエリ( l〜r までの頻度の和 )対応版 ✘ 各高さごとにsketchを保持 ✗ 追加 ➔ 各高さで該当dyadic

    rangeの g の値をテーブルに追加 ✗ クエリ ➔ dyadic range coverの各rangeクエリの和をとる ✘ 実行時間は O(log n) (nはキーの最大値 ⬅ 通常定数!) 23 3 4 [3,4] [1,4] 5 6 7 8 [5,6] [7,8] [5,8] 1 2 [1,8] [1,2] g=0 g=0 g=1 g=4 h1(0)... hd(0) h1(0)... hd(0) h1(1)... hd(1) h1(4)... hd(4) 4
  17. 分位数(パーセンタイル) 対応版 ✘ p -パーセンタイルを探したければ, ✗ count( [1, n] )

    = Total で全体を求める ✗ あとは二分探索で count ( [1, r] ) = pT になるように r を見つける 24
  18. HyperLogLog ✘ 集合異なり数: 重複を取り除いた異なる物の数 ✗ 例: ユニークユーザー数 ✗ カーディナリティとも呼ばれる ✘

    near-optimalである(漸近的にはこれ以上改善できないらしい? ) ✘ ハッシュ値ではなく Base 2 Rank というスケッチ値を使う ✗ Base 2 Rank ▪ ハッシュ値の先頭の0の個数: ρ(000101010011) = 3 ✗ 要素を入れるたびにρの最大値を覚えておく ✗ データに含まれる異なり数を2^(ρの最大値)で推定 26
  19. HyperLogLog 先頭の0の数がなぜユニーク数と関係するのか!? ✘ ハッシュ値のビットがランダムだとすると・・・ ➔ 各ビットが 1, 0 になる確率= 1/2

    ➔ 先頭に 0 が p 個並ぶ確率 = 1/ 2^p ➔ pの最大値が更新された ➔ 初めて p 個 0 が並んだ ➔ 確率 1/2^p で出現する数が出た ➔ これまでざっくり言って 2^p 種類が存在したはず!? 27
  20. HyperLogLog のアルゴリズム ✘ k = 2^b のbucketを用意 ✘ Hashの先頭 b

    ビットでbucketに振り分け ✘ Bucketごとに Base 2 Rank の maxを保存 28 Hash値はもちろん先頭bビットを 切り捨てて使う 000 001 010 011 100 101 110 111 b = 3 3 4 1 ➔ 2 1 5 3 4 6 x 01000101..10 h(x) Z = (Σ 1/2^t[i])^-1 Output: α m^2 Z αはhash衝突 分を補う係数
  21. HyperLogLogのメモリ量と性能 ✘ メモリはものすごく少なくていい ✗ 32ビットのハッシュ値の場合 ▪ ρの値は5 bitで保存可 (実際このくらいで十分らしい) ✗

    b = 16 (4 bit)としても たったの 80 bit !!! ✘ 精度 ✗ 相対誤差 = 1.04 √k ✗ 定数確率で1 ±ε近似するために O(ε^(-2) loglogn + logn) 29 名前の由来
  22. HyperLogLog は 巨大な集合でないと誤差大き杉 ✘ 小さい時はかなりデタラメ ✘ Cardinalityが小さい時は Linear Counting(1990) が良いらしい

    ✗ Hash値を適当なbucket数 に mod して分けてカウントする 30 ref: HyperLogLog in Practice: Algorithmic Engineering of a ... - Google AI
  23. HyperLogLog in Practice (Googleによる改良) ✘ LinearCountingとHyperLogLogをしきい値で使い分けて良いとこ取り ✗ 異なり数 15000 くらいまではLinear

    Counting のほうが誤差が少ないのが図から分かる ✘ 実はもっと良い改良版もある ✗ HIP(Historic Inverse Probability) Estimator (2014) ✗ HyperLogLogは最大値を更新したが これはその時に値が更新される 条件付き確率を考えてその逆数を足す ✗ メモリが0.56倍同じ精度! ✗ Cardinalityが小さくてもOK ! 31 ref: HyperLogLog in Practice: Algorithmic Engineering of a ... - Google AI
  24. 確率的データ構造のライブラリ・ソフトウェア ✘ 探すとたーーーっくさんあります(Production Readyかどうか謎なものを含む) ✗ https://www.google.co.jp/search?q=bloom+filter+libraries ✗ https://www.google.co.jp/search?q=count+min+sketch+libraries ✗ https://www.google.co.jp/search?q=hyperloglog+libraries

    ✘ Scalaだと twitter/algebird: Abstract Algebra for Scala ✗ 今日紹介するデータ構造は全部入ってて良いです ✗ akkaでwrapしてakka-streamで使えるようにすると タイムリーで結構喜ばれるかも ✘ 実装は難しくないので勉強がてら作るのも楽しいです ✗ Bloom filterは作ってみたことある: https://github.com/everpeace/bloom-filter ✘ Redis, Spark, Presto とかから使えたりもするので実行時間とか比較してみるのも面白 いかも ✗ PrestoとHyperLogLogで、大量ログからユニークユーザー数を高速に推定する (実践編) 33
  25. hash関数について。実際どのhashがよいか? ✘ 実性能はhashの性能に依存する ✗ 解析ではハッシュ値がrandomだと仮定していたりする ✘ Hash functions: An empirical

    comparison - strchr.com ✗ Hash関数の性能比較をとても幅広くしてくれている (注意: 最終更新が6年前, 初稿は10年前) ✗ 結果: Murmur2, Meiyan, SBox, CRC32 が汎用として良い ▪ 暗号的ハッシュ出ないものもあるので注意! ✗ 個人的にはハッシュテーブルでよく使われているMurmur2, Murmur3で良さそうに思う 34
  26. THANKS! Any questions? You can find me at ✘ twitter/github:

    everpeace ✘ facebook: shingo.omura 35
  27. 付録: 参考文献 ✘ 乱択データ構造の最新事情 -MinHash と HyperLogLog の最近の進歩- ✗ しっかり最新の事情が詳しく紹介されている。おすすめ。

    ✘ PrestoとHyperLogLogで、大量ログからユニークユーザー数を高速に推定する(実践編) ✘ RedisのBitCountとHyperLogLogを使用した超高速Unique User数集計 ✘ An Improved Data Stream Summary: The Count-Min Sketch and its Applications ✗ Count min sketch の 原典 ✘ A Linear-Time Probabilistic Counting Algorithm for Database Applications ✗ Linear Countingの原典 ✘ Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm ✗ HyperLogLog原典 ✘ Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm ✗ HyperLoglogのGoogleの改良 ✘ All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis ✘ Hash functions: An empirical comparison - strchr.com ✘ Algebird & Approximation algorithms by Stephan H on Prezi ✗ Algebirdというtwitterのライブラリと絡めた説明 36
  28. 付録: Bloom Filter の 偽陽性グラフのgnuplot script set palette model XYZ

    functions gray**0.35, gray**0.5, gray**0.8 set pm3d map interpolate 10,10 set xrange [27:35] set yrange [0.5:5] set xlabel "lg n" set ylabel "m [GB]" splot 0.6185**(8*1024*1024*1024*y/2**x) 37
  29. 付録: count min sketchのsketchサイズのグラフのgnuplot スクリプト set pm3d map interpolate 3,

    3 set palette model XYZ functions gray**0.35, gray**0.5, gray**0.8 set title "sketch size [GB]" set xrange [1e-6:1e-1] set logscale x 10 set xtics auto set xlabel "delta" set yrange [1e-9:1e-7] set logscale y 10 set ytics auto set ylabel "epsilon" splot ceil(2.718/(y))*ceil(log(1/(x)))/(1024*1024*1024) 38