PGM index

El índice de modelo geométrico por partes (índice PGM) es una estructura de datos que permite una búsqueda rápida, predecesor, búsquedas de rango y actualizaciones en matrices de miles de millones de elementos utilizando órdenes de magnitud menos espacio que los índices tradicionales, al tiempo que proporciona las mismas garantías de tiempo de consulta en el peor de los casos.

Sitio web | Documentación | Papel | Diapositivas | Python Wrapper | Un laboratorio

Inicio rápido

Esta es una biblioteca solo de encabezado. No es necesario instalarlo. Solo clona el repositorio con

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

y copie el directorio include/pgm a la ruta de incluido de su sistema o proyecto.

El archivo examples/simple.cpp muestra cómo indexar y consultar un vector de enteros aleatorios con el índice 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 ;
}

Ejecute y edite este y otros ejemplos en repl.it. O ejecutarlo localmente a través de:

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

Descripción general de las clases

Aparte de la clase pgm::PGMIndex En el ejemplo anterior, esta biblioteca proporciona las siguientes clases:

• pgm::DynamicPGMIndex admite inserciones y deleciones.
• pgm::MultidimensionalPGMIndex almacena puntos en K dimensiones y admite consultas de rango ortogonal.
• pgm::MappedPGMIndex almacena datos en el disco y utiliza un PGMindex para operaciones de búsqueda rápida.
• pgm::CompressedPGMIndex comprime los segmentos para reducir el uso espacial del índice.
• pgm::OneLevelPGMIndex utiliza una búsqueda binaria en los segmentos en lugar de una estructura recursiva.
• pgm::BucketingPGMIndex utiliza una tabla de búsqueda de nivel superior para acelerar la búsqueda en los segmentos.
• pgm::EliasFanoPGMIndex utiliza una estructura sucinta de nivel superior para acelerar la búsqueda en los segmentos.

La documentación completa está disponible aquí.

Compilar las pruebas y el sintonizador

Después de clonar el repositorio, cree el proyecto con

cmake . -DCMAKE_BUILD_TYPE=Release
make -j8

El corredor de prueba se colocará en test/ . El ejecutable de sintonizador se colocará en tuner/ . El ejecutable de referencia se colocará en benchmark/ .

Licencia

Este proyecto tiene licencia bajo los términos de la licencia de Apache 2.0.

Si usa la biblioteca, coloque un enlace al sitio web y cita el siguiente documento:

Paolo Ferragina y Giorgio Vinciguerra. El índice PGM: un índice aprendido comprimido totalmente dinámico con límites de peores casos probables. 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}}}