Talán

Probabilistic data structures for Elixir, backed by Erlang's :atomics:

• Talan.BloomFilter — membership and cardinality estimation
• Talan.CountingBloomFilter — membership, frequency, and cardinality estimation with deletion
• Talan.LinearCounter — cardinality estimation
• Talan.Stream.uniq/2 — bounded-memory stream deduplication

The data structures are mutable and support concurrent access. See the documentation for API details and concurrency semantics.

Installation

Talan requires Elixir 1.14 and OTP 25 or later.

def deps do
  [
    {:talan, "~> 1.0"}
  ]
end

Examples

Bloom filter

filter = Talan.BloomFilter.new(1_000)
:ok = Talan.BloomFilter.put(filter, "Barna")
true = Talan.BloomFilter.member?(filter, "Barna")

Counting Bloom filter

filter = Talan.CountingBloomFilter.new(1_000)
:ok = Talan.CountingBloomFilter.put(filter, "hat")
:ok = Talan.CountingBloomFilter.put(filter, "hat")
2 = Talan.CountingBloomFilter.count(filter, "hat")
:ok = Talan.CountingBloomFilter.delete(filter, "hat")
1 = Talan.CountingBloomFilter.count(filter, "hat")

put/2 and delete/2 return {:error, :value_out_of_bounds} when a packed counter would overflow or underflow.

Linear counter

counter = Talan.LinearCounter.new(10_000)
:ok = Talan.LinearCounter.put(counter, "Barna")
1 = Talan.LinearCounter.cardinality(counter)

Stream deduplication

filter = Talan.BloomFilter.new(10_000, hash_functions: [fn value -> value end])

[1, 2, 3] =
  [1, 2, 1, 3]
  |> Talan.Stream.uniq(filter)
  |> Enum.to_list()

Bloom filter false positives can cause Talan.Stream.uniq/2 to reject unique values. The function mutates its filter, so re-enumerating the stream can produce different results.

License

MIT