大量データストリームのベストプラクティス

概要: 膨大な量のデータを効率的に分析するために、科学者はまず大量の数字を細分化する必要があります。膨大なデータストリームを処理するためのストリーミングアルゴリズムを段階的に解説します。このアルゴリズムは継続的に改良されており、超大規模データストリームの高性能な分析のための新しいアルゴリズムです。以下はその翻訳です。

[[210234]]

消防ホースから水が顔に当たると、水を量るのは難しいです。ある意味、これはデータ ストリームを分析する際の課題です。データは常に流れてきており、止まることはありません。 Twitter でツイートが次々と流れていくのを見ているときは、一時停止して何がトレンドになっているか確認したほうがよいかもしれません。そうは言っても、これはうまくいかないので、ハッシュタグをリアルタイムで記録する方法を見つける必要があります。

このようなリアルタイム計算を実行するコンピュータ プログラムは、ストリーミング アルゴリズムと呼ばれます。データは大量に継続的に流入するため、ストリーミング アルゴリズムは重要なデータを記録しようとし、残りのデータを戦略的に忘れます。 30 年以上にわたり、コンピューター科学者たちはより優れたストリーミング アルゴリズムの構築に取り組んできました。昨年の秋、研究チームはほぼ完璧なアルゴリズムを開発した。

「私たちはあらゆる基準から見て最高のアルゴリズムである新しいアルゴリズムを開発した」とハーバード大学のコンピューター科学者ジェラニ・ネルソン氏は述べた。ネルソン氏はデンマークのオーフス大学のカスパー・グリーン・ラーセン氏、コペンハーゲン大学のミッケル・ソルプ氏、ノースイースタン大学のフイ・グエン氏とともにこの新しいアルゴリズムを提案した。

[[210235]]
この新しいアルゴリズムは、ハーバード大学の理論計算機科学者ジェラニ・ネルソン氏によって共同開発された。
画像クレジット: Yaphet Teklu

この最先端のストリーミング アルゴリズムは、最も頻繁に表示されるものを伝えるのに十分なデータを記憶することによって機能します。これは、データフロー分析に固有のトレードオフが実際には必要ではないことを示唆しています。それはまた、戦略的忘却の新しい時代への道を示しています。

トレンドを把握する

ストリーミング アルゴリズムは、継続的に更新されるデータベースを監視するあらゆる状況で役立ちます。それは、AT&T のタブ パケットの絶え間ない流れ、あるいは Google による終わりのない検索クエリの流れのせいかもしれません。このような場合、ストリーミング アルゴリズムは、これまでに見たすべてのデータを再確認したり記憶したりすることなく、データに関するリアルタイムの質問に答える方法を提供する上で非常に役立ち、必要でさえあります。

ここに簡単な例を示します。一連の数字があり、これまでに見たすべての数字の合計を知りたいとします。この場合、すべての数字を一つずつ覚えるのではなく、累積合計という 1 つの数字だけを覚えておけばよいことは明らかです。

しかし、データに関して尋ねたい質問が複雑になるにつれて、この課題はより困難になります。合計を計算する代わりに、次の質問に答えたいとします。どの数字が最も頻繁に出現するか? 正しい答えを素早く得るための近道があるかどうかは明らかではありません。

この特定のパズルは、「頻出項目」（またはヘビーヒッター）問題と呼ばれます。このパズルを解く最初のアルゴリズムは、1980 年代初頭にコーネル大学の David Gries 氏とテキサス大学オースティン校の Jayadev Misra 氏によって開発されました。彼らのアルゴリズムは多くの点で効果的ですが、「変更検出」と呼ばれるものを処理することはできません。最も頻繁に検索される用語はわかりますが、どの用語が人気があるかはわかりません。たとえば、Google は「Wikipedia」を人気のある検索語として認識しますが、ハリケーン イルマのような大規模な出来事に関連するトレンド検索は認識しません。

「これはエンコードの問題だ。情報を簡潔な要約としてエンコードし、元の内容を復元できるような方法で情報を抽出しようとするのだ」とウォーリック大学のコンピューター科学者、グラハム・コーモード氏は語った。

その後 30 年間にわたり、カーモード氏と他のコンピューター科学者たちはグリース氏とミスラ氏のアルゴリズムを改良しました。たとえば、新しいアルゴリズムの中には、よく使われる単語を検出できるものもあれば、頻繁に使用される単語をより細かく定義できるものもあります。これらのアルゴリズムにはすべて、精度のために速度を犠牲にしたり、信頼性のためにメモリ消費を犠牲にしたりするなどの欠点があります。

この分野の作業のほとんどはインデックスに依存しています。頻繁に検索される用語を特定しようとしていると想像してください。 1 つの方法としては、英語の各単語に番号を割り当て、その番号を、その単語が検索された回数を記録する 2 番目の番号と組み合わせるというものがあります。おそらく、「aardvark」は単語番号 17 としてインデックス付けされ、データベースでは (17, 9) として表示されます。これは、単語番号 17 が 9 回検索されたことを意味します。このアプローチにより、各単語が検索された回数をいつでも正確に把握できるため、最も頻繁に使用される用語をすぐに把握できるようになります。

それでも、アルゴリズムが英語の何十万もの単語を調べるのに多くの時間がかかるという欠点があります。

しかし、辞書に100語しか載っていない場合はどうなるでしょうか。ネルソン氏は「辞書にあるすべての単語を調べるのにそれほど時間はかかりません」と述べています。

残念ながら、辞書には単語が多すぎます。新しいアルゴリズムの作成者が発見したように、大きな辞書を小さな辞書に分割し、それを再び組み立てる巧妙な方法を見つけない限り、何もできません。

スモールデータ

小さな数字は大きな数字よりも追跡しやすいです。

0 から 50,000,000 までの数字のストリームを監視していると想像してください (IP アドレスでインターネット ユーザーをログに記録するタスクに似ています)。これらの数値を追跡するには 50,000,000 項目のインデックスを使用することもできますが、このような大規模なインデックスを処理するのは困難です。より良いアプローチは、各 8 桁の数字を 4 つの 2 桁の数字が結合したものとして考えることです。

12345678 という数字が表示されているとします。効率的に記憶する方法は、12、34、56、78 という 4 つの 2 桁のブロックに分割することです。次に、各ブロックを、項目の頻度を計算するサブアルゴリズムに送信できます。サブアルゴリズム 1 には 12、サブアルゴリズム 2 には 34、サブアルゴリズム 3 には 56、サブアルゴリズム 4 には 78 が送信されます。

各サブアルゴリズムには、見たものに対する独自のインデックスがありますが、どのバージョンでも 2 桁を超えるインデックスは見られないため、各インデックスは 0 から 99 までになります。

この分割の重要な特徴は、大きな数字 12345678 がデータ ストリーム全体で頻繁に出現する場合、その 2 桁のブロック部分も頻繁に出現することです。各サブアルゴリズムに最も頻繁に表示される数字を識別するように要求すると、サブアルゴリズム 1 は 12 を返し、サブアルゴリズム 2 は 34 を返します。 4 つのはるかに短いリストで頻繁に使用される項目を探すだけで、大きなリストで最も一般的な項目を見つけることができます。

画像クレジット: ルーシー・リーディング・イカンダ/Quanta Magazine

「宇宙全体を横断するのに5000万時間かかる代わりに、たった4つのアルゴリズムで100時間しかかかりませんでした」とニールセン氏は語った。

この分割統治戦略の主な問題は、大きな数字を小さな数字に分割するのは簡単だが、小さな数字を大きな数字に再結合するのは難しいことです。つまり、正しい大きな数字に再結合するための適切な小さな数字を見つけるのが難しいのです。

データ ストリームに、12,345,678 と 12,999,999 のように、同じ桁が複数ある 2 つの数字が定期的に含まれているとします。どちらも12時に始まります。アルゴリズムは、各大きな数値を 4 つの小さな数値に分割し、各小さな数値をサブアルゴリズムに送信します。次に、各サブアルゴリズムに「どの数字を最も頻繁に見るか」を尋ねます。サブアルゴリズム 1 は、「12 という数字をよく見ます」と答えます。この場合、どの 8 桁の数字であるかを識別しようとするアルゴリズムは、これらの 12 が 8 桁の数字の 1 つに属するのか、それともこの場合は 2 つの異なる 8 桁の数字に属するのかを知らないことがよくあります。

「難しいのは、どの2桁のブロックが他のどの2桁のブロックと合うかを判断することです」とネルソン氏は語った。

新しいアルゴリズムの作成者は、各 2 桁のブロックを小さなタグにラップすることでこのジレンマを解決しました。このタグはメモリをあまり消費しませんが、アルゴリズムは 2 桁のブロックを正しい方法で元に戻すことができます。

ラベル付けがどのように機能するかを簡単に確認するには、12,345,678 から始めて、それを 2 桁のチャンクに分割します。しかし今回は、各ブロックをそれぞれのサブアルゴリズムに送信する前に、ブロックは、元に戻すことができる一意の識別番号のペアでラップされます。最初のラベルはブロックの名前として使用され、2 番目のラベルはリングとして使用されます。このようにして、12345678 は次のようになります。

ここで、数字 12 は「0」という名前が付けられ、「1」という数字にリンクされています。数字 34 は「1」という名前で、「2」という数字にリンクされています。

ここで、サブアルゴリズムが最も一般的な 2 桁のブロックを返すと、12 は「1」でマークされた数字を探し、34 につながり、次に 34 は「2」でマークされた数字を探し、56 につながり、56 は「3」でマークされた数字を探し、78 につながります。

このように、2 桁のブロックはチェーン内のリングとして考えることができ、これらの追加のマーカー番号がリングを接続します。

もちろん、多くのチェーンの問題は、チェーンの強度が、最も弱いリンクの強度と同程度しかないことです。そして、それらの鎖はほぼ確実に壊れます。

ビルディングブロック

実行されるたびに完璧に機能するアルゴリズムはありません。最も優れたアルゴリズムであっても、わずかな時間では失敗することがあります。上記の例では、失敗とは、2 番目の 2 桁のブロック 34 に間違ったラベルが割り当てられ、その結果、接続するはずのブロックを検索したときに 56 を見つけるために必要な情報がなかったことを意味する可能性があります。チェーンの 1 つのリンクが壊れると、作業全体が崩壊します。

[[210237]]
コペンハーゲン大学のコンピューター科学者マイケル・トルップ氏は、データを記憶するためのエラー防止方法の開発に貢献した。
画像出典: UNIAVISEN.DK

この問題を回避するために、研究者たちはいわゆる「拡張グラフ」を使用します。拡張されたグラフでは、数字の 2 つのブロックごとに 1 つの点が形成されます。これらのポイントは（上記のラベル付けプロセスに従って）線で接続され、クラスターを形成します。拡張グラフの重要な特徴は、各ポイントを隣接するブロックに接続するだけでなく、各 2 桁のブロックが複数の他のブロックに接続されていることです。 12345678 を例にとると、12 は 34 だけでなく 56 にも接続されているため、12 と 34 の間のリンクが失敗した場合でも、12 と 56 は同じ数字に属していることがわかります。

グラフを拡張した結果は必ずしも完璧ではありません。リンクすべき 2 つのブロックがリンクされなかったり、リンクすべきでない 2 つのブロックがリンクされたりすることがあります。この欠点を克服するために、研究者らはアルゴリズムの中核部分を開発した。それは、拡張されたグラフを調査し、いくつかの線が失われ、誤った線が追加されても、どの点が一緒にクラスター化される予定であり、どの点がそうではないかを正確に判断する「クラスター保存」サブアルゴリズムである。

「これにより、元のクラスタリングとまったく同じものを復元できるようになります」とトルップ氏は語った。

Twitter 社は明日この拡張グラフを使用する予定はないが、その基礎となる技術はツイートのカウントだけにとどまらず、非常に幅広いコンピューター サイエンスの問題に適用できる。このアルゴリズムは、頻繁に出題される項目の質問に答える際にこれまで必要だと思われていた特定の犠牲が不要であることも実証しています。以前のアルゴリズムでは、常に何かを犠牲にしていました。非常に正確でしたが、メモリを大量に消費しました。また、非常に高速でしたが、頻繁に使用されるアイテムのうちどれが人気があるかを判断できませんでした。この新しいアルゴリズムは、大量の情報を適切にエンコードする方法があれば、頻繁に使用する項目を保存できるだけでなく、それらを取得することもできるという、両方の長所を活かせることを示しています。