Radix Top-K

Radix Top-K is an algorithm for finding the top-k elements in an array without sorting the full array. For simplicity, assume the values are unsigned integers. The same idea can be extended to other representations. Initial setup: Choose TOP_K and BITS_PER_ITER, and assume every element can be represented with NUM_BITS bits. Then iteratively apply the following procedure: Extract the next BITS_PER_ITER bits from all current candidates, starting from the most significant bits. Count how many candidates fall into each bucket: 0, 1, ..., 2^{BITS_PER_ITER} - 1. Perform an inclusive scan over the bucket counts. Let K_remaining be TOP_K minus the number of elements already known to be in the top-k. Select the first bucket index i where inclusive_scan[i] >= K_remaining. All elements in buckets j < i are guaranteed to be in the top-k. Elements in bucket i remain candidates for the next round. Elements in buckets j > i are discarded. Repeat with the new candidates as input, updating…