検索エンジンはいかにして動くのか?

第10回 動的な索引構築

この記事を読むのに必要な時間:およそ 3 分

Remerge(Immediate Merge)戦略

Remerge戦略は,ディスク上の索引を常に1つに保つようにマージしていく方法となります。よって,メモリ上の索引のサイズがある閾値に達した場合,メモリ上のポスティングは既存のディスク上の索引とマージされ,新しい索引を作成します。その後,マージ元のディスク上の索引とメモリ上の索引は削除されます。

この戦略では,転置リストの取得に必要なディスクシークの数を最小化していますが,マージの度にディスク上の索引を全スキャンする必要あるという欠点があります。nを構築する総ポスティング数,bをバッファで保持できるポスティング数とすると,n/bは構築完了までのディスクへの書き出し回数を表し,n個のポスティングはn/b回のマージを行うため,構築におけるディスク操作の漸近的時間計算量は,O(n2/b) となります。

No Merge戦略

No Merge戦略は,その名のごとくマージ操作を全く行いません※3⁠。Remerge戦略と同様に,メモリ上の索引のサイズがある閾値に達した場合,その索引はディスク上に書き出されます。

この戦略では,高いインデックス構築速度を達成しますが,ディスク上の索引が複数の索引に分割されているため,転置リストの取得に部分索引の数のディスクシークが発生してしまう欠点があります。n個のポスティングはそれぞれ1回のフラッシュを行うため,構築におけるディスク操作の漸近的時間計算量はO(n)となります。

※3)
マージを行わないので,マージによる統合方法の1つとして挙げるのには違和感がありますが,Remerge戦略との比較として紹介される場合が多いので,本連載でも同様にマージによる統合方法の1戦略として紹介します。

Geometric Partitioning戦略

上記に紹介した2つのマージ戦略の中間的な方法が,Geometric Partitioning戦略となります。メモリ上に構築された索引は,毎回ではなく定期的にディスク上の索引とマージされます。Geometric Partitioning戦略では,索引を制限された数のパーティションに分割します。

この戦略では,キーとなるパラメータrを導入し(通常はr=2 or r=3)し,rによりマージのタイミングを調整します。各レベルk(k=1,2,3 ...)のパーティションは,空またはr(k-1)b個以上(r-1)r(k-1)b個以下のポスティングを保持します(kが大きいレベルになるにつれて,索引が大きくなります⁠⁠。

メモリ上に構築された索引は常にレベル1の索引とマージされ(レベル1に索引が無い場合は書き出されるだけ⁠⁠,ポスティング数がレベルの上限を越えた場合は,さらに1つ上のレベルの索引とのマージ処理が行われます(各レベルの上限に収まるまで繰り返しマージされます。※4⁠。

少し動作が複雑なので,具体的にr=2の場合を考えてみましょう。r=2の場合には,2進数に1を加算していくのと同じ過程でマージ処理が行われます。各桁がレベルに相当し,上のレベルの索引とのマージ処理は繰り上げに相当します。

たとえば,レベル3に索引がある場合は,00000100という2進数で表現できます。この状態に新たにメモリ上の索引をマージしていきましょう。->をマージ処理とすると,Geometric Partitioning (r=2) では以下のように索引が構築されます。

  • 00000100 -> 00000101 -> 00000111 -> 00001000 -> …

r=2の場合,n個のポスティングはlog2(n/b)回のマージを行うため,構築におけるディスク操作の漸近的時間計算量は,O(n log(n/b))となります。そして, 各状態でのディスク上の索引数は1の数を数えれば求まります。また, Geometric Partitioning(r=2)はLogarithmic Mergeとも呼ばれます。r=3の場合も,パラメータが異なるだけで,同様の構築過程となります。

※4)
複数のレベルにおいてマージが起きる場合は,2つの索引のマージを繰り返すのではなく,通常はマルチウェイでマージを行います。

各戦略のまとめ

3つのマージ戦略を紹介しました。

各マージ戦略には一長一短ですが,現在は構築速度と検索速度のバランスからGeometric Partitioning戦略が有効であると考えられています。

以下に各マージ戦略の特徴を表にまとめます。

 RemergeNo MergeGeometric Partitioning(r=2)
構築におけるディスク操作O(n2/b)O(n)O(n log(n/b))
ディスク上の索引数※51n/blog2(n/b)
※5)
マージ処理の回数はn/bを切り上げた整数となります。Geometric Partitioning(r=2)では,厳密には,2i-1 < n/b ≤ 2i(i=1,2,3 …)における索引数の上限がlog2 2i 個となります。

まとめ

動的な索引構築方法について説明しました。

基本としては,メモリ上の索引とディスク上の索引を分けて管理し,直近の文書の追加による索引の更新はメモリ上に索引に対して行うことで,ディスクにおけるランダムアクセスの数を減らすことにより実現します。

メモリ上の索引は定期的にディスク上の索引と統合され,近年はディスク上の索引を直接更新しないマージによる統合が主流となっています。また,マージによる統合における幾つかのマージ戦略も紹介しました。これらの戦略は毎年のように改良案が出されるなど,研究分野としても注目されています。

参考文献
  • [1]Efficient online index construction for text databases, Nicholas Lester, Alistair Moffat, Justin Zobel, ACM Transactions on Database Systems (TODS), 2008
  • [2]Inverted files for text search engines, Justin Zobel, Alistair Moffat, ACM Computing Surveys (CSUR), 2006
  • [3]Introduction to Information Retrieval, C. D. Manning, P. Raghavan, H. Schutze, Cambridge University Press, 2008

著者プロフィール

山田浩之(やまだひろゆき)

日本IBM株式会社を経て,ヤフー株式会社等で検索エンジンの開発に従事。現在は大学院でデータベース・情報検索の研究を行う。また,オープンソースで全文検索エンジンLuxやデータベースマネージャLux IOの開発を行っている。