الصفحة الرئيسية>المتعلقة بالبرمجة>ج/ج++
تنزيل

فهرس النموذج الهندسي المتقطعة (PGM-Index) هو بنية بيانات تتيح البحث السريع والسلف وعمليات البحث في المدى والتحديثات في صفائف من العناصر التي تستخدم أوامر ذات حجم أقل من الفهارس التقليدية مع توفير نفس ضمانات وقت الاستعلام الأسوأ.

الموقع | الوثائق | ورقة | الشرائح | غلاف بيثون | مختبر A³

Quickstart

هذه مكتبة رأس فقط. لا يحتاج إلى تثبيت. فقط استنساخ الريبو مع 

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

ونسخ دليل include/pgm إلى مسار نظامك أو مشروعك.

يوضح ملف 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}}}
يوسع
معلومات إضافية
تطبيقات ذات صلة
نوصي لك
أخبار ذات صلة الكل