prob/cms
CountMin
(defstruct CountMin [counters : (Vec int) d : int w : int])
a Count-Min Sketch with d rows and w columns.
Since: probabilistic-spice-plan C1
cms-d
(cms-d [^borrow c : CountMin] :)
the depth (number of rows).
| c | the sketch |
d, the number of hash functions / rows.
Since: probabilistic-spice-plan C1
cms-w
(cms-w [^borrow c : CountMin] :)
the width (columns per row).
| c | the sketch |
w, the number of columns per row.
Since: probabilistic-spice-plan C1
cms-new
(cms-new [d : int w : int] :)
create a Count-Min Sketch with d rows and w columns.
| d | depth (number of rows / hash functions) | |
| w | width (columns per row; should be a power of two) |
A new sketch with all counters zero.
(let [c (cms-new 5 1024)] ...)
Since: probabilistic-spice-plan C1
cms-free
(cms-free [c : CountMin] :)
release the counter array.
| c | the sketch to free |
Since: probabilistic-spice-plan C1
cms-add!
(cms-add! [^borrow c : CountMin key : int] :)
record one occurrence of an element.
| c | the sketch (mutated in place) | |
| key | the integer key to add |
nil
Since: probabilistic-spice-plan C1
cms-estimate
(cms-estimate [^borrow c : CountMin key : int] :)
the estimated frequency of an element.
| c | the sketch | |
| key | the integer key to estimate |
The minimum counter value over all d rows. Always >= the true frequency; never under-counts.
Since: probabilistic-spice-plan C1
cms-merge
(cms-merge [^borrow a : CountMin ^borrow b : CountMin] :)
pointwise addition of two sketches.
| a | first sketch | |
| b | second sketch (must have the same d and w) |
A new CountMin whose counters are a[i] + b[i]. Both inputs remain valid.
Since: probabilistic-spice-plan C1
cms-inner-product
(cms-inner-product [^borrow a : CountMin ^borrow b : CountMin] :)
estimate the inner product of two streams' frequencies.
| a | first sketch | |
| b | second sketch (must have the same d and w) |
The min over d rows of the dot product of corresponding rows. Estimates the size of the join of the two streams.
Since: probabilistic-spice-plan C1
Internal definitions
__cms-init-- internal: push n zeros into the counter Vec.__cms-add-loop-- internal: increment d counters for this element.__cms-est-loop-- internal: min over d rows of the counter for this element.__cms-merge-loop-- internal: pointwise addition of counters.__cms-dot-loop-- internal: dot product of one row of a and b.__cms-ip-loop-- internal: min over d rows of the dot product.__cms-eq-loop-- internal: are all counters equal?Eq[CountMin]-- same d, w, and all counters equal.default-cms-d-- default depth for bottom.default-cms-w-- default width for bottom.JoinSemilattice[CountMin]-- join is pointwise addition.BoundedJoin[CountMin]-- the all-zero sketch of default size is bottom.