PGM index

L'indice de modèle géométrique par morceaux (PGM-Index) est une structure de données qui permet une recherche rapide, un prédécesseur, des recherches de plages et des mises à jour dans des tableaux de milliards d'éléments utilisant des ordres de grandeur moins d'espace que les index traditionnels tout en offrant les mêmes garanties de temps de requête du pire cas.

Site Web | Documentation | Papier | Diapositives | Python Wrapper | Laboratoire

Start

Il s'agit d'une bibliothèque d'en-tête uniquement. Il n'a pas besoin d'être installé. Il suffit de cloner le repo avec

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

et copiez le répertoire include/pgm sur le chemin incluent de votre système ou de votre projet.

Le fichier examples/simple.cpp montre comment indexer et interroger un vecteur d'entiers aléatoires avec l'index PGM:

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

Exécutez et modifiez cela et d'autres exemples sur REPL.it. Ou l'exécutez localement via:

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

Présentation des cours

Autre que la classe pgm::PGMIndex dans l'exemple ci-dessus, cette bibliothèque fournit les classes suivantes:

• pgm::DynamicPGMIndex prend en charge les insertions et les suppressions.
• pgm::MultidimensionalPGMIndex stocke des points dans les dimensions k et prend en charge les requêtes de plage orthogonale.
• pgm::MappedPGMIndex stocke les données sur le disque et utilise un pgMindex pour les opérations de recherche rapide.
• pgm::CompressedPGMIndex comprime les segments pour réduire l'utilisation de l'espace de l'index.
• pgm::OneLevelPGMIndex utilise une recherche binaire sur les segments plutôt qu'une structure récursive.
• pgm::BucketingPGMIndex utilise une table de recherche de niveau supérieur pour accélérer la recherche sur les segments.
• pgm::EliasFanoPGMIndex utilise une structure succincte de niveau supérieur pour accélérer la recherche sur les segments.

La documentation complète est disponible ici.

Compiler les tests et le tuner

Après cloner le référentiel, construisez le projet avec

cmake . -DCMAKE_BUILD_TYPE=Release
make -j8

Le coureur de test sera placé dans test/ . L'exécutable de tuner sera placé dans tuner/ . L'exécutable de référence sera placé dans benchmark/ .

Licence

Ce projet est sous licence en vertu des termes de l'Apache License 2.0.

Si vous utilisez la bibliothèque, veuillez mettre un lien vers le site Web et citer l'article suivant:

Paolo Ferragina et Giorgio Viniguerra. L'indice PGM: un indice appris compressé entièrement dynamique avec des limites de pire cas prouvables. 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}}}