HyperLoglogでcount distinctを速くする


こんにちは。俺やで。

HyperLoglogについて書きます。おもしろいです。名前が。

■1. HyperLoglogとは?

count distinctを速くするアルゴリズム

以前、Minhashについて書きました。
(Treasure Dataさんのブログにも載せていただきました。ありがとうございます。)

HivemallでMinhash!〜似てる記事を探し出そう。〜
Build a Simple Recommendation Engine with Hivemall and Minhash

HyperLoglogもMinhash同様乱択アルゴリズムを応用したものです!

ビッグデータのエンジニアとかデータアナリストであれば、count distinctする機会はめちゃめちゃあると思うのですが、「おせーよ。早く結果返せよ」と思うこともめちゃめちゃあるのでは。
なぜ遅いかと言うと正直にすべてのデータを見てるからです。当たり前ですが。

しかし、データがビッグになればなるほど、“正直に”データを見なくても問題ないケースが増えてきます。

例えば1億レコードのWebサイトのログがあったとします。

このレコードの中にどれだけユニークユーザー(UU)がいるのか知りたいと思ったときにcount distinctで返ってきた値が10,000だろうが10,001だろうが9,999だろうが、「だいたい10,000UUであること」がわかれば問題ないケースって多いと思います。
“正直にデータ見なくてもいい”とはそういうことです。

データを正直に見ない代わりにcount distinctの結果を速く返してくれるのがHyperLoglogです!

どのぐらい速くなるのか

HyperLoglogを使ったdistinct countがAWSのRedshiftに搭載されているので、これを使って検証してみましょう!

使うテーブルの情報(メタデータ?)は次の通りです。

  • レコード数:2,979,567,452
  • UU数:309,157,705

ビッグですね。

このレコードからUU数をditinct countで処理すると28秒かかりました。

ではHyperLoglogで処理してみましょう。
こんなクエリで簡単にHyperLoglogを試せます。

select apploximate count(distinct user_id) from hoge;

count distinctの前にapploximateをつけるだけです。
返ってきた値は309,983,724でした。
正確な値より826,019大きくなってますが、0.26%の誤差で済んでます。
そして処理の速さですが、なんと10秒で終わりました!
“正直な”クエリより半分以上短い処理時間です!

HyperLoglogすごい!

※注意(言い訳)※
HyperLoglogはランダム性を伴うので1000回処理したら1回ぐらいとんでもない外れ値を返してくる可能性もないとは言えません。
ですから上のAWSでの検証も本当は1000回ぐらい処理してその平均を評価するべきです。
が、AWSは常にseedが固定されているのか常に同じ結果を返してくるため、この評価ができず。
悪しからず。

■2. HyperLoglogの中身の話

ここからはアルゴリズムの中身の話に移ります。
1から10まで説明するつもりはありませんし、僕も10まではわかりません。
数学とかよくわからなくても「おもしろい」と思えるところまでの解説にします!

「8人」の数え方

目の前に8人います。この8人が「8人」であることを確認してみましょう。

ふつうは「いち」「に」「さん」「よん」・・・と数えるでしょう。

でも「8人であること」を確認するだけならいろんな(まわりくどい)方法があります。

例えば。

1.本を8冊用意する
2.一人1冊ずつ渡す
3.本が余らない
4.ということは、人数も「8」だ!

数学の集合論という分野ではこんな数え方をします。

めちゃめちゃ話が逸れますが、もし数字が「3」までしかない世界なら「8」という数字が存在しないので、「2の3乗」とか「2+2+2+2」で表すしかありません。
でもこれも立派な「8」の数え方です。

本題。
HyperLoglogではこんな数え方をします。

hyperloglog

はい!こんな数え方もできますよね。

速さの秘訣

この数え方は、対象が2のN乗じゃないと”正確には”数えられません。
でも”だいたいの数字”はわかります。

“正直な”disitnct countが遅いのは、
すべてのデータ(文字列)を保持しないと集計できないからです。

しかしHyperLoglogの数え方では、保持すべきデータは「b」だけ。
「b」だけもっておけばだいたいの母数がわかります。

これがHyperLoglogの速さの秘訣です。

推定の秘密

ビッグなデータに話を戻しましょう。
例えば1億UUいるとしましょうか。
これを適当に10グループにわけると1グループあたり平均1,000万UUです。
この10グループそれぞれに対して、さきほどの数え方をしてみます。
そうすると10個の「b」が算出されますよね。
「b」の平均をmean(b)とします。

すると。
全体の母数は、
2のmean(b)乗になりそうじゃないですか。

これがHyperLoglogです!
すごい!

ここまでを説明できれば僕は満足なのでこれ以上の説明はしませんが、
納得できない方は是非是非論文を読んでみてください。
HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm

■3.追記

ビッグデータじゃないとダメです。

ある程度大きいデータじゃないとHyperLoglogはワークしません。
小さいデータならすぐ処理も終わりますし、そもそもHyperLoglogを使う必要はありませんが。

平均にもいろんな平均があります。

Hyperloglogではmean(b)を計算してますが、ここで言う平均はいろんな普通の平均ではありません。
調和平均です!
調和平均 – Wikipedia
いろんな平均があって楽しいです。

そして、申し遅れました。私ビッグデータ解析部吉村と申します。

またの機会に!


DACエンジニア採用情報

  関連記事

PPG_anteli-kunatokei_TP_V
Treasure Dataで大規模なマスタデータを扱う際にはtimeカラムインデックスを活用しよう

DACではTreasure Dataを利用して各種データの蓄積や集計を行っています。Treasure Dataは時系列のデータを扱うのに特にすぐれたアーキテクチャなのですが、セグメントIDとユーザーIDの組み合わせといった大量のマスタデータを利用した計算にも利用することもできます。そのような場合にt …

6914441342_605f947885
Treasure Dataの新機能(Data Tank)をAudienceOneのレポート機能で利用した話

Data Tankとは? Treasure Dataの新機能でTreasure Dataのプラットフォーム上に構築されたデータマートです。 Tableau等のBIツールとの接続を想定されており、AWSでいうところのRedshift的なものだと考えるとわかりやすいかと。 Data TankはPostg …

chain
PyStanによるはじめてのマルコフ連鎖モンテカルロ法

はじめに こんにちは。システム開発部の中村です。 社内で行っている『データ解析のための統計モデリング入門』(所謂緑本)の輪読会に参加した所、 大変わかりやすい本だったものの、Macユーザには悲しい事に実装サンプルがWinBUGSだったため、 9章の一般化線形モデルのベイズ推定によるアプローチをPyt …

tf
ディープラーニングで「顔が似ているAKB48のメンバーを教えてくれるbot」を構築

概要 こんにちは、システム開発部の中村です。 今回は、Facebook Messenger APIを利用して、 画像をアップロードすると、似ているAKB48のメンバーを教えてくれるbotを実装しました。 尚、ディープラーニングやTensorFlowそのものの解説というより、 「エンジンとしてディープ …

logomono-tableau-software-mono
Tableau 9.2で郵便番号の特性を地図で可視化してみる

Tableau 9.2から郵便番号地図が表示可能に 弊社ではデータ分析ツールのTableauを利用しています。オーディエンスデータの重複を分析したり、デモグラフィック属性を表示したりするなどデータの可視化に役立ちますTableauでは9.2から日本の郵便番号を用いて地図を可視化できるようになりました …

gasserverless
GoogleAppsScriptとTreasureData REST APIを使ってサーバレスにTwitterのデータを取得

またまたTreasureDataネタです。 ただ、今回はクエリ系のネタではなく、GoogleAppsScriptとTreasureDataのREST APIを使ってTwitterのデータをTreasureDataに入れてみたので、その方法を紹介したいと思います。 はじめに ログデータだけではなく、公 …

【超入門】Hivemallで機械学習_サムネイル
【超入門】Hivemallで機械学習 〜Treasure Dataでロジスティック回帰編〜

こんにちは。俺やで。 ビッグデータとかデータサイエンティストとかいう言葉が未だブームですね。 (「データサイエンティスト」は下火か。) ビッグデータ扱えるエンジニアも、 統計解析ができるアナリストも、 どっちもできるスーパーマンも世の中にはたくさんいますが、 ビッグデータも統計解析も扱えるインフラは …

no image
Treasure Dataで長期間の集計

プラットフォーム・ワン T氏です。プラットフォーム・ワンでは、DSPのMarketOneとSSPのYIELD ONE提供しています。 MarketOneやYIELD ONEのログを調査する場合にTreasure Dataを使うことがあります。Treasure Dataでは大量のデータに対してHive …

sqlカクテル
【入門編】TreasureDataでサイトのアクセス解析をしてみた~第2弾!~

今回もやります、集計クエリ解説シリーズ第2弾!! 前回は、Webログからセッション単位のデータを作成するだけでした。 第2弾では作成したテーブルを元に、より実践的なアクセス解析、サイト分析で使えるHiveQLについて、実際に使用したクエリとともに解説していきたいと思います。 今回やったこと 利用した …

no image
いま必要なのは「アナリティクスアプローチ」

こんにちは。 ビッグデータ解析部のakiです。 解析部で、Markezineでの連載をはじめましたのでご紹介です。 いま必要なのは「アナリティクスアプローチ」、ビッグデータ活用の課題とこれから (http://markezine.jp/article/detail/21293) マーケターのかた向け …