19

Doug Cutting の論文を読みました。「合計ランキングのスペース最適化」。

ずいぶん前に書いたものなので、luceneがどんなアルゴリズムを使っているのか気になります(投稿リストのトラバーサルやスコア計算、ランキングに関して)。

特に、そこで説明されている総合ランキング アルゴリズムでは、各クエリ タームの投稿リスト全体をトラバースする必要があるため、「yellow dog」のような非常に一般的なクエリ タームの場合、2 つのタームのいずれかが非常に長い投稿リストを持つ可能性があります。ウェブ検索。それらはすべて、現在の Lucene/Solr で本当にトラバースされていますか? または、採用されているリストを切り捨てるためのヒューリスティックはありますか?

上位k件の結果しか返ってこない場合は、投稿リストを複数のマシンに分散させて、それぞれの上位k件をまとめればいいのは理解できますが、「100件目の結果ページ」を返さなければならない場合は、つまり、結果が 990 から 1000 番目にランク付けされた場合、各パーティションは依然として上位 1000 を見つける必要があるため、パーティショニングはあまり役に立ちません。

全体として、Lucene で使用される内部アルゴリズムに関する最新の詳細なドキュメントはありますか?

4

1 に答える 1

30

そのようなドキュメントは知りませんが、Lucene はオープンソースなので、ソース コードを読むことをお勧めします。特に、現在のトランク バージョンには柔軟なインデックス作成が含まれています。これは、ストレージと投稿リストのトラバーサルが残りのコードから分離されていることを意味し、カスタム コーデックを記述できるようになっています。

デフォルトでは、投稿リストのトラバーサルに関する仮定は正しいです (スコアラーの実装によって異なります) 。 TopDocsCollectorを参照してください)。そのため、990 から 1000 までの結果を返すと、Lucene はサイズ 1000 のヒープをインスタンス化します。また、インデックスをドキュメントごとに分割する場合 (別の方法として用語で分割することもできます)、すべてのシャードが上位 1000 の結果をサーバーに送信する必要があります。結果のマージを担当します (たとえば、N から P>N へのクエリを 0 から P への複数のシャード リクエストに変換するSolr QueryComponentを参照してください)。sreq.params.set(CommonParams.START, "0");）。これが、極端なページングの場合に、Solr がスタンドアロン モードよりも分散モードで遅くなる可能性がある理由です。

Google がどのようにして効率的に結果をスコアリングしているかはわかりませんが、Twitterは検索エンジン Earlybird に関する論文を公開し、投稿リストの効率的な逆時系列順トラバーサルを行うために Lucene にパッチを適用した方法を説明しています。すべての用語の投稿リスト全体をトラバースすることなく、クエリに一致する最新のツイート。

更新: Googler Jeff Deanによるこのプレゼンテーション を見つけました。これは、Google が大規模な情報検索システムをどのように構築したかを説明しています。特に、シャーディング戦略と投稿リストのエンコーディングについて説明しています。

于 2012-04-26T08:34:34.427 に答える