[
https://issues.apache.org/jira/browse/ARROW-1565?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17396072#comment-17396072
]
David Li commented on ARROW-1565:
---------------------------------
Daniel Lemire compared various approaches (modifications of the heap approach
or modifications of quickselect) and found that the heap wins in his tests:
https://lemire.me/blog/2017/06/21/top-speed-for-top-k-queries/
If we want this to perfectly emulate Pandas's nlargest/nsmallest then there are
some additional complications (inputs must have a defined order to resolve
ties, and/or we must be able to track and output duplicate values).
> [C++][Compute] Implement TopK/BottomK streaming execution nodes
> ---------------------------------------------------------------
>
> Key: ARROW-1565
> URL: https://issues.apache.org/jira/browse/ARROW-1565
> Project: Apache Arrow
> Issue Type: New Feature
> Components: C++
> Reporter: Wes McKinney
> Priority: Major
> Labels: Analytics, query-engine
> Fix For: 6.0.0
>
>
> Heap-based topk can compute these indices in O(n log k) time
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
