[ARROW-10831] [C++][Compute] Implemement quantile kernel

• Type: New Feature
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 4.0.0
• Component/s: C++
• Labels: pull-request-available
• External issue URL: https://github.com/apache/arrow/issues/26769
• Assignee: Yibo Cai
• Reporter: Yibo Cai
• Created: 07/Dec/20 05:03
• Updated: 11/Jan/23 08:15
• Resolved: 21/Jan/21 14:39

Description

Similar function as https://numpy.org/doc/stable/reference/generated/numpy.quantile.html
Support chunked array, and calculate multiple quantiles at once.

Possibly implement features in steps:

• implement exact quantile kernel which records all chunks and partition at finalize
• reduce memory footprint for integer inputs by maintaining "value:count" histogram
• implement approximate quantile kernel without storing input values

Issue Links

• is depended upon by: ARROW-11338 [R] Bindings for quantile and median
• links to: GitHub Pull Request #8920