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を試せます。
[sql]
select apploximate count(distinct user_id) from hoge;
[/sql]
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ではこんな数え方をします。
はい!こんな数え方もできますよね。
速さの秘訣
この数え方は、対象が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
いろんな平均があって楽しいです。
そして、申し遅れました。私ビッグデータ解析部吉村と申します。
またの機会に!

関連記事
-
-
GoogleスプレッドシートからTreasureDataへデータを取り込む
AudienceOneの開発を担当しています。skryoです。 またまたTreasureDataネタですが、今回はGoogleスプレッドシートからGoogleAppsScriptを使ってTreasureDataへデータを取り込む手順を紹介したいと思います。 なぜ? Googleスプレッドシート上でマ …
-
-
【超入門】Hivemallで機械学習 〜Treasure Dataでロジスティック回帰編〜
こんにちは。俺やで。 ビッグデータとかデータサイエンティストとかいう言葉が未だブームですね。 (「データサイエンティスト」は下火か。) ビッグデータ扱えるエンジニアも、 統計解析ができるアナリストも、 どっちもできるスーパーマンも世の中にはたくさんいますが、 ビッグデータも統計解析も扱えるインフラは …
-
-
Tableauを利用してMySQLとRedshiftのクロスDBジョインを実現する
はじめに RedshiftやTreasureDataなどのデータマート用のDBにはID単位の解析結果が格納され、ローカルのMySQLにはIDに紐づいた名称マスタが管理されている構成の場合、データマートのクロス集計結果に対してIDに紐づいた名称を付与したいことがあります。 データマート用に用意したDB …
-
-
Amazon ElastiCache/Redisのパフォーマンス確認
はじめに こんにちは、AudienceOne開発部です。AudienceOne開発部ではいわゆるビッグデータと呼ばれる大量のデータをアドホックあるいは定常的に日々ETLだの集合演算だのをする一方で、様々な大規模データ処理ソリューションを継続的に検証しております。 本記事は、その中でもユーザが保持して …
-
-
Treasure Dataで長期間の集計
プラットフォーム・ワン T氏です。プラットフォーム・ワンでは、DSPのMarketOneとSSPのYIELD ONE提供しています。 MarketOneやYIELD ONEのログを調査する場合にTreasure Dataを使うことがあります。Treasure Dataでは大量のデータに対してHive …
-
-
トレジャーデータの新機能「Data Connector」でクライアントレスなビッグデータ連携を実現する
トレジャーデータは、スキーマレスな大量のデータ(ビッグデータ)をパブリッククラウド上に保管して集計や抽出をするためのサービスなのですが、他システムからの連携データをトレジャーデータのテーブルに格納するまでが一苦労でした。 他システムとの外部連携を行う場合、一般的にローカルサーバー内のストレージを外部 …
-
-
D3.jsとその活用事例について
D3.jsとは? D3とは「Data Driven Document」の略で、データに基づいてドキュメントを操作するための JavaScript ライブラリです。 ご存知の方も多いと思いますが、ちょっとだけD3.jsの基本的な使い方、そして弊社プラットフォームでの利用についてご紹介したいと思います。 …
-
-
fastavroとjqでAVRO形式のファイルからデータを取得しよう
AVRO形式のファイルを取り扱いたい AVROとはApacheプロジェクトのひとつとして開発されているデータ交換形式です。 コンパクトなバイナリで高速なシリアライズ・デシリアライズが行えるため、サーバーログなどに利用されています。 弊社内での一部システムのログデータにも利用されているのですが、専用の …
-
-
GoogleAppsScriptとTreasureData REST APIを使ってサーバレスにTwitterのデータを取得
またまたTreasureDataネタです。 ただ、今回はクエリ系のネタではなく、GoogleAppsScriptとTreasureDataのREST APIを使ってTwitterのデータをTreasureDataに入れてみたので、その方法を紹介したいと思います。 はじめに ログデータだけではなく、公 …
-
-
HivemallでMinhash!〜似てる記事を探し出そう。〜
こんにちは。俺やで。 前回の投稿に続き(間が空きましたが)、 ビッグデータに対応したHiveで使える機械学習ライブラリ、 「Hivemall」の使い方、第2弾となります。 今回はMinhashという手法について書きたいと思います。 ※前回 【超入門】Hivemallで機械学習 〜Treasure D …