The PGM-index: a multicriteria, compressed and learned approach to data indexing

Paolo Ferragina; Giorgio Vinciguerra

Source-linked AI summary

The PGM-index: a multicriteria, compressed and learned approach to data indexing

Paolo Ferragina, Giorgio Vinciguerra

arXiv:1910.06169v1Oct 14, 2019cs.DScs.DBcs.IRcs.LG

TL;DR

Learned indexes improve indexing efficiency but traditionally lack guarantees and adaptable resource trade-offs. This paper introduces the recursively constructed PGM-index and three variants, reporting major space reductions with comparable query efficiency and rapid adaptation to changing constraints.

Problem
Learned indexes provide efficiency gains but are heuristic, lacking guaranteed time and space requirements and flexible adaptation to changing application constraints.
Method
The PGM-index recursively constructs optimal piecewise linear models, with variants for model compression, query-distribution awareness, and multicriteria tuning.
Results
The PGM-index reduces space by 63.3% versus FITing-tree and by more than four orders of magnitude versus B-tree while matching or improving query efficiency.
Takeaways & Limitations
The PGM-index supports compressed, distribution-aware, and rapidly self-tuned indexing across changing space, latency, and query-distribution requirements.
Takeaways & Limitations
The multicriteria time model may misestimate actual query time because of hardware-dependent caches and CPU prefetching.

Abstract

from arXiv · show

The recent introduction of learned indexes has shaken the foundations of the decades-old field of indexing data structures. Combining, or even replacing, classic design elements such as B-tree nodes with machine learning models has proven to give outstanding improvements in the space footprint and time efficiency of data systems. However, these novel approaches are based on heuristics, thus they lack any guarantees both in their time and space requirements. We propose the Piecewise Geometric Model index (shortly, PGM-index), which achieves guaranteed I/O-optimality in query operations, learns an optimal number of linear models, and its peculiar recursive construction makes it a purely learned data structure, rather than a hybrid of traditional and learned indexes (such as RMI and FITing-tree). We show that the PGM-index improves the space of the FITing-tree by 63.3% and of the B-tree by more than four orders of magnitude, while achieving their same or even better query time efficiency. We complement this result by proposing three variants of the PGM-index. First, we design a compressed PGM-index that further reduces its space footprint by exploiting the repetitiveness at the level of the learned linear models it is composed of. Second, we design a PGM-index that adapts itself to the distribution of the queries, thus resulting in the first known distribution-aware learned index to date. Finally, given its flexibility in the offered space-time trade-offs, we propose the multicriteria PGM-index that efficiently auto-tune itself in a few seconds over hundreds of millions of keys to the possibly evolving space-time constraints imposed by the application of use. We remark to the reader that this paper is an extended and improved version of our previous paper titled "Superseding traditional indexes by orchestrating learning and geometry" (arXiv:1903.00507).

1. INTRODUCTION

Learned indexes recast indexing as succinct models that approximate key rank, but existing approaches lack controllable guarantees and flexibility. The PGM-index addresses these limitations with recursively constructed optimal linear models and variants for compression, query distributions, and changing resource constraints.

Research gap: Existing methods leave a need for data structures flexible enough to operate under computational constraints that vary across users, devices, applications, and time.Traditional index families also have limitations: hash-based indexes do not support predecessor or range searches, while bitmap- and trie-based indexes can impose storage or pointer overheads.
Motivation and background: Learned indexes model keys as points mapping key values to their positions, enabling potential space savings over conventional index structures.For regularly spaced keys, rank can be computed exactly with constant time and space.
Limitations of prior learned indexes: RMI uses a hierarchy of machine-learning models followed by binary search over a neighboring position range, but its trade-offs depend on data and model choices.FITing-tree restricts models to linear functions and exposes an error parameter ε controlling the final search region.
The PGM-index: The PGM-index recursively builds optimal piecewise linear models, producing a purely learned structure with guaranteed I/O-optimal query operations and theoretical space-time bounds.Its segments use an optimal number of linear models, unlike the hybrid RMI and FITing-tree designs.
Variants and adaptation: The paper adds compressed, distribution-aware, and multicriteria variants to adapt space usage, query behavior, and tuning to application requirements.The multicriteria version reorganizes a 750M-key dataset in less than 20 seconds under newly specified space or time bounds.

2. THE PGM-index

The PGM-index combines optimal piecewise-linear rank approximation with recursive learned routing. It uses a minimum number of ε-approximate segments while retaining bounded query and space complexity.

Optimal PLA-model: The PGM-index maps keys to approximate positions using a minimum number of ε-approximate linear segments.An optimal PLA-model can be computed in linear time and space, and exact positions are recovered by binary search within ±ε keys.
Querying: Each segment occupies constant space and answers its approximate-position query in constant time, while exact rank is obtained by local binary search.The recursive index searches a range of size 2ε around each estimated position at every level.
Recursive construction: Recursive construction turns each PLA-model into keys for another model, continuing until a single segment forms the hierarchy.Each segment routes queries to a segment at the next level, adapting the structure to the input-key distribution.
Design advantages: Unlike B-tree-like indexes, PGM-index nodes have data-driven fan-out and constant-space routing segments that restrict searches to ε-sized subsets.Traditional nodes store many keys according mainly to disk-page size, whereas PGM-index routing exploits regularity in the data distribution.
Complexity guarantees: The Recursive PGM-index uses Θ(m) space and answers rank, membership, and predecessor queries in O(log m) time.In external memory, its query cost is O((log_c m) log(ε/B)) I/Os, with c ≥ 2ε.
Complexity guarantees: The PGM-index’s space overhead depends on the input array’s regularity rather than growing linearly with n, and it is I/O-optimal for predecessor search.Its space and time are asymptotically no worse than a 2ε-way tree under the stated conditions.

3. THE COMPRESSED PGM-index

The compressed PGM-index losslessly compresses its segment representation, especially by exploiting repeated slopes and monotone intercepts. These techniques preserve the ε-guarantee while reducing space.

Compression design: Compression targets the PGM-index’s keys, intercepts, and slopes, with segment compression treated separately from orthogonal key-compression methods.The proposed techniques are tailored to the learned segments that form the index.
Intercept compression: The coordinate transformation used for intercept compression increases ε by 1.This is an explicit precision trade-off associated with storing truncated integer intercepts.
Intercept compression: Intercepts are transformed into increasing integers and stored in m log(n/m) + 1.92m + o(m) bits with O(1) random access.The intercept representation uses the segment coordinate system and succinct storage for increasing integers.
Slope compression: The slope compressor replaces the original slopes with the minimum number t of distinct slopes while preserving ε-approximation.It processes m slope intervals and selects shared slopes that lie within the relevant intervals.
Slope compression: The compressed slopes require 64t + m⌈log t⌉ bits and can be computed in O(m log m) time.The representation stores t floating-point slopes and encodes each segment’s slope by its table position.

4. THEDISTRIBUTION-AWAREPGM-index

The distribution-aware PGM-index adapts learned routing to known query probabilities rather than assuming uniform queries. It targets entropy-sensitive average query time while retaining succinct space.

Motivation: The standard PGM-index assumes uniformly distributed queries, whereas practical workloads such as search-engine queries can be skewed.The distribution-aware variant is motivated by the goal of answering frequent queries faster than rare ones.
Design: The distribution-aware variant adapts to both input-key and query distributions and is presented as the first distribution-aware learned index.It is additionally described as very succinct in space.
Target bound: For a key with known probability p_i, the target search time is O(log(1/p_i)), yielding average time equal to the query-distribution entropy H.The distribution-aware dictionary problem explicitly defines this probability-sensitive objective.
Construction: The construction assigns each key a y-range of size min{1/p_i, ε} and applies the optimal PLA algorithm to those ranges.This modifies the approximation constraints so segment search cost reflects query probabilities.
Space: The variant uses O(m + Lε) space, which is O(m) when ε is constant.The level count is L = O(log_c m) with c ≥ 2ε.
Guarantees: The Distribution-Aware Recursive PGM-index uses O(m) space and answers queries in O(H) average time.Here m is the number of ε-approximate segments in the optimal PLA-model for the array keys.

5. THE MULTICRITERIA PGM-index

The multicriteria PGM-index automates choosing a space–time operating point for changing application requirements. It models the trade-off between approximation error, space, and query time, then refines candidate settings using measured performance.

Motivation: Data structures may need retuning as data distributions, devices, and resource requirements change, making manual grid searches difficult and potentially costly.The search space may be too large for timely reorganisation, or the structure may lack sufficient flexibility.
Optimisation goals: Given a space constraint, the optimisation outputs the PGM-index with minimum query time; given a time bound, it minimises space.These are respectively the time-minimisation and space-minimisation problems.
Trade-off model: The recursive PGM-index models query time as t(ε) = c(log2ε m) log(2ε/B) and bounds total segments through the segment counts at each level.Here, m is the number of last-level segments, B is the page size, and c depends on memory-access latency.
Parameter search: Because the exact dataset-dependent segment count lacks a closed formula, the method estimates the final-level count with a fitted power law aε^-b.The approximation covers both the pessimistic theoretical bound and the best case of a strictly linear dataset.
Trade-off model: Increasing ε decreases space occupancy but increases query time because binary searches examine 2ε keys at each level.The feasible ε values are searched within E = [B/2, n/2], and the time-minimisation solution is the lowest ε satisfying the space bound.
Parameter search: The time model can misestimate actual query time because caches, CPU pre-fetching, and scheduler effects introduce hardware-dependent variation and measurement error.The method therefore uses measured average query time from random-query batches and stops when the remaining search interval is sufficiently small.

6. EXPERIMENTS

Experiments across synthetic and real-world datasets show that the PGM-index substantially reduces space while retaining competitive query performance and fast construction. Its recursive, distribution-adaptive design dominates traditional and learned alternatives across space-time trade-offs, while compression further reduces space at moderate query cost.

Experimental setup: The experiments use Web logs, Longitude, IoT, and synthetic datasets spanning uniform, Zipf, and lognormal distributions.The real-world datasets contain about 715M, 166M, and 26M keys or events, respectively.
Space occupancy: 20.8%–69.4% space savings were measured against FITing-tree on six synthetic datasets of 1G elements.On real-world datasets, the corresponding savings ranged from 37.7% to 63.3%.
Space occupancy: Two to five orders of magnitude fewer segments than keys were observed, with at least two orders of magnitude at ε = 8.The segment count is the principal driver of the learned index’s space footprint.
Query performance: The Recursive PGM-index dominated alternative PGM configurations, RMI, and traditional indexes across the evaluated space-time trade-offs.Its recursive construction yielded five levels versus seven for PGM◦CSS, shortening traversal time through a higher branching factor.
Query performance: 82.7× less space matched the fastest CSS-tree’s query performance, while four orders of magnitude less space matched the fastest B+-tree’s performance.The examples used 4 MiB versus 341 MiB for CSS-tree and 87 KiB versus 874 MiB for B+-tree.
Compressed PGM-index: Up to 99.94% fewer distinct slopes and up to 81.2% lower last-level space were achieved by slope compression, while full compression reduced space up to 52.2% with query slowdowns no greater than 24.5%.Slope compression can be ineffective on Longitude for ε ≥29 because the slope-table mapping overhead exceeds the original segment space.
Multicriteria PGM-index: The multicriteria PGM-index selected space- or time-oriented configurations under tolerances and completed in less than 20 seconds in both modes.The approach targets applications with changing data distributions and space-time constraints.

7. CONCLUSIONS AND FUTURE WORK

The paper introduces the PGM-index and three variants that improve space, query performance, query-distribution adaptation, and multicriteria optimization. It identifies dynamic updates and combining additional indexing techniques as future research directions.

The PGM-index improves query performance and space occupancy for traditional and modern learned indexes by up to several orders of magnitude.
Three variants provide ad-hoc compression, query-distribution adaptation, and estimations of individual-key or range-key occurrences.
The multicriteria PGM-index can be rapidly optimized under user-given space-occupancy or query-time constraints.
Future work: Future work includes evaluating PGM-index insertion and deletion using split-merge strategies or buffers merged into the index.
Future work: Another research direction is orchestrating segments, nonlinear models, and rank/select indexing techniques within the multicriteria framework.