Talan.CountingBloomFilter (talan v1.0.0)

Copy Markdown View Source

Counting Bloom filter implementation with safe concurrent access, powered by the :atomics module.

Features

  • Fixed-size Counting Bloom filter
  • Concurrent reads and writes
  • Custom and default hash functions
  • Estimate number of unique elements
  • Estimate false positive probability

Counting bloom filters support probabilistic deletion of elements but have higher memory consumption because they need to store a counter of N bits for every Bloom filter bit.

Counters are the source of truth for membership. Updates to individual counters are atomic, but reads concurrent with writes may observe an operation in progress.

Summary

Types

counters_bit_size()
option()
options()
t()
update_result()

Functions

cardinality(counting_bloom_filter)

See Talan.BloomFilter.cardinality/1 for docs.

clear(counting_bloom_filter)

Clears every counter in counting_bloom_filter and returns the same filter.

count(counting_bloom_filter, term)

Returns the estimated net frequency of term after insertions and deletions. The estimate is the minimum of the counters selected by the term's hashes. Hash collisions and deletions can distort it.

delete(counting_bloom_filter, term)

Probabilistically deletes term from bloom_filter and decrements counters in counter.

false_positive_probability(counting_bloom_filter)

See Talan.BloomFilter.false_positive_probability/1 for docs.

member?(counting_bloom_filter, term)

See Talan.BloomFilter.member?/2 for docs.

new(cardinality, options \\ [])

Returns a new %Talan.CountingBloomFilter{} struct.

put(counting_bloom_filter, term)

Puts term into the filter by incrementing its counters.

Types

counters_bit_size()

@type counters_bit_size() :: 2 | 4 | 8 | 16 | 32

option()

@type option() ::
  {:counters_bit_size, counters_bit_size()}
  | {:signed, boolean()}
  | {:false_positive_probability, float()}
  | {:hash_functions, [Talan.hash_function()]}

options()

@type options() :: [option()]

t()

@type t() :: %Talan.CountingBloomFilter{
  counter: Abit.Counter.t(),
  filter_length: pos_integer(),
  hash_functions: [Talan.hash_function(), ...]
}

update_result()

@type update_result() :: :ok | {:error, :value_out_of_bounds}

Functions

cardinality(counting_bloom_filter)

@spec cardinality(t()) :: non_neg_integer()

See Talan.BloomFilter.cardinality/1 for docs.

Examples

iex> cbf = Talan.CountingBloomFilter.new(10_000)
iex> cbf |> Talan.CountingBloomFilter.put("hat")
iex> cbf |> Talan.CountingBloomFilter.put("hat")
iex> cbf |> Talan.CountingBloomFilter.put("hat")
iex> cbf |> Talan.CountingBloomFilter.put("car keys")
iex> cbf |> Talan.CountingBloomFilter.cardinality()
2

clear(counting_bloom_filter)

@spec clear(t()) :: t()

Clears every counter in counting_bloom_filter and returns the same filter.

The filter is reset in place without reallocating its packed counter storage. Clearing individual atomic words is safe during concurrent access, but the filter is not cleared as one atomic operation. Concurrent reads may observe a partially cleared filter, and concurrent updates may be cleared or remain visible depending on their timing.

Examples

iex> cbf = Talan.CountingBloomFilter.new(1000)
iex> Talan.CountingBloomFilter.put(cbf, "hat")
iex> Talan.CountingBloomFilter.clear(cbf) == cbf
true
iex> Talan.CountingBloomFilter.count(cbf, "hat")
0

count(counting_bloom_filter, term)

@spec count(t(), any()) :: integer()

Returns the estimated net frequency of term after insertions and deletions. The estimate is the minimum of the counters selected by the term's hashes. Hash collisions and deletions can distort it.

Examples

iex> cbf = Talan.CountingBloomFilter.new(10_000)
iex> cbf |> Talan.CountingBloomFilter.put("hat")
iex> cbf |> Talan.CountingBloomFilter.put("hat")
iex> cbf |> Talan.CountingBloomFilter.put("hat")
iex> cbf |> Talan.CountingBloomFilter.count("hat")
3

delete(counting_bloom_filter, term)

@spec delete(t(), any()) :: update_result()

Probabilistically deletes term from bloom_filter and decrements counters in counter.

Returns :ok, or {:error, :value_out_of_bounds} if an affected counter is already at its minimum value. Updates to other affected counters may already have succeeded because the operation is not atomic across counters.

Examples

iex> cbf = Talan.CountingBloomFilter.new(10_000)
iex> cbf |> Talan.CountingBloomFilter.put("hat")
iex> cbf |> Talan.CountingBloomFilter.count("hat")
1
iex> cbf |> Talan.CountingBloomFilter.delete("hat")
:ok
iex> cbf |> Talan.CountingBloomFilter.count("hat")
0
iex> cbf |> Talan.CountingBloomFilter.delete("this wasn't there")
iex> cbf |> Talan.CountingBloomFilter.count("this wasn't there")
-1

false_positive_probability(counting_bloom_filter)

@spec false_positive_probability(t()) :: float()

See Talan.BloomFilter.false_positive_probability/1 for docs.

member?(counting_bloom_filter, term)

@spec member?(t(), any()) :: boolean()

See Talan.BloomFilter.member?/2 for docs.

Examples

iex> cbf = Talan.CountingBloomFilter.new(10_000)
iex> cbf |> Talan.CountingBloomFilter.put("hat")
iex> cbf |> Talan.CountingBloomFilter.member?("hat")
true

new(cardinality, options \\ [])

@spec new(pos_integer(), options()) :: t()

Returns a new %Talan.CountingBloomFilter{} struct.

cardinality is the expected number of unique items. Duplicate items do not count toward the expected cardinality.

Raises ArgumentError if cardinality or any option is invalid.

Options

  • :counters_bit_size - bit size of counters, defaults to 8
  • :signed - whether counters are signed, defaults to true
  • :false_positive_probability - a float, defaults to 0.01
  • :hash_functions - a list of functions that each accept a term and return a non-negative integer, defaults to randomly seeded Murmur

Examples

iex> cbf = Talan.CountingBloomFilter.new(10_000)
iex> cbf |> Talan.CountingBloomFilter.put("hat")
iex> cbf |> Talan.CountingBloomFilter.put("hat")
iex> cbf |> Talan.CountingBloomFilter.put("phone")
:ok
iex> cbf |> Talan.CountingBloomFilter.count("hat")
2
iex> cbf |> Talan.CountingBloomFilter.count("phone")
1

put(counting_bloom_filter, term)

@spec put(t(), any()) :: update_result()

Puts term into the filter by incrementing its counters.

A successful insertion increments every counter selected by the term's hashes. Membership is true only while all selected counters are positive, so earlier deletions can keep it false.

Returns :ok, or {:error, :value_out_of_bounds} if an affected counter is already at its maximum value. Updates to other affected counters may already have succeeded because the operation is not atomic across counters.

Examples

iex> cbf = Talan.CountingBloomFilter.new(10_000)
iex> cbf |> Talan.CountingBloomFilter.put("hat")
:ok