転置インデックス

転置インデックスは、コレクション内の各用語を、それを含む文書のポスティングリストにマッピングすることで、検索システムがすべての文書をスキャンすることなく、一致する文書を見つけられるようにする。

Definition

転置インデックスとは、インデックス化された用語の辞書から構成されるデータ構造であり、各用語は、その用語を含む文書を列挙するポスティングリストを指し示し、多くの場合、頻度と用語の位置が注釈付けされている。これにより、ポスティングリストの交差またはマージによって検索を実行できる。

Scope

このトピックでは、転置インデックスの構造と構築について扱う。具体的には、用語辞書、文書識別子、用語頻度、位置を記録するポスティングリスト、およびブロックソートベースのインデックス作成やシングルパスインメモリインデックス作成を含む、大規模なコレクションに対するインデックスを構築および更新するアルゴリズムについて述べる。フレーズクエリのための位置情報とインデックス保守のエンジニアリングについても触れるが、圧縮とクエリ評価戦略については関連トピックに譲る。

Core questions

• 辞書エントリとそのポスティングリストには何が含まれるか？
• フレーズクエリと近接クエリをサポートするために、位置はどのように保存されるか？
• コレクションがメモリに収まらないほど大きい場合、転置インデックスはどのように構築されるか？
• 文書が追加、変更、または削除された場合、インデックスはどのように更新されるか？
• ポスティングリストは、結合クエリの効率的な交差をどのようにサポートするか？

Key concepts

• 用語辞書
• ポスティングリスト
• 文書識別子
• 位置インデックス
• 用語頻度ストレージ
• ブロックソートベースのインデックス作成 (BSBI)
• シングルパスインメモリインデックス作成 (SPIMI)
• インデックスのマージと更新

Key theories

辞書とポスティングの編成

コンパクトな用語辞書と可変長のポスティングリストを分離することで、システムは用語を迅速に検索し、関連する文書のみをストリーミングできるようになる。これは、すべての転置インデックス検索の構造的基盤である。

スケーラブルなインデックス構築

ブロックソートベースのインデックス作成やシングルパスインメモリインデックス作成のようなディスクベースの手法は、部分インデックスを蓄積およびマージすることにより、メモリよりもはるかに大きいコレクションに対して転置ファイルを構築する。

Clinical relevance

転置インデックスは、ウェブ検索エンジン、Luceneとその派生製品のようなオープンソース検索プラットフォーム、データベースの全文検索など、事実上すべてのテキスト検索システムの中核となるデータ構造である。その設計は、どのようなクエリタイプがサポートされ、それらがどれだけ迅速かつ安価に回答できるかを決定する。

History

転置ファイルは初期の書誌情報検索システムで使用され、コレクションの増加に伴い全文検索の標準構造となった。1990年代から2000年代にかけての研究、特にシングルパスインメモリインデックス作成のようなスケーラブルな構築方法の開発により、ウェブ規模のコーパスをインデックス化することが実用的になり、この構造は現在、広く使用されているオープンソース検索ライブラリの基盤となっている。

Key figures

• Justin Zobel
• Alistair Moffat
• Steffen Heinz

Seminal works

• zobel2006
• heinz2003
• manning2008

Frequently asked questions

なぜ「転置」インデックスと呼ばれるのか？

通常の（順方向）インデックスは、各文書に含まれる用語をリストする。転置インデックスは、このマッピングを逆転させ、各用語を含む文書をリストする。この転置こそが、用語ベースの検索を高速にする理由である。

位置インデックスは何のために使われるのか？

位置インデックスは、各用語が各文書内で出現する位置を保存する。これにより、システムは、用語が文書内のどこかに現れるかどうかだけでなく、用語の順序や近接性が重要なフレーズクエリや近接クエリに回答できる。