หน้าแรก>การเขียนโปรแกรมที่เกี่ยวข้อง>ซี/ซี++
ดาวน์โหลด

ดัชนีแบบจำลองเรขาคณิตแบบชิ้นเดียว (PGM-index) เป็นโครงสร้างข้อมูลที่ช่วยให้การค้นหาที่รวดเร็ว, รุ่นก่อน, การค้นหาช่วงและการอัปเดตในอาร์เรย์ของรายการหลายพันล้านรายการโดยใช้คำสั่งของขนาดพื้นที่น้อยกว่าดัชนีดั้งเดิม

เว็บไซต์ | เอกสาร กระดาษ | สไลด์ Python Wrapper | ห้องแล็บ

เร็ว

นี่คือห้องสมุดส่วนหัวเท่านั้น ไม่จำเป็นต้องติดตั้ง เพียงแค่โคลน repo ด้วย 

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

และคัดลอกไดเรกทอรี include/pgm ไปยังเส้นทางของระบบหรือ 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 License 2.0

หากคุณใช้ห้องสมุดโปรดใส่ลิงค์ไปยังเว็บไซต์และอ้างถึงกระดาษต่อไปนี้:

Paolo Ferragina และ Giorgio Vinciguerra PGM-Index: ดัชนีที่เรียนรู้อย่างสมบูรณ์แบบ dynamic ที่ได้รับการบีบอัดพร้อมขอบเขตกรณีที่เลวร้ายที่สุดที่พิสูจน์ได้ 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}}}
ขยาย
ข้อมูลเพิ่มเติม
แอปที่เกี่ยวข้อง
แนะนำสำหรับคุณ
ข้อมูลที่เกี่ยวข้อง ทั้งหมด