Lua Count-min Sketch Module

1. Overview

Calculates the frequency of an item in a stream. The module is globally registered and returned by the require function.

2. Example Usage

require "streaming_algorithms.cm_sketch"
local cms = streaming_algorithms.cm_sketch.new(0.01, 0.01)
for i = 1, 100 do
    cms:update(i)
end
local cnt = cms:point_query(1)
-- cnt == 1

3. Module

3.1. Functions

3.1.1. new

local cm_sketch = require "streaming_algorithms.cm_sketch"
local cms = cm_sketch.new(0.01, 0.01)

Creates a new cm_sketch userdata object.

Arguments

• epsilon (number) approximation factor
• delta (number) probability of failure

Return

• cm_sketch userdata object

3.2. Methods

3.2.1. update

local estimate = cms:update("foo")

Update the count for the specified item in the sketch.

Arguments

• key (string/number) item identifier
• n (number/nil/none) number of items (default 1), a negative value removes items

Return

• estimate (integer) estimated frequency count

3.2.2. point_query

local estimate = cms:point_query("foo")

Retruns the frequency for the specified item in the sketch.

Arguments

• key (string/number) item identifier

Return

• estimate (integer) estimated frequency count

3.2.3. clear

cms:clear()

Resets the count-min sketch.

Arguments

• none

Return

• none

3.2.4. item_count

local count = cms:item_count()

Returns the total number items in the sketch.

Arguments

• none

Return

• count (number)

3.2.5. unique_count

local count = cms:unique_count()

Returns the total number unique items in the sketch.

Arguments

• none

Return

• count (number)

3.2.6. fromstring

cms1:fromstring(tostring(cms))

Restores the sketch to the previously serialized state (must have a compatible epsilon and delta).

Arguments

• serialization (string) tostring output

Return

• none or throws an error