Golomb Compressed Sets
Simple implementation of the Golomb Compressed Sets (GCS), a statistical
compressed data-structure. It is similar to Bloom filters, but it is far more
compact: given N elements, and P probability of a false positive, an optimal
Bloom filter requires at least N*log2(e)*log2(1/P) bits, where GCS gets the
bar closer to theoretical minimum of N*log2(1/P). With real-world data sets,
GCS can be 20-30% more compact than a Bloom filter.
Fri 02 Nov 2012 08:40:22 AM CET - permalink -
-
https://github.com/rasky/gcs