PGM index

PGM-Index (Pistewise Geometric Model Index)는 기존 인덱스보다 공간보다 적은 공간을 사용하여 빠른 조회, 이전 모델, 범위 검색 및 업데이트를 제공하면서 동일한 최악의 쿼리 시간 보증을 제공하는 데이터 구조입니다.

웹 사이트 | 문서 | 종이 | 슬라이드 | 파이썬 포장지 | A³ Lab

QuickStart

헤더 전용 라이브러리입니다. 설치할 필요가 없습니다. 저장소를 복제하십시오

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

include/pgm 디렉토리를 시스템 또는 프로젝트 포함 경로에 복사하십시오.

examples/simple.cpp 파일은 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 ;
}

Repl.it. 에서이 예와 다른 예제를 실행하고 편집하십시오. 또는 로컬로 실행하십시오.

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

수업 개요

위의 예에서 pgm::PGMIndex 클래스 외에이 라이브러리는 다음 클래스를 제공합니다.

• pgm::DynamicPGMIndex 삽입 및 삭제를 지원합니다.
• pgm::MultidimensionalPGMIndex k 치수로 포인트를 저장하고 직교 범위 쿼리를 지원합니다.
• pgm::MappedPGMIndex 디스크에 데이터를 저장하고 빠른 검색 작업에 PGMINDEX를 사용합니다.
• pgm::CompressedPGMIndex 세그먼트를 압축하여 인덱스의 공간 사용을 줄입니다.
• pgm::OneLevelPGMIndex 재귀 구조가 아닌 세그먼트에서 이진 검색을 사용합니다.
• pgm::BucketingPGMIndex 최상위 조회 테이블을 사용하여 세그먼트의 검색 속도를 높입니다.
• pgm::EliasFanoPGMIndex 최상위 간결 구조를 사용하여 세그먼트의 검색 속도를 높입니다.

전체 문서는 여기에서 제공됩니다.

테스트와 튜너를 컴파일합니다

저장소를 복제 한 후 프로젝트를 구축하십시오

cmake . -DCMAKE_BUILD_TYPE=Release
make -j8

테스트 러너는 test/ 에 배치됩니다. 튜너 실행 파일은 tuner/ 에 배치됩니다. 벤치 마크 실행 파일은 benchmark/ 에 배치됩니다.

특허

이 프로젝트는 Apache 라이센스 2.0의 조건에 따라 라이센스가 부여됩니다.

도서관을 사용하는 경우 웹 사이트에 대한 링크를 넣고 다음 논문을 인용하십시오.

Paolo Ferragina와 Giorgio Vinciguerra. PGM-Index : 최악의 최악의 경계를 가진 완전 제압 된 학습 된 학습 지수. 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}}}