Twitterなどでささやかれる自社の製品の評判や、競合他社の製品の評判はマーケティング上重要な情報である。また、いろいろなニーズのささやきは新製品開発の重要なインプットとなる。Salesforce.comのMarketing Cloudは、Twitterなどのソーシャルサイトに投稿される文書などの中からキーワードがマッチしたものを見つけ出すSocial Listeningサービスを提供しており、この技術について、3月に開催されたGTC 2013で発表が行われた。

このツイートなどのサーチは、複数のキーワードの一致をAND、OR、NOTなどで結合した論理式、例えば"mango" AND ("horrible" OR "delicious")のような形でサーチすることができ、キーワード数の多い論理式を用いる方が、一般的には、より絞り込んだサーチが行える。このようなキーワードサーチを行うツールとしてTwitter workersがあるが、スピードが遅いという問題がある。 Twitterのツイートは現在1日約5億件で、さらに増加傾向にある。全ツイートをほぼリアルタイムで取りこぼしなく処理するには80台のサーバが必要になるという。また、ピーク時にはツイート数が数倍に跳ね上がり、より多くのサーバが必要になる。

このため、Saleforce.comはZappと呼ぶGPUを使うキーワード一致サーチシステムを開発したという。Zappでは、GPUによる並列処理とキーワードサーチや論理式評価のアルゴリズムの改良による高速化が行われている。

Zappでは、次の図のような状態遷移図を用いてキーワードを見つける。この例はhe、she、his、hersの4つのキーワードを見つけるもので、hとs以外の文字の場合は状態0に留まり、hが出てくると状態1に移り、次にeが出てくると状態2、iが出てくると状態6に移るというように動き、最終状態をみれば、どのキーワードが出てきたかが分かる。

右上のような状態遷移図を使うと、最終状態をみれば、どのキーワードが出てきたかが分かる。この例ではhe、she、his、hersだけしか見つけられないが、サーチするキーワードすべてに対応する状態遷移図を作る

そして、連続したツイートのテキストを一定の長さに切り、それぞれをCUDAのスレッドに割り当てて、キーワードが出てきたかどうかをチェックする。そして、ツイートごとに出現したキーワードをビットマップ形式で出力する。

次に、各ツイートのキーワードマッチが論理式を満足するかどうかを調べるのであるが、Marketing Cloudでは、全顧客からの論理式を合わせるとすでに160万個の論理式があり、これらの論理式と5億件/日のツイートを総当たりで調べるのは膨大な処理になる。現在、これらの論理式は平均12のキーワードを含んでいるが、キーワード数、論理式の個数ともに増加傾向にあるので、より多くのサーバが必要になって来るという問題がある。

Zappでは、この部分を個々のツイートに含まれるキーワードが論理式を満足するかを調べるのではなく、複数のツイートを含む長いブロック(バッチと呼ぶ)に対して、論理式を満足するかどうかを調べる。この時、"mango" AND ("horrible" OR "delicious")の"mango"と("horrible" OR "delicious")は実は別のツイートに入っているという場合でも論理式を満足してテストをパスしてしまうが、論理式を満足するツイートが除外されてしまうことはない。

第1段階では、大きなバッチで論理式を満足するかどうかを評価し、このテストを通過したバッチに対してツイートごとに論理式を満足するかを評価するという2段階の一致検出を行う方が、次の図に示すように圧倒的に高速に処理できるという。

2段階処理の場合の一致評価回数のグラフ。横軸はツイートをまとめるバッチサイズで、バッチサイズ=816にすると、バッチサイズ1の場合の1/501に計算量が減少する

そして、このバッチ(第2段階ではツイート)と1つの論理式のペアを1つのスレッドとしてGPUで並列に実行させる。

なお、3段階にすれば更に一致評価回数を減らすことができるが、手間の割に性能向上は小さいので、2段階の一致評価を用いているという。

このようなGPUによる並列処理の適用とアルゴリズムの改善で大幅な高速化を実現した結果、たった2台のGTX 580 GPUでピーク時にも対応できる処理能力が実現できたという。

日本の警察がMarketing Cloudを使っているのかどうかは知らないが、このようなテクノロジを使えば、殺人予告のツイートをピックアップするのは容易であると思わる。