PGM index

Indeks model geometris piecewise (PGM-index) adalah struktur data yang memungkinkan pencarian cepat, pendahulu, rentang pencarian dan pembaruan dalam array miliaran item menggunakan pesanan besar lebih sedikit ruang daripada indeks tradisional sambil memberikan jaminan waktu kueri terburuk yang sama.

Situs web | Dokumentasi | Kertas | Slide | Pembungkus Python | A³ Lab

QuickStart

Ini adalah perpustakaan header saja. Itu tidak perlu diinstal. Cukup klon repo dengan

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

dan salin direktori include/pgm ke jalur sistem atau proyek Anda.

File examples/simple.cpp menunjukkan cara mengindeks dan meminta vektor bilangan bulat acak dengan indeks 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 ;
}

Jalankan dan edit ini dan contoh lainnya di repl.it. Atau jalankan secara lokal melalui:

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

Tinjauan Kelas

Selain kelas pgm::PGMIndex dalam contoh di atas, perpustakaan ini menyediakan kelas -kelas berikut:

• pgm::DynamicPGMIndex mendukung penyisipan dan penghapusan.
• pgm::MultidimensionalPGMIndex menyimpan poin dalam dimensi K dan mendukung kueri rentang ortogonal.
• pgm::MappedPGMIndex menyimpan data pada disk dan menggunakan PGMIndex untuk operasi pencarian cepat.
• pgm::CompressedPGMIndex mengompres segmen untuk mengurangi penggunaan ruang indeks.
• pgm::OneLevelPGMIndex menggunakan pencarian biner pada segmen daripada struktur rekursif.
• pgm::BucketingPGMIndex menggunakan tabel pencarian tingkat atas untuk mempercepat pencarian pada segmen.
• pgm::EliasFanoPGMIndex menggunakan struktur ringkas tingkat atas untuk mempercepat pencarian pada segmen.

Dokumentasi lengkap tersedia di sini.

Mengkompilasi tes dan tuner

Setelah mengkloning repositori, bangun proyek dengan

cmake . -DCMAKE_BUILD_TYPE=Release
make -j8

Test Runner akan ditempatkan di test/ . Tuner yang dapat dieksekusi akan ditempatkan di tuner/ . Benchmark dapat dieksekusi akan ditempatkan di benchmark/ .

Lisensi

Proyek ini dilisensikan berdasarkan ketentuan Lisensi Apache 2.0.

Jika Anda menggunakan perpustakaan, silakan letakkan tautan ke situs web dan mengutip makalah berikut:

Paolo Ferragina dan Giorgio Vinciguerra. Indeks PGM-index: indeks terpelajar terkompresi sepenuhnya dinamis dengan batas terburuk yang terbukti. 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}}}