Bloomy.Counting (Bloomy v0.1.0)

View Source

Counting bloom filter implementation using Nx tensors.

A counting bloom filter extends the standard bloom filter by using counters instead of bits. This allows for deletion operations while maintaining the probabilistic properties of bloom filters.

Features

  • Supports deletion (remove operation)
  • Uses Nx tensors for counter storage
  • Configurable counter bit width
  • Overflow detection and handling
  • EXLA backend support

Trade-offs

  • Uses more memory than standard bloom filter (counters vs bits)
  • Slightly slower operations due to counter arithmetic
  • Enables deletion, which standard bloom filters cannot do

Examples

iex> # Create a counting bloom filter
iex> filter = Bloomy.Counting.new(1000, false_positive_rate: 0.01)
iex>
iex> # Add items
iex> filter = filter
iex>   |> Bloomy.Counting.add("apple")
iex>   |> Bloomy.Counting.add("banana")
iex>
iex> # Check membership
iex> Bloomy.Counting.member?(filter, "apple")
true
iex>
iex> # Remove items
iex> filter = Bloomy.Counting.remove(filter, "apple")
iex> Bloomy.Counting.member?(filter, "apple")
false

Summary

Types

t()

Functions

add(filter, item)

Add an item to the counting bloom filter.

add_all(filter, items)

Add multiple items to the counting bloom filter.

clear(filter)

Clear the counting bloom filter (reset all counters to zero).

info(filter)

Get information and statistics about the counting bloom filter.

member?(filter, item)

Check if an item might be in the counting bloom filter.

new(capacity, opts \\ [])

Create a new counting bloom filter.

remove(filter, item)

Remove an item from the counting bloom filter.

union(filter1, filter2)

Union (merge) two counting bloom filters.

Types

t()

@type t() :: %Bloomy.Counting{
  backend: atom(),
  counter_width: 8 | 16 | 32,
  counters: Nx.Tensor.t(),
  items_count: non_neg_integer(),
  params: Bloomy.Params.t()
}

Functions

add(filter, item)

Add an item to the counting bloom filter.

Increments counters at hash positions. Detects and prevents counter overflow.

Parameters

  • filter - The counting bloom filter struct
  • item - Item to add

Returns

Updated counting bloom filter struct.

Examples

iex> filter = Bloomy.Counting.new(1000)
iex> filter = Bloomy.Counting.add(filter, "hello")
iex> filter.items_count
1

add_all(filter, items)

Add multiple items to the counting bloom filter.

Parameters

  • filter - The counting bloom filter struct
  • items - List of items to add

Returns

Updated counting bloom filter struct.

Examples

iex> filter = Bloomy.Counting.new(1000)
iex> filter = Bloomy.Counting.add_all(filter, ["a", "b", "c"])
iex> filter.items_count
3

clear(filter)

Clear the counting bloom filter (reset all counters to zero).

Parameters

  • filter - The counting bloom filter struct

Returns

Cleared counting bloom filter struct.

Examples

iex> filter = Bloomy.Counting.new(1000)
iex> filter = Bloomy.Counting.add(filter, "test")
iex> filter.items_count
1
iex> filter = Bloomy.Counting.clear(filter)
iex> filter.items_count
0

info(filter)

Get information and statistics about the counting bloom filter.

Parameters

  • filter - The counting bloom filter struct

Returns

Map containing filter statistics.

Examples

iex> filter = Bloomy.Counting.new(1000)
iex> info = Bloomy.Counting.info(filter)
iex> info.type
:counting
iex> info.counter_width
8

member?(filter, item)

Check if an item might be in the counting bloom filter.

Parameters

  • filter - The counting bloom filter struct
  • item - Item to check

Returns

Boolean - true if item might be present, false if definitely not present.

Examples

iex> filter = Bloomy.Counting.new(1000)
iex> filter = Bloomy.Counting.add(filter, "hello")
iex> Bloomy.Counting.member?(filter, "hello")
true
iex> Bloomy.Counting.member?(filter, "world")
false

new(capacity, opts \\ [])

Create a new counting bloom filter.

Parameters

  • capacity - Expected number of items to store
  • opts - Keyword list of options:
    • :false_positive_rate - Desired false positive rate (default: 0.01)
    • :counter_width - Bits per counter: 8, 16, or 32 (default: 8)
    • :backend - Nx backend to use (default: Nx.default_backend())

Returns

A new Bloomy.Counting struct.

Examples

iex> filter = Bloomy.Counting.new(1000)
iex> filter.params.capacity
1000

iex> filter = Bloomy.Counting.new(1000, counter_width: 16)
iex> filter.counter_width
16

remove(filter, item)

Remove an item from the counting bloom filter.

Decrements counters at hash positions. Will not decrement below zero.

Parameters

  • filter - The counting bloom filter struct
  • item - Item to remove

Returns

Updated counting bloom filter struct.

Examples

iex> filter = Bloomy.Counting.new(1000)
iex> filter = Bloomy.Counting.add(filter, "hello")
iex> Bloomy.Counting.member?(filter, "hello")
true
iex> filter = Bloomy.Counting.remove(filter, "hello")
iex> Bloomy.Counting.member?(filter, "hello")
false

union(filter1, filter2)

Union (merge) two counting bloom filters.

Takes the maximum counter value at each position.

Parameters

  • filter1 - First counting bloom filter
  • filter2 - Second counting bloom filter

Returns

New counting bloom filter containing union.

Examples

iex> f1 = Bloomy.Counting.new(1000) |> Bloomy.Counting.add("a")
iex> f2 = Bloomy.Counting.new(1000) |> Bloomy.Counting.add("b")
iex> f_union = Bloomy.Counting.union(f1, f2)
iex> Bloomy.Counting.member?(f_union, "a") and Bloomy.Counting.member?(f_union, "b")
true