インデックス圧縮

インデックス圧縮は、転置インデックスのポスティングリストをコンパクトに符号化することで、検索システムが保存するデータ量を減らし、クエリ応答を高速化します。

Definition

インデックス圧縮とは、転置インデックスの辞書とポスティングに整数および文字列符号化手法を適用し、ストレージフットプリントを削減しつつ、クエリ処理中にポスティングを迅速に復号可能に保つことです。

Scope

このトピックでは、転置インデックスの圧縮技術、特に可変長およびワードアラインされた整数コードによる文書識別子ギャップとターム頻度の符号化について扱います。辞書圧縮、ギャップ（デルタ）符号化、ユニバーサル符号、ガンマ符号、ゴロム符号などの古典的な符号、可変バイト符号やPForDeltaなどのバイトアラインおよびブロックベースのスキーム、そして圧縮率と復号速度のトレードオフについて論じます。インデックス自体の構築や、それを消費するクエリ評価戦略は対象外とします。

Core questions

• 文書識別子間のギャップを符号化することが、ポスティングを効果的に圧縮するのはなぜですか？
• どのような整数コードが使用され、それらは圧縮率と復号速度をどのようにトレードオフしていますか？
• ターム辞書自体はどのように圧縮されますか？
• 圧縮されたポスティングは、クエリのレイテンシを低く保つために十分な速さで復号できますか？
• 圧縮はキャッシュの動作と入出力コストにどのように影響しますか？

Key concepts

• ギャップ（デルタ）符号化
• 可変バイト符号化
• ガンマ符号とゴロム符号
• PForDeltaとブロックベースの符号
• 辞書圧縮
• 圧縮率
• 復号スループット
• SIMD / ベクトル化された復号

Key theories

ポスティングのギャップ符号化

ポスティングリスト内の文書識別子は増加順であるため、連続する識別子間の差分（ギャップ）を格納すると、特に頻繁に出現する用語の密なポスティングの場合、圧縮に適した小さな数値が得られます。

圧縮速度のトレードオフ

ガンマ符号やゴロム符号のようなビットアライン符号は圧縮を最大化しますが、復号が遅い傾向があります。一方、可変バイト符号やPForDeltaのようなバイトアラインおよびブロックベースの符号は、圧縮率を多少犠牲にするものの、はるかに高速でベクトル化可能な復号を実現し、全体的なクエリパフォーマンスにおいて優位に立つことがしばしばあります。

Clinical relevance

圧縮は、大規模な検索操作に不可欠です。インデックスを縮小してメモリやより小さなストレージに収め、入出力を削減し、キャッシュ局所性を向上させることで、クエリのレイテンシとハードウェアコストの両方を低減します。本番環境の検索エンジンやオープンソースの検索ライブラリはすべて、圧縮されたポスティングに依存しています。

History

テキストインデックスのコンパクトな符号化は、転置ファイルと並行して開発され、1990年代のManaging Gigabytesの著作において、古典的なビットアライン符号（ユニバーサル符号、ガンマ符号、ゴロム符号）が体系化されました。ウェブスケール検索がより高速な復号を要求するにつれて、可変バイト符号やPForDeltaなどのバイトアラインおよびブロックベースのスキーム、そして後に1秒あたり数十億の整数を処理できるベクトル化されたデコーダが登場し、重点は速度へと移行しました。

Key figures

• Alistair Moffat
• Ian H. Witten
• Daniel Lemire
• Justin Zobel

Seminal works

• wittenmgb1999
• lemire2015
• manning2008

Frequently asked questions

圧縮されたインデックスは、非圧縮のものよりも高速になるのはなぜですか？

圧縮は、ディスクやメモリから読み取られるデータ量を削減し、これがしばしばボトルネックとなります。現代の整数コードは、ベクトル命令を頻繁に利用することで非常に高速に復号されるため、入出力で節約される時間と改善されたキャッシュ動作が、復号作業を十分に補って余りある効果をもたらします。

生の文書識別子の代わりにギャップを保存するのはなぜですか？

ポスティングリスト内の文書識別子はソートされており、増加順であるため、連続する識別子間の差は小さい傾向があります。大きな絶対識別子の代わりにこれらの小さなギャップを保存することで、コンパクトなコードが非常に少ないビットで表現できる値が生成されます。