PGM indexダウンロード-PGM PGM indexソースコードのダウンロード

PGM index

C/C++

1.0.0

ダウンロード

区分的な幾何学モデルインデックス（PGM-Index）は、同じ最悪のクエリ時間保証を提供しながら、従来のインデックスよりも数桁少ないスペースを使用して、数十億個のアイテムのアレイで、速いルックアップ、前身、範囲検索、および更新を可能にするデータ構造です。

クイックスタート

これはヘッダーのみのライブラリです。インストールする必要はありません。リポジトリをクローンするだけです

git clone https://github.com/gvinciguerra/PGM-index.git
cd PGM-index

include/pgmディレクトリをシステムまたはプロジェクトのincludeパスにコピーします。

examples/simple.cppファイルは、PGM-Indexを使用してランダム整数のベクトルをインデックス付けおよびクエリする方法を示しています。

# include < vector >
# include < cstdlib >
# include < iostream >
# include < algorithm >
# include " pgm/pgm_index.hpp "

int main () {
    // Generate some random data
    std::vector< int > data ( 1000000 );
    std::generate (data. begin (), data. end (), std:: rand );
    data. push_back ( 42 );
    std::sort (data. begin (), data. end ());

    // Construct the PGM-index
    const int epsilon = 128 ; // space-time trade-off parameter
    pgm::PGMIndex< int , epsilon> index (data);

    // Query the PGM-index
    auto q = 42 ;
    auto range = index . search (q);
    auto lo = data. begin () + range. lo ;
    auto hi = data. begin () + range. hi ;
    std::cout << * std::lower_bound (lo, hi, q);

    return 0 ;
}

Repl.itでこれやその他の例を実行して編集します。または、次のようにローカルに実行します。

g++ examples/simple.cpp -std=c++17 -I./include -o simple
./simple

クラスの概要

上記の例のpgm::PGMIndexクラス以外に、このライブラリは次のクラスを提供します。

pgm::DynamicPGMIndex挿入と削除をサポートしています。
pgm::MultidimensionalPGMIndex Kディメンションでポイントを格納し、直交範囲クエリをサポートします。
pgm::MappedPGMIndexディスクにデータを保存し、PGMINDEXを使用して高速検索操作を使用します。
pgm::CompressedPGMIndexセグメントを圧縮して、インデックスのスペース使用量を削減します。
pgm::OneLevelPGMIndex 、再帰構造ではなく、セグメントでバイナリ検索を使用します。
pgm::BucketingPGMIndexトップレベルのルックアップテーブルを使用して、セグメントの検索をスピードアップします。
pgm::EliasFanoPGMIndexトップレベルの簡潔な構造を使用して、セグメントの検索をスピードアップします。

完全なドキュメントはこちらから入手できます。

テストとチューナーをコンパイルします

リポジトリをクローニングした後、プロジェクトを構築します

cmake . -DCMAKE_BUILD_TYPE=Release
make -j8

テストランナーはtest/に配置されます。チューナー実行可能ファイルはtuner/に配置されます。ベンチマーク実行可能ファイルはbenchmark/に配置されます。

ライセンス

このプロジェクトは、Apacheライセンス2.0の条件に基づいてライセンスされています。

ライブラリを使用する場合は、ウェブサイトにリンクを入れて、次の論文を引用してください。

パオロ・フェラギナとジョルジオ・ヴィンシゲラ。 PGM-Index：予測可能な最悪の範囲の境界を備えた完全にダイナミック圧縮された学習インデックス。 Pvldb、13（8）：1162-1175、2020。

@article{Ferragina:2020pgm,
  Author = {Paolo Ferragina and Giorgio Vinciguerra},
  Title = {The {PGM-index}: a fully-dynamic compressed learned index with provable worst-case bounds},
  Year = {2020},
  Volume = {13},
  Number = {8},
  Pages = {1162--1175},
  Doi = {10.14778/3389133.3389135},
  Url = {https://pgm.di.unipi.it},
  Issn = {2150-8097},
  Journal = {{PVLDB}}}

拡大する

追加情報