ガジェット通信 GetNews

見たことのないものを見に行こう

体験を伝える―『ガジェット通信』の考え方

面白いものを探しにいこう 本物を体験し体感しよう 会いたい人に会いに行こう 見たことのないものを見に行こう そしてそれをやわらかくみんなに伝えよう [→ガジェ通についてもっと詳しく] [→ガジェット通信フロアについて]

リクルート全社基盤アーキテクチャ、最適検索スコア導出、Ansible vs Chef-Solo、Node.js Stream─リクルートテクノロジーズ社内勉強会

偽陽性判定のアルゴリズム「Bloom Filter」を検索基盤に活用

最初に登壇したのは、守谷純之介さん。リクルート全社検索基盤の開発に携わっており、「検索、検索、検索」の日々を送っている。

▲株式会社リクルートテクノロジーズ アプリケーション・ソリューショングループ 守谷純之介さん

全社基盤アーキテクチャに採用されている技術については、『リクルート 全社検索基盤アーキテクチャ』で検索してみてほしい。

今回の発表テーマは「Bloom Filter」。Bloom Filterとは要素が集合に含まれるか否かを判定するためのデータ構造であり、偽陽性(False Positive)のアルゴリズムである。

偽陽性とは図を見ればわかるとおり、「『H9K4H9』はある?」という問い合わせに、「あります」という回答の場合はあやしいという判断となり、「ないです」という回答だと本当にないので、正しいという判定になる。

Bloom Filterは、Akamai、Google BigTable、Google Chrome、Apache Lucene、Apache Hadoop、Oracleなどいろいろなところで使われている。

原理は次の通りだ。Bloom Filterはm個のビットからなるビット配列で、初期状態では全て0となっている。次にk個のハッシュ関数を定義する(k個のハッシュ関数を準備する必要はなく、異なるk個の初期値でもよい)。

1つの要素を追加するとk個の1が登録される。そして要素が含まれているかどうかは、k個のビットが1であるかどうかを検索することで判定する。

例えば、図のように「ア」と「イ」を登録する。

この状態で「ウ」はあるかというと、図を見ればわかるとおり、「ない」という判定が返される(正しい)。

一方、「T」はあるかと問い合わせると、「ある」と判定され、正しくないという結果になるというわけだ。

ハッシュ関数としてはMurmurやFVN、Jenkins Hash、MD5などがあるが、これらの初期値をk個準備して、値をmで割ればよい。

また実際にどのようなフローになるかについては、2つのパラメータを用意するだけで簡単に実装できる。

実際の誤り確率については、次の式で表されるため、登録する件数が増えれば増えるほど、誤りは大きくなるが、ビット配列長が1MByteでハッシュ関数が8個、要素数が100万個の場合、誤り確率は1.7%となる。ないときはないと正しく言ってくれる。実装工数もかからないので、使える技術だ。

ユーザーに最適な検索スコアを返す仕組みはどうつくる?

続いて登壇したのは、リクルートテクノロジーズで検索改善を担当する大杉直也さん。テーマは「最適な検索スコア導出のためのアイデアとその実装」。

▲株式会社リクルートテクノロジーズ アプリケーション・ソリューショングループ 大杉直也さん

1 2 3次のページ
CodeIQ MAGAZINEの記事一覧をみる
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。