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.
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
Citations
- Lemire and Boytsov: Decoding billions of integers per second through vectorization, sections 2.6-2.8 and 5
- Hesela: frame-of-reference arithmetic and exception example
- Zukowski, Heman, Nes and Boncz: Super-Scalar RAM-CPU Cache Compression, ICDE 2006, sections 2.1 and 3.1
Sources & caveats
- Primary-source synthesis plus a bounded signed-64-bit integer illustration; no native codec benchmark, format-compatibility claim or new empirical result.