PGM index

分段幾何模型索引（PGM-INDEX）是一種數據結構，可以使用比傳統索引的空間少的數十億個項目中的快速查找，前身，範圍搜索和更新，同時提供相同的最差案例查詢時間保證。

網站|文檔|紙|幻燈片| Python包裝| A³實驗室

Quickstart

這是一個僅限標題庫。它不需要安裝。只是用

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

並將include/pgm目錄複製到系統或項目的Inclage Path。

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的條款獲得許可的。

如果您使用庫，請在網站上放置一個鏈接，並引用以下論文：

Paolo Ferragina和Giorgio Vinciguerra。 PGM索引：具有可證明的最壞情況邊界的完全動態壓縮學指數。 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}}}