patched-frame-of-reference · shipping · also PFOR, Patched FOR, Patched frame of reference

Patched frame-of-reference

Patched frame-of-reference is a family of integer compression schemes that bit-pack values at a chosen width and separately encode information needed to reconstruct exceptions.

Related Observatory article: Read on hesela.com

Exceptions: An unsigned value at or above 2^b does not fit b bits. Handling it separately can avoid increasing the packed width for every value, but exception positions, payloads and headers also cost space. Selecting a smaller width does not by itself minimize total size. [1]

Base choice: The original PFOR design permits a base above some input values and stores below-base values as exceptions. PFOR-DELTA specifically applies PFOR to adjacent differences. [3]

Variants: Original PFOR, NewPFD, OptPFD and FastPFOR differ in width selection and exception layout. FastPFOR selects widths per block and groups exception high bits across a page. Do not assume every variant stores complete exceptional values or uses one shared wire format. [1]

Example: Appending 2024 to 1000, 1001, 1003 and 1007 makes the maximum base-1000 offset 1024. Plain packing needs 11 bits per offset. A toy low/high split at width 3 uses five low fields and a separate exception at zero-based position 4 with high part 128; this is exact arithmetic, not a native PFOR stream or a measured compression ratio. [2]

Relations

related
Frame-of-reference encoding, Bit packing, Lossless compression

Citations

  1. Lemire and Boytsov: Decoding billions of integers per second through vectorization, sections 2.6-2.8 and 5 (accessed 2026-11-17)
  2. Hesela: frame-of-reference arithmetic and exception example (accessed 2026-11-17)
  3. Zukowski, Heman, Nes and Boncz: Super-Scalar RAM-CPU Cache Compression, ICDE 2006, sections 2.1 and 3.1 (accessed 2026-11-17)
Sources & caveats
  • Primary-source synthesis plus a bounded signed-64-bit integer illustration; no native codec benchmark, format-compatibility claim or new empirical result.

JSON: /data/terms/patched-frame-of-reference.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Patched frame-of-reference. Hesela. 2026-11-17. https://hesela.dev/terms/patched-frame-of-reference/