Opaque C struct, managed by a ForeignPtr with a destructor. The entire sketch lives in C-allocated memory: no GC pressure, no monadic bind overhead, no dictionary passing.
Moduledata-sketches-0.4.0.1Haskell2010
DataSketches.Quantiles.KLL
KLL (Karnin-Lang-Liberty) sketch for approximate quantile computation with additive error bounds. Based on "Optimal Quantile Approximation in Streams" (Karnin, Lang, Liberty — FOCS 2016).
Feed it a stream of numbers, then ask questions like "what's the median?" or "what value is at the 99th percentile?" — without storing every value. The sketch keeps a small, fixed-size buffer regardless of how many items you insert.
KLL provides uniform additive error across all ranks. With k = 200,
the normalized rank error is approximately 1.33% with 99% confidence,
regardless of whether you query p50 or p99.
This is the recommended quantile sketch for most use cases. Prefer DataSketches.Quantiles.RelativeErrorQuantile only when you need high accuracy specifically at the distribution tails (p99.9+).
Implementation
Backed by a C implementation (cbits/kll.c) behind a ForeignPtr.
All sketch memory lives outside the GHC heap — zero GC pressure,
zero boxing overhead.
Usage
import qualified DataSketches.Quantiles.KLL as KLL
main :: IO ()
main = do
sk <- KLL.mkKllSketch 200
mapM_ (KLL.insert sk) [1..100000 :: Double]
p99 <- KLL.quantile sk 0.99
putStrLn $ "p99 = " ++ show p99
Mergeability
Fully mergeable: merge combines two sketches as if all data had been inserted into one. Suitable for parallel and distributed computation.
- 1 type
- 15 values
- Packagedata-sketches-0.4.0.1
- Exports16
- LanguageHaskell2010
- LicenceLicenseRef-Apache
- SourceKLL.hs
Construction
2 declarationsUpdating the sketch
3 declarationsCreate a new KLL sketch with the given accuracy parameter k. Larger k gives better accuracy but uses more space. k must be >= 8. Default recommendation is 200.
Insert a value into the sketch. NaN values are ignored.
Bulk-insert a storable vector of doubles. Avoids per-element FFI overhead.
Merge the second sketch into the first.
Querying
11 declarationsTotal number of items inserted.
True if no items have been inserted.
Smallest value seen.
Largest value seen.
Number of items currently retained in the sketch.
Get the approximate quantile for the given normalized rank in [0, 1].
Get approximate quantiles for multiple normalized ranks.
Get the approximate normalized rank of a value.
Get approximate normalized ranks for multiple values.
Approximate cumulative distribution function. Given a list of split points, returns a list of cumulative probabilities. Returns Nothing if the sketch is empty.
Approximate probability mass function. Given a list of split points, returns probabilities for each interval. Returns empty list if the sketch is empty.