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}}}