PaperlayerView exact revision on arXiv

Source-linked AI summary

RT-HiSS: Ray Tracing Accelerated High Dimensional Vector Similarity Searches

Revanth Reddy Munugala, Michael Gowanlock

arXiv:2609.01975v1cs.DCcs.DB

TL;DR

RT-HiSS addresses the lack of RT-core similarity search methods for datasets above three dimensions by combining RT-core indexing and searches with CUDA-core refinement. It reports substantial speedups over GPU and brute-force approaches across datasets and search distances.

  • Problem

    Prior RT-core similarity-search approaches are limited to datasets with ≤3 dimensions, leaving high-dimensional distance similarity search unaddressed.

  • Method

    RT-HiSS groups nearby points for RT-core indexing and searches, then refines candidates on CUDA cores using a two-pass batching approach.

  • Results

    RT-HISS outperforms CUVS-BRUTE across all datasets and search distances, with speedups from 4.74× to 2,368.26×.

  • Takeaways & Limitations

    RT cores can support high-dimensional similarity searches when algorithmic design combines RT-core indexing with CUDA-core refinement.

  • Takeaways & Limitations

    Using RT-HISS for small or low-dimensional datasets with insufficient work can underutilize resources and degrade performance.

Abstract

from arXiv · show

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.

I. INTRODUCTION

Distance similarity searches support data-analytic tasks but face scaling and batching challenges on heterogeneous GPU systems. RT-HISS addresses these challenges by combining RT-core indexing with CUDA refinement and several GPU-oriented optimizations.

  • Distance similarity searches identify dataset points similar to query points and support tasks including clustering, outlier detection, and natural language processing.
  • GPU systems increasingly combine processor types, including CPUs, GPUs, DPUs, tensor cores, and ray tracing cores.
  • Existing RT-core similarity-search approaches face unconstrained result sizes that can exceed GPU global memory and complicate batching.
  • RT-HISS combines RT-core indexing with CUDA-core refinement for high-dimensional distance similarity searches.
  • RT-HISS groups nearby points into shared primitives, uses multi-pass ray tracing for result-size bounds and batching, and compresses results at the bit level.

II. BACKGROUND

Distance similarity search finds points within a specified distance, but conventional approaches face quadratic costs and high-dimensional indexing difficulties. RT-HISS reformulates the search around RT-core candidate identification while retaining exact CUDA-based refinement and compact result storage.

  • A. Problem Statement: Distance similarity search identifies neighbors whose Euclidean distance from a query is at most the search distance ϵ.
  • A. Problem Statement: Prior RT-core approaches are limited to datasets with ≤3 dimensions, motivating RT-HISS for large high-dimensional datasets.
  • 1) Result Set Representation:: The result set stores point pairs within ϵ, and the evaluation compares compact key-value storage rather than a full |Q| × |D| distance matrix.
  • OPTIX and RT-HISS: RT-HISS uses three dimensions for RT-core indexing to identify candidates, then refines those candidates across all dimensions with CUDA cores.

2) RT Cores:

RT-core similarity-search methods use BVH-based spatial pruning, but existing RT-core algorithms support only three-dimensional datasets. RT-HISS addresses this hardware constraint by combining three-dimensional RT indexing with CUDA-based refinement for high-dimensional DSS.

  • Brute-force DSS performs a linear scan with O(|D|2) time complexity, motivating indexing and GPU acceleration.
  • Existing GPU DSS methods use either CUDA cores or RT cores to prune searches and identify neighbors in parallel.
  • All existing RT-core similarity-search algorithms are limited to datasets with d ≤3 because of hardware constraints.
  • OPTIX constructs BVH trees from user-defined geometries and executes programmable shaders during ray tracing.

A. Distance Similarity Searches using RT Cores

RT-core DSS uses BVH traversal to identify candidate neighbors through ray–AABB intersections, then applies exact distance refinement. RT-HISS separates these stages and selects three high-variance dimensions for RT indexing in high-dimensional data.

  • RT-core DSS represents ε-neighborhoods as geometries enclosed by AABBs, which are organized into a BVH tree.
  • A query ray intersecting a BVH branch marks the enclosed points as candidate neighbors, while nonintersected branches are pruned.
  • Ray–AABB intersection alone cannot establish exact membership, so candidate points require Euclidean distance testing within ε.
  • RT-HISS performs candidate identification with RT cores and exact refinement in a separate CUDA-only kernel.
  • RT-HISS reorders dimensions by variance and uses the first three dimensions for RT indexing, while the remaining dimensions participate in CUDA refinement.

B. Identifying and Grouping Nearby Points

RT-HISS groups nearby points and represents each group’s ε-neighborhood as one bounding-sphere primitive, reducing ray–primitive intersections. A balanced kd-tree controls grouping granularity, but its height creates a pruning-versus-traversal trade-off.

  • Representing every point separately creates |D| primitives and many ray–primitive intersections on large datasets.
  • RT-HISS groups nearby points and represents their combined ε-neighborhood as a single bounding-sphere primitive.
  • A balanced kd-tree provides tunable height and approximately equal point counts per leaf, supporting uniform bounding spheres.
  • The algorithm rearranges primitive-associated points contiguously in memory and orders queries by intersected primitives for later processing.
  • Shorter kd-trees reduce traversal levels but produce larger candidate groups, whereas taller trees improve pruning while increasing traversal costs.

C. Rearranging the Points Within the Dataset

RT-HISS reorganizes data and queries to improve refinement locality, then uses a two-pass ray-tracing scheme to estimate batch capacity and write intersection results efficiently under limited GPU memory.

  • Contiguous storage of points within each primitive enables coalesced memory accesses during candidate refinement.
  • The First Intersection Test counts primitive intersections and query intersections to estimate the memory capacity available for a GPU batch.
  • Queries are accumulated until their total intersections remain within the previously determined maximum batch capacity Imax.
  • The first ray-tracing pass counts intersections, while the second stores intersected primitive indices using prefix-sum offsets.
  • The two-pass scheme eliminates global atomic updates and stores only query indices, reducing result-storage memory usage by half.
  • Processing primitives with more intersections first mitigates load imbalance near the end of execution.

E. Candidate Refinement on CUDA Cores

RT-HISS refines RT-core-generated candidate neighbors on CUDA cores, using shared-memory tiling and compact result representations to reduce memory traffic and storage.

  • Candidate refinement: RT-HISS records candidate data from RT-core indexing and refines candidate neighbors with a separate CUDA-core kernel.The RT-core phase identifies points that may lie within the ε search distance of each query batch.
  • Shared-memory tiling: Shared-memory tiling reuses query and primitive-point data, making refinement more efficient than directly reading point data from global memory.Coordinates are transposed during loading so points are tiled cooperatively by dimension.
  • Result representation: A result mask stores each query–candidate comparison as one bit, requiring |Q′| · |S′| · |L| bits for a batch.This representation replaces substantially larger key-value-pair storage for recording comparison outcomes.
  • Result compression: Stream compaction stores only neighbor positions, reducing the result representation from 14 elements to 5 in the illustrated example.The compressed result mask is produced on the GPU after CUDA-core candidate refinement.

2) Pinned Memory for Fast Data Transfers:

The evaluation uses large, high-dimensional real-world datasets and measures end-to-end response time under a fixed experimental setup, including data movement and batching effects.

  • Measurement: Reported response times include reordering, kd-tree grouping, RT-core indexing, CUDA-core refinement, and device-to-host result copying.Dataset loading from disk is excluded, and experiments exceeding 60,000 seconds are marked TIMEOUT.
  • Datasets: The evaluation covers datasets containing 288K–11.6M points with dimensionalities d ∈ [18, 128].Three search distances represent small, medium, and large selectivity levels.
  • Baselines: RT-HISS is evaluated against GPU-accelerated DSS methods including GDS-JOIN, COSS, GTS, CUVS-BRUTE, PYTORCH3D, and RTNN.RTNN is used only for performance evaluation on d = 3 datasets.
  • Experimental setup: Batching is used by several comparison methods to address limited global memory, including implementations for CUVS-BRUTE and PYTORCH3D.The experimental platform uses a Quadro RTX 5000 GPU with 256 GiB of host memory.

D. kd-tree Height

RT-HISS balances kd-tree pruning against traversal and refinement costs, using a dataset-size-based height choice and grouping nearby points into shared primitives.

  • Height trade-off: A higher kd-tree height improves pruning but increases indexing and search costs, while a lower height increases CUDA-core refinement work.The trade-off makes kd-tree height a critical performance parameter.
  • Height evaluation: Across most datasets, response time improves with tree height until a dataset-specific optimum, then worsens; WEC performs best at hkd = 10.Figure 6 evaluates heights from 10 through 18 using averaged normalized response time.
  • Height selection: Setting hkd = ⌊ln |D|⌋ performs well across datasets and remains close to the observed optimal height.RT-HISS uses this rule in subsequent experiments.
  • Point grouping: Grouping nearby points into one bounding-sphere primitive yields speedups from 16.2× to 130.6× over representing each point separately.The reported minimum is for WEC with ϵl, and the maximum is for SuSy with ϵl.
  • Point grouping: Grouping nearby points reduces ray–primitive intersections and produces an average speedup of 42.4× across datasets and search distances.The approach is especially beneficial when individual-point primitives create many RT-core intersections.
  • Point refinement: Using shared memory for both query and primitive points outperforms the global-memory baseline across all datasets and search distances with an average speedup of 2.12×.The broader ablation concludes that shared memory should be used judiciously because partial use can degrade performance.

G. Ablation Study #2: Result Representation

Result representation strongly affects batching and response time: compressed masks reduce transfer size and batches relative to key-value pairs, improving RT-HISS performance.

  • Configurations: The ablation compares compressed masks, uncompressed masks, and key-value-pair result representations.The variants isolate how result storage affects batching and response time.
  • Batching: For ϵl, result-mask variants require 1–1,638 batches, whereas key-value copies require 13 to ≳90K batches.Compressed and uncompressed masks use the same number of batches in this comparison.
  • Compression: RT-HISS uses one bit per point comparison versus two 32-bit integers per key-value result, achieving a 64× compression ratio.The reduced representation allows more queries per batch and supports GPU resource saturation.
  • Response time: Compressed result-mask copying outperforms uncompressed copying across datasets and search distances, except in a few evaluation scenarios, with an average speedup of 1.24×.The improvement is attributed to reduced data-transfer time.

H. Comparison with the State-of-the-art

RT-HISS generally outperforms competing GPU similarity-search algorithms, including indexed, brute-force, and low-dimensional RT-based approaches. Its optimizations improve refinement-kernel resource use, while low-dimensional performance remains constrained by design trade-offs.

  • Comparison with indexed GPU algorithms: Up to 9.19× speedup over GDS-JOIN and up to 8.37× over COSS demonstrate RT-HISS’s strong performance against indexed GPU algorithms.RT-HISS slowed only on SuSy at one search distance and on WEC at one search distance.
  • Comparison with GPU baselines: 34.20× to 4,180.12× speedups over PYTORCH3D span all evaluation scenarios, while GTS reaches timeouts in several experiments.These comparisons cover all datasets and search distances reported for the evaluation.
  • Comparison with brute force: 4.74× to 2,368.26× speedups over CUVS-BRUTE show substantial gains over the optimized brute-force baseline.CUVS-BRUTE does not use a result estimator and allocates |D|^2 result elements, limiting the number of queries processed per batch.
  • Comparison with RT-based algorithms: Up to 1.88× speedup over RTNN is observed across the evaluated d = 3 datasets.The comparison uses two real-world and two synthetic datasets with the ϵs search distance.
  • Low-dimensional trade-offs: Low-dimensional performance is reduced because separate CUDA refinement and result-set compression are optimized for high-dimensional searches.The paper identifies both design decisions as opportunities for improving low-dimensional DSS.
  • Kernel optimizations: Shared memory tiling improves compute throughput by 2.06× to 4.38× and reduces global memory loads by 85.64% to 98.35% versus Shared-None.The optimization stages point data in shared memory to reduce off-chip global-memory requests.

L. Time Distribution Analysis

CUDA refinement dominates RT-HISS execution time, whereas RT-core indexing occupies a small fraction of runtime while supporting batching and load balancing. The design targets large high-dimensional workloads, with limited suitability for small or low-dimensional datasets and a single-GPU evaluation scope.

  • Component time distribution: CUDA core execution averages 59.54% of total time, followed by kd-tree construction at 15.71% and CPU work at 11.30%.Times are averaged across all datasets and the ϵs, ϵm, and ϵl search distances.
  • Component time distribution: FIT and the two-pass RT-core approach together average only 6.58% of total time, supporting lightweight indexing and near-perfect batch load balancing.The two-pass approach enables batching based on estimated result sizes.
  • Design implication: RT-HISS combines RT-core indexing with CUDA-core refinement to address RT-core hardware limitations for high-dimensional DSS.The approach is presented as producing performance gains over state-of-the-art GPU algorithms.
  • Scope and scalability: The evaluation focuses on a single-GPU system, although the algorithm and optimizations can be translated to multi-GPU and multi-node HPC environments.The proposed extension would asynchronously offload work while retaining the batching and optimization strategies.
  • Future work: Future work extends RT-HISS toward exact high-dimensional k-nearest neighbors by recursively expanding the search radius until k neighbors are found.The proposed strategy retains three-dimensional indexing and applies the paper’s optimizations to the resulting recursive searches.
  • Scope and limitations: Small or low-dimensional datasets with insufficient work can underutilize resources and produce degraded performance.The paper identifies this as a limitation to be examined alongside support for other distance similarity searches.
Loading 2609.01975v1…