Quantile Compression
This rust library compresses and decompresses sequences of numerical data very well. It currently supports the following data types: i32, i64, u32, u64, f32, f64. Smaller data types like i16 can be efficiently compressed by casting to i32. Timestamp support may come soon in the future.
For natural data, it typically shrinks data to 25-40% smaller than what gzip -9 produces, compresses much faster, and decompresses equally quickly.
The intended use case for this algorithm is compressing columnar data, especially for use by Spark and other execution engines.
This IS:
- lossless
- order-preserving
- moderately fast
This is NOT:
- lossy
- for multisets
- optimal for time series with high mutual information between consecutive elements
Usage
See the following basic usage. To run something right away, see the example.
use q_compress:{BitReader, I64Compressor, I64Decompressor};
fn main() {
// your data
let mut my_ints = Vec::new();
for i in 0..100000 {
my_ints.push(i as i64);
}
// compress
// max_depth is basically compression level - 6 is generally good.
// Max depths between 4 and 8 are reasonable.
let max_depth = 6;
let compressor = I64Compressor::train(&my_ints, max_depth).expect("failed to train");
let bytes = compressor.compress(&my_ints).expect("out of range");
println!("compressed down to {} bytes", bytes.len());
// decompress
let bit_reader = &mut BitReader::from(bytes);
let decompressor = I64Decompressor::from_reader(bit_reader).expect("couldn't read compression scheme");
let recovered = decompressor.decompress(bit_reader);
println!("got back {} ints from {} to {}", recovered.len(), recovered[0], recovered.last().unwrap());
}
Method
This works by describing each number with a range and an offset. The range specifies an inclusive range [lower, upper] that the number might be in, and the offset specifies the exact position within that range. The compressor chooses a prefix for each range via Huffman codes.
For data sampled from a random distribution, this compression algorithm can reduce byte size to near the theoretical limit of the distribution's Shannon entropy. Ideally it encodes a number k in b bits if 2^-b ~= P(k). We can plot Q(k) = 2^-b to see how close quantile compression gets to the ideal in this example with max_depth=3:
The inefficiency of quantile compression in bits per number is the KL divergence from the approximated distribution Q to the true distribution P.
.qco File Format
Quantile-compressed files consist of a lightweight header (usually <1KB) and then very many short number blocks, each of which usually encodes a single number.
The header is expected to start with a magic sequence of 4 bytes for "qco!" in ascii. The next byte encodes the data type (e.g. i64). The next few bytes encode the count of numbers in the file, and then the count of ranges (or prefixes) used to compress. It then contains metadata for each range: lower and upper bound, the length of its prefix in bits, the prefix. The next bit for each range encodes whether it uses repetitions, which are only used for the most common range in a sparse distribution. If so, the file then encodes a "jumpstart", which is used in number blocks to describe how many repetitions of the range to use.
Each number block has just 2 or 3 parts. First comes the prefix, which indicates a range to use. If that range uses repetitions, a varint for the exact number of repetitions follows, leveraging the jumpstart from earlier. Then an offset (for each repetition if necessary) follows, specifying the exact value within the range.
162 Dec 24, 2022
9 May 22, 2023
59 Oct 7, 2022
56 Nov 24, 2022
619 Jan 8, 2023
232 Jan 2, 2023
0 Dec 16, 2021
2 Jan 5, 2022
1 Feb 2, 2022
734 Dec 30, 2022
659 Dec 29, 2022
3 Aug 17, 2022
294 Dec 23, 2022
172 Oct 31, 2022
27 Jan 3, 2023
62 Nov 29, 2022
1.8k Dec 28, 2022
4 Oct 15, 2022
7 Dec 14, 2022
11 Jan 23, 2023