Crate bloom2

bloom2 implements a 2-level bitmap to provide a sparse, lazily initialised, high performance bloom filter with a reduced memory footprint.

The memory usage of a sparse bloom filter grows proportionally with the load factor of the filter, resulting in substantially smaller memory footprints for filters with average, or low load factors. As bloom filters are typically sized to avoid high load factors in order to minimise false positives, this is highly effective for the typical use case.

The Bloom2 filter provides amortised O(1) insert, and constant time O(1) lookup with a similar average case latency compared to a standard bloom filter (~30ns on a Core i7 @ 2.60GHz, with a majority of this taken up by the hashing of values).

The sparse memory behaviour is implemented in the underlying CompressedBitmap, which is used as the bit storage for the filter. The CompressedBitmap is a fast (~4ns set, 1ns get) space efficient general-purpose bitmap suitable for use in applications in addition to the bloom filter.

Features

• serde - enable serialisation with serde, disabled by default

Structs

• Bloom2
  A fast, memory efficient, sparse bloom filter.
• BloomFilterBuilder
  Construct Bloom2 instances with varying parameters.
• CompressedBitmap
  A sparse, 2-level bitmap with a low memory footprint.

Enums

• FilterSize
  FilterSize bounds the allocated size and false-positive rate of a Bloom2 instance.

Traits

• Bitmap
  A trait to abstract bit storage for use in a Bloom2 filter.