[
https://issues.apache.org/jira/browse/ARROW-11367?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
ASF GitHub Bot updated ARROW-11367:
-----------------------------------
Labels: pull-request-available (was: )
> [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
> Priority: Major
> Labels: pull-request-available
> Time Spent: 10m
> Remaining Estimate: 0h
>
> 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)
