Crate newpfd

Crate implementing NewPFD (a variant of PForDelta, aka Patched Frame Of Reference Delta) compression of integers.

See Inverted index compression and query processing with optimized document ordering for the original publication.

Overview

The algorithm splits the intput data (u64) into blocks of size blocksize. For each block, choose a bit_width, such that 90% of the block elements can be encoded using bit_width. Those elements can be stored in the primary buffer. For elements that don’t fit, store the lower bit_width bits in the primary buffer, encode and store the excess bits separately (Fibonacci encoding)

Note

• The decoder is written in such a way that it doesn’t consume the compressed data. Rather it takes a refence to it, reads in the specific amount of elements and returns the number of bits processed. This allows for complex formats where NewPFD is only a small part, and after the NewPFD section, theres other data that has to be processed differently. In particular, after calling let (decompressed_data, bits_processed) = decode(&compressed_data, data.len(), blocksize); you can get hold of the remaining bitstream via compressed_data[bits_processed..]

• This compression does not use delta compression internally. If you need that, apply it before feeding the data into encode().

• There’s multiple decoders (all equivalent, but different performance): decode uses regular Fibonacci decoding (for the exceptions), decode_fast_u8 and decode_fast_u16 use FastFibonacci decoding, which in theory should be faster (2x). However, Fibonacci decoding is not the bottleneck of NewPFD, and FastFibonacci doesn’t have much gain.

Example

// Encode some data using NewPFD
let data = vec![10_u64,12,10,1,1,2,3];
let blocksize = 32; // needs to be a mutliple of 32
// encode
let (compressed_data, _) = encode(data.iter().cloned(), blocksize);
// compressed_data is a `bitvec::BitVec` (similar to a Vec<bool>)
 
// decode
let (decompressed_data, bits_processed) = decode(&compressed_data, data.len(), blocksize);
assert_eq!(data, decompressed_data);
assert_eq!(compressed_data.len(), bits_processed); // the entire bitstream was consumed

Memory layout of a NewPFD block:

Header:

• fib([b_bits, min_element, #exceptions])
• Exceptions
• exception indices (delta encoded)

Body:

• |b_bits|b_bits|b_bits|b_bits|b_bits|b_bits|...|

Performance

The library is currently NOT optimized for performance! I’m using some code from the fastfibonacci crate to have efficient encoding/decoding of int-streams.

However, here’s what we get in terms of encoding and decoding 1Mio 1byte integers (0..255):

mean +/- std
Encoding: [87.819 ms 88.334 ms 88.882 ms]
Decoding: [15.956 ms 16.057 ms 16.199 ms]

Decoding seems to be vastly faster!

Re-exports

• pub use newpfd_bitvec::encode;
• pub use newpfd_bitvec::decode;
• pub use newpfd_bitvec::decode_fast_u8;
• pub use newpfd_bitvec::decode_fast_u16;

Modules

• newpfd_bitvec
  NewPFD with bitvec backend (instead of the old, bit_vec crate)
• newpfd_u32
  Same as crate::newpfd_bitvec, but instead of using the bitvec backend lets work directly with a bytestream (coming from a stream of u32, as in bustools)