gmcabrita/bloomex

:hibiscus: A pure Elixir implementation of Scalable Bloom Filters

Gonçalo Mendes Cabrita — @gmcabrita

I'm a Lead Software Engineer based in Portugal.

• 🏢 Building things at Amplemarket
• 🔧 Mostly using Ruby, Rails, Redis, Postgres
• 📫 @gmcabrita

bloomex's Issues

the spec in the function scalable is inconsistent with guards

bloomex/lib/bloomex.ex

Line 117 in ede7fbf

@spec scalable(integer, number, number, 1 | 2 | 3, hash_func()) :: ScalableBloom.t()

and

bloomex/lib/bloomex.ex

Line 125 in ede7fbf

when capacity > 0 and error > 0 and error < 1 and growth > 0 and growth < 4 and

the guards of growth can't match 1 | 2 | 3.
so, we can pass a float to the function parameter growth.
maybe growth in [1, 2, 3] would be a little better.

Add more tests to reach 100% coverage

Rethink Bloom filter creation API

I'm currently dissatisfied with a subset of the API being used, most specifically:
new/2
new/3
new/5
new_plain_bloom/3

new currently denotes the creation of a Scalable Bloom filter, and new_plain_bloom the creation of a plain Bloom filter.

My current idea is to discard both new/2 and new/3, forcing the user to understand what kind of parameters he's actually using in this Bloom filter.

The function naming is also ambiguous so I'm changing that as well.

Current proposed API:
plain/2, uses the default hash function
plain/3, the user specifies everything
scalable/4, uses the default hash function
scalable/5, the user specifies everything

In the new API plain will denote a regular Bloom filter and scalable a Scalable Bloom filter.

plain bloom filter false positives

It appears that the capacity of the plain bloom filter may be calculated incorrectly. This example

bloom = Bloomex.plain(1000, 0.01)
Enum.reduce(1..1000, bloom, &Bloomex.add(&2, &1))

results in the following bloom filter struct

%Bloomex.Bloom{
  bv: [
    {:array, 1, 0, 0, {3, 0, 0, 0, 0, 0, 0, 0, 0, 0}},
    {:array, 1, 0, 0, {3, 0, 0, 0, 0, 0, 0, 0, 0, 0}},
    {:array, 1, 0, 0, {3, 0, 0, 0, 0, 0, 0, 0, 0, 0}},
    {:array, 1, 0, 0, {3, 0, 0, 0, 0, 0, 0, 0, 0, 0}},
    {:array, 1, 0, 0, {3, 0, 0, 0, 0, 0, 0, 0, 0, 0}},
    {:array, 1, 0, 0, {3, 0, 0, 0, 0, 0, 0, 0, 0, 0}},
    {:array, 1, 0, 0, {3, 0, 0, 0, 0, 0, 0, 0, 0, 0}}
  ],
  error_prob: 0.01,
  hash_func: #Function<1.7646300/1 in Bloomex.plain/2>,
  max: 1,
  mb: 1,
  size: 3
}

It appears that only 3 distinct numbers were actually added to the filter, even though it was initialized with a capacity of 1000 and a false positive rate of 1%. This configuration would be expected to hold around 990 distinct keys. It also seems wrong that the :max field is being set to 1 in this configuration.

If the above configuration is incorrect, or if I am misunderstanding the calculations for the plain filter, please let me know.