PGM index

Der stückweise geometrische Modellindex (PGM-Index) ist eine Datenstruktur, die eine schnelle Lookup, Vorgänger, Reichweite und Aktualisierungen in Arrays von Milliarden von Elementen ermöglicht, die Größenordnungen weniger Platz als herkömmliche Indizes verwenden und gleichzeitig die gleichen Zeitgarantie für die Abfragegarerie für schlechteste Fall bieten.

Website | Dokumentation | Papier | Folien | Python Wrapper | A³ Lab

QuickStart

Dies ist eine Nur-Header-Bibliothek. Es muss nicht installiert werden. Klonen Sie einfach das Repo mit

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

und kopieren Sie das include/pgm -Verzeichnis in das System Ihres Systems oder Projekts include Path.

Die examples/simple.cpp -Datei zeigt, wie Sie einen Vektor von zufälligen Ganzzahlen mit dem PGM-Index indexieren und abfragen:

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

Führen und bearbeiten Sie diese und andere Beispiele auf Repl.it. Oder führen Sie es lokal über:

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

Klassenübersicht

Abgesehen von der pgm::PGMIndex -Klasse im obigen Beispiel enthält diese Bibliothek die folgenden Klassen:

• pgm::DynamicPGMIndex unterstützt Insertionen und Löschungen.
• pgm::MultidimensionalPGMIndex speichert Punkte in K -Dimensionen und unterstützt orthogonale Bereichsabfragen.
• pgm::MappedPGMIndex speichert Daten auf der Festplatte und verwendet einen PGMINDEX für schnelle Suchvorgänge.
• pgm::CompressedPGMIndex komprimiert die Segmente, um die Raumnutzung des Index zu verringern.
• pgm::OneLevelPGMIndex verwendet eine binäre Suche in den Segmenten und nicht eine rekursive Struktur.
• pgm::BucketingPGMIndex verwendet eine Suchtabelle auf der obersten Ebene, um die Suche in den Segmenten zu beschleunigen.
• pgm::EliasFanoPGMIndex verwendet eine prägnante Struktur auf höchster Ebene, um die Suche in den Segmenten zu beschleunigen.

Die vollständige Dokumentation finden Sie hier.

Kompilieren Sie die Tests und den Tuner

Erstellen Sie das Projekt nach dem Klonen des Repositorys mit

cmake . -DCMAKE_BUILD_TYPE=Release
make -j8

Der Testläufer wird in test/ platziert. Die ausführbare Tuner -Datei wird in tuner/ platziert. Die ausführbare Benchmark -Datei wird in benchmark/ platziert.

Lizenz

Dieses Projekt ist gemäß den Bestimmungen der Apache -Lizenz 2.0 lizenziert.

Wenn Sie die Bibliothek verwenden, geben Sie bitte einen Link zur Website ein und zitieren Sie das folgende Papier:

Paolo Ferragina und Giorgio Vinciguerra. Der PGM-Index: Ein voll dynamischer komprimierter gelernter Index mit nachweislichsten Grenzen für Worst-Case. 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}}}