HLL

v0.1.1

HLL v0.1.1 HLL View Source

Default HyperLogLog module.

Note that this module is not Redis compatible. Use alternative HLL.Redis module if you need to interact with Redis and need it to be Redis compatible.

This module uses :erlang.phash2 as hash function.

Example 

iex> hll = HLL.new(14)
iex> hll = Enum.reduce(1..2000, hll, fn i, acc -> HLL.add(acc, i) end)
iex> HLL.cardinality(hll)
1998

Serialization

It has two representations, sparse (space-efficient for low cardinality) and dense (space-efficient for high cardinality). When encode HyperLogLog with HLL.encode, this module would automatically choose the representation with smaller encoded size.

# sparse representation:
<<0::4, (p - 8)::4, index0::p, count0::6, index1::p, count1::6 ..., padding::xx>>

# dense representation:
<<1::4, (p - 8)::4, count0::6, count1::6, count2::6 ...>>

Link to this section Summary

Types

t()

Functions

add(hll, item)

Add a value to HyperLogLog instance

cardinality(hll)

Estimate cardinality of HyperLogLog instance

decode(hll_binary)

Decode HLL binary format to HyperLogLog instance

encode(hll)

Encode HyperLogLog instance to HLL binary format

merge(list_of_hll)

Merge multiple HyperLogLog instances into one

new(p)

Create a HyperLogLog instance with specified precision in range from 8 to 16

Link to this section Types

Link to this type

t() View Source 
t() :: {HLL, 8..16, map()}

Link to this section Functions

Link to this function

add(hll, item) View Source 
add(t(), any()) :: t()

Add a value to HyperLogLog instance.

Example 

iex> h = HLL.new(12)
{HLL, 12, %{}}
iex> HLL.add(h, "hello")
{HLL, 12, %{1581 => 2}}
Link to this function

cardinality(hll) View Source 
cardinality(t()) :: non_neg_integer()

Estimate cardinality of HyperLogLog instance.

Example 

iex> h = HLL.new(14)
iex> HLL.cardinality(h)
0
iex> h = HLL.add(h, "foo")
iex> HLL.cardinality(h)
1
iex> h = HLL.add(h, "bar")
iex> HLL.cardinality(h)
2
Link to this function

decode(hll_binary) View Source 
decode(binary()) :: t()

Decode HLL binary format to HyperLogLog instance.

Example 

iex> h = HLL.new(14) |> HLL.add("foo")
{HLL, 14, %{617 => 1}}
iex> encoded = HLL.encode(h)
<<6, 9, 164, 16>>
iex> HLL.decode(encoded)
{HLL, 14, %{617 => 1}}
Link to this function

encode(hll) View Source 
encode(t()) :: binary()

Encode HyperLogLog instance to HLL binary format.

Example 

iex> HLL.new(14) |> HLL.encode()
<<6>>
iex> HLL.new(14) |> HLL.add("foo") |> HLL.encode()
<<6, 9, 164, 16>>
iex> HLL.new(14) |> HLL.add("foo") |> HLL.add("bar") |> HLL.encode()
<<6, 9, 164, 16, 219, 129, 0>>
Link to this function

merge(list_of_hll) View Source 
merge([t()]) :: t()

Merge multiple HyperLogLog instances into one.

Example 

iex> h1 = HLL.new(12) |> HLL.add("foo")
iex> h2 = HLL.new(12) |> HLL.add("bar")
iex> h3 = HLL.new(12) |> HLL.add("foo") |> HLL.add("bar")
iex> h_merged = HLL.merge([h1, h2])
iex> h3 == h_merged
true
Link to this function

new(p) View Source 
new(8..16) :: t()

Create a HyperLogLog instance with specified precision in range from 8 to 16.

Example 

iex> HLL.new(12)
{HLL, 12, %{}}
iex> HLL.new(14)
{HLL, 14, %{}}