Quantile Estimator
Commmon Library collecting multiple quantile algorithms for streaming data, concurrent & easy to use.
Implemented in java/dotnet separately. Code is clean. Easy to read.
Usage
-
java https://github.com/mydotey/quantile-estimator/tree/master/java
-
dotnet https://github.com/mydotey/quantile-estimator/tree/master/dotnet
Features
-
Thread Safe
-
add value: lock free
-
batch get quantiles: synchronized
-
-
Time Window
- better accuracy by time window rotate
Algorithms
-
Classic Algorithm
-
accurate
-
no data compaction
-
-
CKMS Algorithm
-
data compaction & space efficient
-
predefined quantile error
-
most used approximate algorithm
-
-
GK Algorithm
- data compaction & space efficient
-
KLL Algorithm
-
data compaction & space efficient
-
new algorithm
-
Papers
-
Greenwald and Khanna. "Space-efficient online computation of quantile summaries" in SIGMOD 2001
-
Zohar Karnin, Kevin Lang and Edo Liberty. "Optimal Quantile Approximation in Streams" in FOCS 2016
Others' Projects
Developers
- Qiang Zhao [email protected]