Great work. Can you elaborate on how the radix selection works and how to get that working with float's and inner product distance? I just quickly checked the code, I'm not familiar with radix selection, but really interested in making extremely fast GPU indices.
The radix selection algorithm is a modified radix sort that, since we don't care to sort the whole list but rather just the top K results, manages to cut some of the time out of the algorihm. It was an awesome way to get experience in CUDA programming.
Radix sort works with any ordered sets--it just lends itself well for GPUs since it is designed to be run in parallel. I used the modified version to get the best hamming distance results quickly, and implemented a few other distance measures as well (e.g., cosine distance)
Comments
Great work. Can you elaborate on how the radix selection works and how to get that working with float's and inner product distance? I just quickly checked the code, I'm not familiar with radix selection, but really interested in making extremely fast GPU indices.
The radix selection algorithm is a modified radix sort that, since we don't care to sort the whole list but rather just the top K results, manages to cut some of the time out of the algorihm. It was an awesome way to get experience in CUDA programming.
Radix sort works with any ordered sets--it just lends itself well for GPUs since it is designed to be run in parallel. I used the modified version to get the best hamming distance results quickly, and implemented a few other distance measures as well (e.g., cosine distance)