「Elasticsearch での類似文書検索と More Like This Query API 詳解」というタイトルで発表しました
Elasticsearch 勉強会 in 大阪・京都で発表しました。
最近、興味をもって調べていた More Like This Query API について、改めてソースコードリーディングしながら整理した内容になっています。
- Elasticsearch 勉強会 in 大阪(7/13 Yahoo! JAPAN 大阪)
- Elasticsearch 勉強会 in 京都(7/14 はてな京都オフィス)
- 大阪と京都でElasticsearch勉強会を開催しました。 ( @johtani さんのブログ)
この発表で使ったスライドを Speaker Deck にアップしました。大阪と京都で同内容の発表でしたが、スライドの体裁をよくして見やすくした、京都での発表スライドをアップしています。
Elasticsearch での類似文書検索と More Like This Query API 詳解 // Speaker Deck
関西では初の開催ということで、何を発表するか、かなり悩みました。
先月の Hatena Engineer Seminar #5 では、どちらかというと事例についての発表だったので、もうちょっと汎用的に使える知識を、とはいえ、入門的な話は johtani さんがしてくださるので、より発展的な内容を、ということで類似文書検索に着地しました。
ただ、両日ともに全文検索より Kibana 等の分析系のほうに興味がある方が多かったようで、参加者の興味を外していた感が否めませんでしたが。。(あとで Twitter を見返してみると、何人かの方には刺さっていたようでした)
類似文書検索とそのアプリケーションについて
類似文書検索は、 Web 検索のみならず、社内文書の検索や、特許検索など、多くの検索アプリケーションで有用な技術です。
ブログの関連エントリー機能などでも使われている技術だと思いますが、類似文書を関連エントリーとしてよいかどうかは、一考の余地があります。要するに、文章が似ているからといって、そのエントリーがブログの読者にとって有益かどうかはまた別問題、ということです。
これについては、 id:skozawa さんが以前に発表した以下のスライドが参考になるかと思います(はてなブックマークの関連エントリー機能で、実際に Elasticsearch を使って実現されている技術について解説されています)。
優先度つきキューによる Top-K retrieval
スライドの中で、優先度つきキュー (PriorityQueue) を使ってスコア上位 K 個の語(ターム)を求めるアルゴリズムが出てきました。発表では時間がなくて話せなかったので、ここで補足しておきます。
Top-K を求めるアルゴリズムは、全文検索エンジンにとって最もコアであり、性能が求められる部分です。なぜなら、全文検索というのは、「与えられたクエリでの文書のスコアを計算し、スコア上位 K 件の文書を返す」という処理に他ならないからです。Lucene レベルでも、でかい転置インデックスから文書の Top-K を計算しており、そこにサイズ制限のある優先度つきキューが使われています。優先度つきキューを使用する際には、スコアを優先度とみなし、優先度の高い文書(= スコアの高い文書)を取り出します。
Elasticsearch の More Like This Query API でも、膨大な数の語(ターム)の Top-K を計算するために、このアルゴリズムが使われています(こちらは文書ではなく、各タームのスコアを計算してスコア上位のタームを求めていることに注意)。
優先度つきキューは、(プリミティブな)配列を使って実装できるため、定数オーダーの操作も高速ですが、これを使って Top-K を求めると、普通にソートするのと比べると、計算量のオーダーも下がるため、ソート対象が大きい場合には劇的な効果があります。
バイナリヒープを用いた制限のある優先度つきキューの実装
優先度付きキュー (Priority Queue) はヒープ 、とくにバイナリヒープで実装されることが多いようです。ここで、ヒープとしては Min-Heap (最小値をもつ要素が先頭になるヒープ)を使うところがポイントです。
サイズ制限のある優先度付きキューの実装は、普通に Max-Heap を使って実装すると、
- delete-min: ヒープから優先度の低いノードを削除 (O(N))
- insert: ノードを追加 (O(1))
ですが、 Min-Heap を使うと、
- extract-min: ヒープから優先度の低いノードを削除 (O(log N))
- insert: ノードを追加 (O(1))
となります。もう少し補足します。
ルートノードは優先度が最も低いことが保証されているため、これは削除してよいということになります。上述の通り、先頭の要素の削除は O(log N) で可能です。単純に Max-Heap を使って、先頭以外の要素の削除をした場合には O(N) ですから、相当に高速化できました。
最後に、サイズが k の配列を用意し、そこにバイナリヒープから順番に取り出した要素を、逆順に詰めていきます。詰め終わった配列を見ると、 Top-k の要素がソートされた状態で得られることになります。
(なお、ここでの優先度つきキューは、最初に要素の追加をすべて済ませ、最後にまとめて優先度の高い要素を取り出す、というタイプのものです。ジョブキューのような、追加の途中で削除があるような用途には使えません)
バイナリヒープを配列で実装する方法については、以下の PDF が参考になります。
Lucene での優先度つきキューの実装については、以下のソースを参照してください。
- org.apache.lucene.util.PriorityQueue ( https://github.com/apache/lucene-solr/blob/trunk/lucene/core/src/java/org/apache/lucene/util/PriorityQueue.java )
あとがき
大阪では、ヤフー大阪支社の方々にお世話になりました。勉強会のあとの懇親会も楽しかったです。ありがとうございました。
また、両日ともに elastic 社の方々には大変お世話になりました。また、 Elasticsearch: The Definitive Guide を献本いただいたり、 elastic ロゴ入りのビーチボールや sugru などの elastic な販促グッズもいただきました。
京都での開催については、発表者全員のスライドが揃いましたら、開催報告エントリーを上げようと思います。