PGM index

O índice de modelo geométrico por partes (PGM-Index) é uma estrutura de dados que permite uma pesquisa rápida, antecessor, pesquisas de alcance e atualizações em matrizes de bilhões de itens usando ordens de magnitude menos espaço que os índices tradicionais, fornecendo as mesmas garantias de tempo de consulta de pior caso.

Site | Documentação | Papel | Slides | Wrapper Python | A³ Lab

Investir rápido

Esta é uma biblioteca somente para cabeçalho. Não precisa ser instalado. Apenas clone o repo com

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

e copie o diretório include/pgm para o seu sistema ou projeto incluir o caminho.

O arquivo examples/simple.cpp mostra como indexar e consultar um vetor de números inteiros aleatórios com o 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 ;
}

Execute e edite este e outros exemplos no Repl.it. Ou executá -lo localmente via:

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

Visão geral das aulas

Além da classe pgm::PGMIndex no exemplo acima, esta biblioteca fornece as seguintes classes:

• pgm::DynamicPGMIndex suporta inserções e exclusões.
• pgm::MultidimensionalPGMIndex armazena pontos em dimensões k e suporta consultas de intervalo ortogonais.
• pgm::MappedPGMIndex armazena dados no disco e usa um PGMIndex para operações de pesquisa rápida.
• pgm::CompressedPGMIndex comprime os segmentos para reduzir o uso de espaço do índice.
• pgm::OneLevelPGMIndex usa uma pesquisa binária nos segmentos em vez de uma estrutura recursiva.
• pgm::BucketingPGMIndex usa uma tabela de pesquisa de nível superior para acelerar a pesquisa nos segmentos.
• pgm::EliasFanoPGMIndex usa uma estrutura sucinta de nível superior para acelerar a pesquisa nos segmentos.

A documentação completa está disponível aqui.

Compilar os testes e o sintonizador

Depois de clonar o repositório, construa o projeto com

cmake . -DCMAKE_BUILD_TYPE=Release
make -j8

O corredor de teste será colocado em test/ . O executável do sintonizador será colocado no tuner/ . O executável de referência será colocado em benchmark/ .

Licença

Este projeto está licenciado nos termos da licença Apache 2.0.

Se você usar a biblioteca, coloque um link para o site e cite o seguinte artigo:

Paolo Ferragina e Giorgio Vinciguerra. O INDEX PGM: um índice aprendido compactado totalmente dinâmico com limites comprováveis ​​de piores casos. 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}}}