📐 pgm_index — Learned Index for Sorted Keys

PGM-Index is a space-efficient data structure for fast lookup in sorted sequences.
It approximates the distribution of keys with piecewise linear models, allowing searches in O(log ε) with a guaranteed error bound.

📄 Algorithm

Based on the work by Paolo Ferragina & Giorgio Vinciguerra:

The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds (2020)
🔗 Paper · 🌐 Official site

📦 Installation

Add to your Cargo.toml:

[dependencies]
pgm_index = "*"

🛠 Usage

use pgm_index::PGMIndex;

fn main() {
    let data: Vec<u64> = (0..1_000_000).collect();
    let pgm = PGMIndex::new(&data, 32); // ε = 32

    let key = 123456;
    if let Some(pos) = pgm.search(key) {
        println!("Found at position {}", pos);
    } else {
        println!("Not found");
    }
}

🏎 Benchmarks by ε

Dataset: 1,000,000 elements, 100,000 random queries CPU: Intel Core i7 12700, Windows 11, single-threaded

Binary Search (baseline): 4.32 ms, 23.13 M/s, 43.2 ns/query.

📊 Comparison to Other Indexes (1M elements) *

Using ε = 32 as a balanced configuration:

• our benchmarks

📈 Relative Performance *

• our benchmarks

📌 Potential Use Cases

• Indexing large sorted numeric datasets
• Time-series databases
• Read-optimized storage engines
• Scientific & bioinformatics data search
• Columnar store secondary indexes

📜 License

MIT