Sketches have always struck me as kinda magic.
With an infinite time-series of data, we usually keep a window: the last 20 bars, the last 1,000 ticks, the last five minutes. Then recompute whatever statistic you want over the window. This is fine until you have thousands of symbols, long lookbacks, or tight loops where sorting is expensive.
A lot of statistics don’t require a window. You can reduce a stream to a small state, update that state when a new observation arrives, and throw the observation away. This is what skream does. It’s a Clojure library for streaming statistics I wrote a while back.
Exponential Mean and Variance
A simple moving average remembers everything in its window and then forgets the oldest observation. In an exponential average, old observations decay instead of vanishing.
The important parameter is the half-life: how many observations until an observation is worth half as much? If the half-life is h, then alpha = 1 - 0.5^(1/h). skream takes alpha directly. The state is just the current EMA plus a count.
(require '[skream.core :as sk])
(def s
(-> (sk/create-skream)
(sk/track-exponential-moving-average 0.05)))
(def s
(reduce sk/add-num s returns))
(get s [:ema 0.05])
The default alpha is 0.125. Keep one Skream per instrument and update it on every return. Variance is a separate tracker:
(def s
(-> (sk/create-skream)
sk/track-variance
sk/track-standard-deviation))
(def s
(reduce sk/add-num s returns))
(:var s)
(:stdev s)
Three numbers per instrument cheaper than keeping the history around. See also the infamous infinite-memory issue in Pandas. And skream has the usual cumulative mean, higher moments, skewness, and kurtosis stats too.
Quantiles Without a Window
The P² algorithm, from Jain and Chlamtac, estimates a quantile using five markers. The markers track the minimum, maximum, desired quantile, and two points around it. New observations update their positions. When the markers get out of place, their heights are adjusted using parabolic interpolation. The amount of state doesn’t grow with the number of observations.
The skream version is straightforward:
(def s
(-> (sk/create-skream)
(sk/track-quantile-ish 0.95)))
(def s
(reduce sk/add-num s prices))
(get s [:quantile 0.95])
For the median, there is a convenience function:
(def s
(-> (sk/create-skream)
sk/track-median-ish))
(def s
(reduce sk/add-num s prices))
(:median s)
After 25 SPY closes, skream produces roughly:
{:quantile 193.72229
:qs [187.55 191.74467 193.72229 195.5992 196.48]
:ns [1 7 13 19 25]}
:qs are the marker heights. :ns are their positions. The middle marker is the median.
There are two catches. P² estimates one quantile, so if you want the 5th, 50th, and 95th percentiles, you run three estimators. More importantly, P² isn’t mergeable. If you have a cluster processing different pieces of a feed and want one global quantile, P² is the wrong tool. Use KLL, t-digest, or another mergeable sketch.
Count Things Without Counting Everything
A Count-Min sketch is a small array of counters plus a few hash functions. Each key increments one counter in each row. To estimate the count, take the minimum across the rows. It can only overestimate. With width w = e/ε and depth d = ln(1/δ), the error is bounded by εN with probability 1−δ.
skream calls this track-element-counts-ish:
(def s
(-> (sk/create-skream)
(sk/track-element-counts-ish 256 128)))
(def s
(reduce sk/add-num s symbols))
(sk/get-element-count-ish s "AAPL")
This is useful when the alternative is keeping a giant hash table around just to discover that one symbol generated an unusually large number of messages.
HyperLogLog estimates cardinality: how many distinct things have I seen? Unique order IDs, unique symbols, unique clients, whatever. With m registers, the standard error is approximately 1.04 / sqrt(m). Sixteen thousand registers gets you roughly 0.8% error while consuming about 12 KB.
In skream, the number of registers is 2^b, so 14 bits gives 16,384 registers:
(def s
(-> (sk/create-skream)
(sk/track-distinct-value-count-ish 14)))
(def s
(reduce sk/add-num s order-ids))
(get s [:hll 14])
The exact answer might require millions of IDs. The approximate answer requires 16,384 registers.
A Bloom filter answers one question: have I seen this before? It has false positives but no false negatives. That makes it useful for feed replay and deduplication. If it says “no,” you haven’t seen the message. If it says “yes,” maybe you have.
skream uses multiple SHA-1-derived hashes for this:
(def s
(-> (sk/create-skream)
(sk/track-member-ish? 6 8)))
(def s
(reduce sk/add-num s message-ids))
(sk/member-ish? s message-id)
The 6 is the number of bits used for each hash bucket and 8 is the number of hash functions. Again, fixed memory, but an arbitrarily long stream.
Feature Hashing
Feature hashing is another sketch, although it usually gets presented as a machine-learning trick rather than a streaming data structure. Suppose you have a stream of sparse categorical features: symbols, venues, order types, words, whatever. Instead of growing a dictionary from feature names to columns, hash each feature into one of m buckets and keep only the resulting vector: feature → hash → bucket → update.
If two features land in the same bucket, they share share a model parameter or set of weights. With signed hashing, a second independent hash assigns each feature either +1 or -1, so a collision either adds or subtracts their contributions. This is useful because collisions do not systematically inflate a bucket: over many collisions, the random signs make the cross-terms tend to cancel, mostly preserving inner products. The parameter tying also reduces the model’s degrees of freedom, so collisions can act as regularization. The two effects are distinct: the random sign controls the distortion caused by collisions; the shared parameter constrains the model.
This is the same trick as the other sketches here: throw away information deliberately so the state stays bounded. Feature hashing just makes the trade particularly obvious. You’re compressing an unbounded feature space while constraining the model at the same time.
Mutual Information
Correlation is easy but less useful when the relationship is nonlinear. Mutual information can find nonlinear dependence. A simple streaming approximation is to keep fixed histograms of (x, y) and their marginals, then calculate Σ p(x,y) log(p(x,y) / (p(x)p(y))) when you want the answer.
skream does this with multiple Skreams: build a histogram for each series, a co-histogram for the pair, and then track the mutual information between them.
(def ms
(sk/create-multi-skream))
(def ms
(-> ms
(sk/assoc-multi-skream :x (sk/create-skream))
(sk/assoc-multi-skream :y (sk/create-skream))
(sk/track-multi-mutual-information :x :y -5.0 5.0 32)))
(def ms
(reduce (fn [ms [x y]]
(sk/add-multi-num ms :x x :y y))
ms
observations))
Mutual information estimates are sensitive to binning and biased when there are not enough observations per bin. Change the bins and you can change the answer, so use it to rank things worth investigating.
Wrapup
Prices are discrete. P² interpolation can produce values between ticks. That’s mathematically cute but buggy.
Histogram methods have their own problem: they depend on the bins. skream has Gaussian-spaced bins, which are useful when you want more resolution around the center of the distribution.
So why bother? Because most streaming systems don’t need the data. They need a statistic about the data. Keeping every observation is often just an indirect way of calculating that statistic later, at considerably greater expense.
A fixed-memory estimator turns data → storage → sorting → calculation into data → update → discard. The second version is generally cheaper, faster, and much harder to accidentally turn into a memory leak.
skream contains the usual collection: moments, variance, skewness, kurtosis, EMA, P² quantiles, Bloom filters, Count-Min, HyperLogLog, histograms, and histogram mutual information. Everything is fixed-memory except the simple moving average, because a simple moving average is definitionally a moving window.


