compressed_map v0.1.0

\[ crates.io | docs.rs | github \]

Hello Rustaceans, I'd like to announce my first crate, a project I've been messing around with off-and-on for a couple of years: compressed_map. I've mostly been building this in C, but I decided to port it to Rust as a way to learn the language. Instead it now exposes a C FFI, but this is currently less stable than the Rust API.

This crate is designed to compress maps where the key space is very large and sparse, and the value space is small. The motivating example is certificate revocation, where you want to compress a map of {all certs issued by some CA in a given time window} -> {still valid, revoked}. It works somewhat similarly to a HashMap, but it discards the keys of the map and instead stores only the distribution of values, and just enough information to evaluate the mapping.

Lookups can be done without decompressing the map, and are almost as fast as looking up in a regular hash table.

As a result of discarding the keys, the compressed form might be hundreds of times smaller than the corresponding HashMap, achieving nearly the minimum size given the information content of the values. But you can't list out the keys, and you can't even tell if a given key is in the map or not. Looking up a key that was in the original map always gives the right answer. Looking up a key that wasn’t in in the map gives an arbitrary (safe) answer instead of failure. In the motivating example and in certain other cases this is fine, because you won't ask for the revocation status of a cert that wasn't issued. Also, unsurprisingly since the compression is lossy, you can't update the compressed map: you have to make a new one. All of this means that the crate is only useful in a certain niche, but within that niche it's quite powerful.

Internally, the encoding is done, roughly, by creating a matrix M such that M(to_sparse_vector(hash(key))) = value for all (key,value) pairs in the map. It solves for M using a new high-speed GF(2) linear algebra platform that maybe should eventually be its own crate, but currently only exposes enough functionality for this one use case. It scales to hundreds of millions of keys, or if the values have particularly low entropy, to billions of keys or more. This is mainly limited by memory usage during compression.

Please let me know if this is useful, and/or if I've committed any severe newbie sins.