PGM index

Кусочно-индекс геометрической модели (PGM-Index) представляет собой структуру данных, которая позволяет быстрый поиск, предшественник, поиск в диапазоне и обновления в массивах миллиардов предметов, используя заказа меньше пространства, чем традиционные индексы, предоставляя те же гарантии времени задачи в наихудшем случае.

Веб -сайт | Документация | Бумага | Слайды | Python Wrapper | Ай -лаборатория

QuickStart

Это библиотека только для заголовка. Это не должно быть установлено. Просто клонировать репо

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

и скопируйте каталог include/pgm в Project's Project или Project.

Файл examples/simple.cpp показывает, как индексировать и запрашивать вектор случайных целых чисел с помощью 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 ;
}

Запустите и отредактируйте это и другие примеры на 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.

Если вы используете библиотеку, пожалуйста, поместите ссылку на веб -сайт и приведите следующую статью:

Паоло Феррагина и Джорджио Винсигерра. PGM-индекс: полностью динамический сжатый индекс с доказываемыми границами худшего. 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}}}