Crate pgm_index

PGM-Index: Ultra-Fast Learned Index

A high-performance implementation of the Piecewise Geometric Model (PGM) Index, a learned data structure for fast lookups in sorted arrays.

Overview

The PGM-Index builds a piecewise linear model of your sorted data and uses it to predict element positions, significantly outperforming binary search for large datasets.

Features

• Ultra-fast lookups: Often 3-10x faster than binary search
• Memory efficient: Low memory overhead per element
• Parallel processing: SIMD-optimized with multi-threading support

Usage

use pgm_index::PGMIndex;

fn main() {
    let data: Vec<u64> = (0..1_000_000).collect();
    let pgm = PGMIndex::new(data, 32);
    assert_eq!(pgm.get(123_456), Some(123_456));
}

Notes

• Keys must be sorted ascending.

The epsilon parameter controls the trade-off between memory usage and query speed:

• Smaller epsilon → more segments → better predictions → faster queries
• Larger epsilon → fewer segments → coarser predictions → more memory efficient

Recommended epsilon values: 16-128 for most use cases.

Structs

PGMIndex

PGMStats

Lightweight stats for export

Segment

Linear segment: y = slope * x + intercept (x — index, y — key)

Traits

Key

Trait bound for key types supported by the PGM-Index

Functions

init_rayon_min_threads

Ensure Rayon global thread-pool is initialized with at least 4 threads.