Yibo Cai created ARROW-11367:
--------------------------------
Summary: [C++] Implement approximante quantile utility
Key: ARROW-11367
URL: https://issues.apache.org/jira/browse/ARROW-11367
Project: Apache Arrow
Issue Type: New Feature
Components: C++
Reporter: Yibo Cai
Assignee: Yibo Cai
This utility is to approximate quantiles of arbitrary length inputs with
constant space (not storing input data points) [1]. It will be used in
implementing approximate quantile kernel and calculating latencies in flightrpc
benchmark.
t-digest [2] is state-of-the-art algorithm for quantile approximation. It
performs well on both edge (0.01, 0.99, etc) and normal cases (0.3, 0.5, etc).
And t-digest can run in parallel, which means multiple chunks can be processed
at same time and combined later.
T-Digest author maintains an java implementation [3]. There are some open
source c++ versions available, including facebook folly [4]. I planned to port
one of them but finally came up with my own implementation, which (I suppose)
is more efficient in space and time.
References
[1] A Survey of Approximate Quantile Computation on Large-scale Data
https://arxiv.org/abs/2004.08255v1
[2] Computing Extremely Accurate Quantiles Using t-Digests
https://arxiv.org/abs/1902.04023
[3] https://github.com/tdunning/t-digest/
[4] https://github.com/facebook/folly/blob/master/folly/stats/TDigest.h
https://github.com/derrickburns/tdigest
https://github.com/SpirentOrion/digestible
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
