ds2i
1.0.0
Data Structures for Inverted Indexes (ds2i) は、転置インデックスで使用される整数シーケンスを表すデータ構造のライブラリです。
このコードは以下の論文の実験で使用されました。
Giuseppe Ottaviano、Rossano Venturini、 Partitioned Elias-Fano Indexes 、ACM SIGIR 2014。
Giuseppe Ottaviano、Nicola Tonellotto、Rossano Venturini、 「転置インデックスの最適時空トレードオフ」 、ACM WSDM 2015。
コードは、Linux では GCC 4.9 で、OSX Yosemite では Clang でテストされています。
ビルドには次の依存関係が必要です。
コードはいくつかの git サブモジュールに依存しています。 --recursiveを使用せずにリポジトリのクローンを作成した場合は、ビルドする前に次のコマンドを実行する必要があります。
$ git submodule init
$ git submodule update
コードを構築するには:
$ mkdir build
$ cd build
$ cmake .. -DCMAKE_BUILD_TYPE=Release
$ make
単体テストを実行するmake test実行することも推奨されます。
ディレクトリtest/test_data単体テストで使用される小さなドキュメント コレクションが含まれています。コレクションのバイナリ形式については、次のセクションで説明します。
インデックスを作成するには、 create_freq_indexコマンドを使用します。使用可能なインデックス タイプは、 index_types.hppにリストされています。たとえば、テスト コレクションを使用して最適なパーティション分割アルゴリズムを使用してインデックスを作成するには、次のコマンドを実行します。
$ ./create_freq_index opt ../test/test_data/test_collection test_collection.index.opt --check
ここで、 test/test_data/test_collectionはコレクションのベース名、つまり.{docs,freqs,sizes}拡張子を除いた名前で、 test_collection.index.optは出力インデックスのファイル名です。 --checkインデックスの正確性をチェックするための検証手順を実行します。
BM25 クエリを実行するには、ドキュメントの長さなど、スコアの計算に必要なパラメータを含む追加ファイルを構築する必要があります。ファイルは次のコマンドで構築できます。
$ ./create_wand_data ../test/test_data/test_collection test_collection.wand
これで、インデックスをクエリできるようになりました。このコマンドqueries標準入力の各行をタブで区切られた用語 ID のコレクションとして解析します。ここで、i 番目の用語は入力コレクション内の i 番目のリストです。クエリのセットの例は、やはりtest/test_dataにあります。
$ ./queries opt and test_collection.index.opt test_collection.wand < ../test/test_data/queries
これにより、結合クエリ ( and ) が実行されます。 andの代わりに、他の演算子 ( or 、 wand 、 ...、 queries.cpp参照) を使用したり、コロンで区切られた複数の演算子 ( and:or:wand ) を使用したりできます。
特定のクエリ分散とスペース バジェットに対して最適なインデックス時間を構築するには、次の手順に従う必要があります。
まず、ブロックベースのインデックスをコレクションに構築する必要があります。これは、ブロックアクセス統計を収集するために使用されます。
$ ./create_freq_index block_optpfor ../test/test_data/test_collection test_collection.index.block_optpfor
$ ./create_wand_data ../test/test_data/test_collection test_collection.wand
次に、クエリ分布からサンプリングされた一連のクエリを基に、統計を生成できます。
$ ./profile_queries block_optpfor ranked_and:wand:maxscore
test_collection.index.block_optpfor test_collection.wand
< ../test/test_data/queries
> query_profile
ブロックのデコード時間を予測するには、サンプルでそれを測定する必要があります。
$ ./profile_decoding block_optpfor test_collection.index.block_optpfor 0.1 > decoding_times.json
0.1 は、サンプリングされたブロックの割合です。大きなインデックスの場合は、非常に小さい数を使用できます。測定された時間を線形モデルのトレーニングに使用できます。
$ ./dec_time_regression.py parse_data decoding_times.json decoding_times.pandas
$ ./dec_time_regression.py train decoding_times.pandas > linear_weights.tsv
上記のスクリプトには、Numpy、Scipy、Pandas、および Theano が必要です。
最後に、新しいインデックス (たとえば、上記で生成されたblock_optpforインデックスよりわずかに小さいもの) を構築できます。
$ ./optimal_hybrid_index block_optpfor linear_weights.tsv
query_profile test_collection.index.block_optpfor
lambdas.bin 4000000 test_collection.index.block_mixed
貪欲アルゴリズムで計算されたクリティカル ポイントはlambdas.binファイルにキャッシュされ、異なる時空間トレードオフを持つ他のインデックスを生成するために再利用できます。それらを再計算するには (クエリ プロファイルが変更された場合など)、ファイルを削除するだけです。
これでインデックスをクエリできるようになりました。
$ ./queries block_mixed ranked_and test_collection.index.block_mixed
test_collection.wand < ../test/test_data/queries
...
Mean: 9.955
...
$ ./queries block_optpfor ranked_and test_collection.index.block_optpfor
test_collection.wand < ../test/test_data/queries
...
Mean: 11.125
...
新しいインデックスは古いインデックスよりも高速であり、サイズも小さいことに注意してください。もちろん、トレーニングしたのと同じクエリを使用してテストしているため、ここでは不正行為を行っています。実際のアプリケーションでは、トレーニングとテストのセットは独立しています。
以下のコマンドでトレードオフカーブのサンプルを出力することも可能です。
$ ./optimal_hybrid_index block_optpfor linear_weights.tsv
query_profile test_collection.index.block_optpfor
lambdas.bin 0 lambdas.tsv
ファイルlambdas.tsvは、トリプル (ラムダ、スペース、推定時間) のサンプルが含まれます。
バイナリ シーケンスは、その長さが接頭辞として付けられた整数のシーケンスであり、シーケンスの整数と長さの両方が 32 ビットのリトル エンディアンの符号なし整数として書き込まれます。
コレクションは、 <basename>.docs 、 <basename>.freqs 、 <basename>.sizesの 3 つのファイルで構成されます。
<basename>.docsシングルトン バイナリ シーケンスで始まり、その唯一の整数はコレクション内のドキュメントの数です。その後、用語 ID の順に、投稿リストごとに 1 つのバイナリ シーケンスが続きます。各投稿リストには、用語を含む一連の文書 ID が含まれています。
<basename>.freqsは、ポスティング リストごとに 1 つのバイナリ シーケンスで構成されます。各シーケンスには、前のファイルと一致するポスティングの出現カウントが含まれます (ただし、このファイルの先頭には追加のシングルトン リストがないことに注意してください)。
<basename>.sizesは、コレクション内のドキュメントの数と同じ長さの単一のバイナリ シーケンスで構成され、シーケンスの i 番目の要素は i 番目のドキュメントのサイズ (用語の数) です。
