Search papers, labs, and topics across Lattice.
This paper introduces RT-HiSS, the first exact similarity search algorithm leveraging GPU ray tracing cores for high-dimensional datasets, overcoming the limitations of existing methods that only handle up to three dimensions. By employing a two-pass approach for upper bound estimation and utilizing CUDA cores for candidate refinement, RT-HiSS achieves significant efficiency improvements in both index construction and search processes. The results demonstrate speedups of up to 8.37 times compared to state-of-the-art GPU algorithms and an astonishing 2,368.26 times relative to brute-force methods across various real-world datasets.
RT-HiSS achieves unprecedented speedups for high-dimensional similarity searches, revolutionizing the efficiency of GPU-based algorithms.
Recent GPU generations include special-purpose ray tracing (RT) cores for graphics applications. While RT cores are primarily used for rendering, recent works show they can be leveraged for general-purpose tasks, including similarity searches. However, existing approaches do not support datasets exceeding three dimensions. In this work, we propose RT-HiSS, the first exact GPU RT-core-based similarity search algorithm for high-dimensional datasets. GPU similarity search often scales poorly for large datasets with substantial search distances. To address this, RT-HiSS uses RT cores for fast index construction and searches, followed by candidate refinement on CUDA cores. We introduce a two-pass approach to estimate an upper bound on result size, enabling efficient batching under GPU memory constraints with near-perfect load balancing. Additionally, we examine shared memory tiling and compressed result masks to improve GPU resource utilization. RT-HiSS yields speedups up to 8.37$\times$ over competitive state-of-the-art GPU algorithms and up to 2,368.26$\times$ relative to the brute-force algorithm across six real-world datasets.
