Search papers, labs, and topics across Lattice.
This paper reformulates the reverse k-nearest neighbor (RkNN) query problem as a ray-casting problem in 2D geometric space, modeling users as rays and facilities as geometric primitives. They then develop an algorithm and implementation that leverages GPU ray-tracing hardware to efficiently solve this reformulated problem. Experiments show that this GPU-based approach significantly outperforms state-of-the-art R-tree based methods, especially in challenging scenarios with large k, dense user populations, and sparse facility distributions.
Solving nearest neighbor search just got a whole lot faster by turning it into a ray-tracing problem for GPUs.
Reverse k nearest neighbor (RkNN) queries are fundamental in spatial databases, location-based analytics, and recommendation systems. Existing state-of-the-art techniques rely on spatial pruning supported by R-trees and their variants. However, their pruning effectiveness degrades significantly in challenging scenarios where the number of facilities is small, the user population is dense, or the value of k is large. To overcome these limitations, this work reformulates the RkNN query problem in two-dimensional geometric spaces as a graphics ray-casting problem, where users are modeled as rays and facilities are represented as geometric primitives. Based on this formulation, the first algorithm and implementation exploiting dedicated hardware ray-tracing cores on modern GPUs are developed. This novel approach preserves strong filtering performance even for large values of k, dense user populations, and highly sparse facility distributions. Extensive experimental results demonstrate that the proposed method outperforms state-of-the-art algorithms across diverse settings, particularly in scenarios where traditional pruning strategies become inefficient.
