RT-RkNN: Reverse k Nearest Neighbor Queries as a Graphics Ray Casting Problem

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

RT-RkNN: Reverse k Nearest Neighbor Queries as a Graphics Ray Casting Problem

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cloud distributedcomputing parallelcomputing

distributed computing, parallel computing, cloud

RT-RkNN: Reverse k Nearest Neighbor Queries as a Graphics Ray Casting Problem Zhengyang Bai

Peng Chen∗

Mohamed Wahib∗

RIKEN Center for Computational Science Kobe, Japan [email protected]

arXiv:2605.26671v1 [cs.DB] 26 May 2026

ABSTRACT Reverse 𝑘 nearest neighbor (R𝑘NN) 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 𝑘 is large. To overcome these limitations, we formulate the R𝑘NN query in two-dimensional geometric spaces as a graphics ray casting problem, in which users are modeled as rays and facilities are represented as geometric primitives. Based on this formulation, we design the first algorithm and provide an implementation that exploits dedicated hardware ray tracing cores on modern GPUs. This novel approach preserves strong filtering performance even for large values of 𝑘, dense user populations, and highly sparse facility distributions. Extensive experimental results demonstrate that our method outperforms state-of-the-art algorithms in diverse settings, especially in scenarios where traditional pruning strategies become inefficient. PVLDB Reference Format: Zhengyang Bai, Peng Chen, and Mohamed Wahib. RT-RkNN: Reverse k Nearest Neighbor Queries as a Graphics Ray Casting Problem. PVLDB, 19(9): XXX-XXX, 2026. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/simon2/RT-RkNN.

INTRODUCTION

Reverse 𝑘 Nearest Neighbor (R𝑘NN) queries are fundamental operators in spatial databases and location-based services, with applications spanning influence analysis, recommendation systems, and spatial impact assessment [6, 12, 18, 23, 27, 41, 56, 58]. Given a set of facilities 𝐹 and users 𝑈 , an R𝑘NN query retrieves all users for whom a given facility is one of their 𝑘 nearest neighbors. Unlike the standard 𝑘 nearest neighbor (𝑘NN) query that captures local proximity, R𝑘NN characterizes a facility’s influence set or effective ∗ Corresponding author.

This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected]. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 19, No. 9 ISSN 2150-8097. doi:XX.XX/XXX.XX

market reach, supporting operational efficiency and protecting substantial capital investments in domains such as retail site selection and delivery services [39]. Beyond spatial applications, R𝑘NN has gained renewed attention in artificial intelligence, where modeling influence often outweighs similarity alone. It refines density estimation and cluster expansion in DBSCAN variants [5, 22], and mitigates hubness in graph neural networks, promoting more balanced graph structures and improved representation learning [44]. Due to their utility, significant research has focused on developing efficient R𝑘NN processing techniques [8, 19, 27, 28, 45, 47, 50, 51, 60– 63], as well as variants like dynamic, continuous, probabilistic, and batched R𝑘NN [1, 3, 4, 7, 9–11, 14, 25, 29, 46, 49, 59]. A critical distinction from the standard 𝑘NN query is the nature of their search spaces. While a 𝑘NN query operates within a compact, query-centered region, an R𝑘NN query must examine usercentric influence regions distributed across the entire data space, resulting in a significantly larger and more complex search area. To manage this complexity, most state-of-the-art solutions rely on spatial pruning strategies to eliminate candidates early. These include region-based pruning [50, 63] and half-space pruning [8, 51, 60, 62], typically built upon spatial indexes like the R-tree [20] or its variants (e.g., R*-tree [2]). These methods leverage geometric relationships to achieve strong practical performance on large datasets. Despite their success, the efficiency of these pruning-based strategies is predicated on the selectivity of geometric relationships. This reliance becomes a critical limitation in realistic and increasingly common scenarios where this selectivity diminishes. For instance, California’s 337 hospitals serve millions of patients annually [24], while around 50 last-mile facilities deliver 2.3 million daily packages to 8.8 million residents in New York City [40]. In such cases, the expansive influence region of each facility severely undermines spatial pruning, motivating the pursuit of a robust R𝑘NN method that does not degrade under these challenging conditions. We identify three specific scenarios where traditional pruningbased R𝑘NN algorithms face significant performance degradation: 1) Small Facility Sets: A small number of facilities leads to expanded potential influence regions for each, drastically reducing the number of candidates that can be pruned. 2) Large User Populations: As the cardinality of 𝑈 grows, spatial pruning retains a much larger pool of candidate users, leading to a prohibitive increase in verification costs. 3) Large 𝑘 Values: Increasing 𝑘 weakens the geometric criteria for discarding candidates, as the conditions for exclusion become harder to satisfy, thereby diminishing the pruning effect. To address these challenges, we propose a fundamental formulation of the two-dimensional (2D) R𝑘NN problem, called RT-RkNN.

We model it as a three-dimensional (3D) graphics ray casting problem, where users are treated as rays and facilities are encoded as geometric primitives. This novel formulation allows the R𝑘NN evaluation to be mapped to massively parallel ray-primitive intersection tests. Crucially, the core geometric operations in this model align perfectly with the capabilities of GPU Ray Tracing (RT) cores, which were originally designed for 3D rendering. By leveraging these specialized hardware accelerators, our approach minimizes warp divergence, exploits massive parallelism, and delivers scalable R𝑘NN performance that remains stable even in settings where traditional spatial pruning becomes ineffective. This paper makes the following contributions: • We formulate 2D R𝑘NN queries as a 3D graphics ray casting problem and establish the formal equivalence between ray–primitive occlusion and R𝑘NN’s spatial pruning relationships. • We provide the first algorithm derived from this new formulation, which can leverage mature technologies in computer graphics and enables massively parallel execution of ray–primitive intersection tests. • We present the application of GPU ray tracing cores to R𝑘NN query processing, demonstrating how hardware-accelerated ray– primitive intersection tests can be effectively leveraged for efficient spatial pruning and user verification. • Extensive experiments on real-world datasets with up to more than 23 million users demonstrate that our approach outperforms state-of-the-art baselines across diverse parameter settings. Notably, our method performs particularly well in scenarios where traditional spatial pruning becomes inefficient, such as with large 𝑘 values, high user cardinality, or sparse facility distributions.

BACKGROUND & RELATED WORK

In this section, we first provide the formal definition of the target problem and address the scope of this paper in subsection 2.1. We review the R𝑘NN related work in subsection 2.2, and the use of RT cores in spatial queries in subsection 2.3.

2.1

Problem Statement

R𝑘NN queries are classified into monochromatic R𝑘NN queries and bichromatic R𝑘NN queries [27]. Monochromatic R𝑘NN. Let 𝑃 = {𝑝 1, . . . , 𝑝𝑛 } be a set of points in a metric space. For any point 𝑝 ∈ 𝑃, let NN𝑘 (𝑝; 𝑃) denote the set of the 𝑘 nearest neighbors of 𝑝 within 𝑃 \ {𝑝}. A monochromatic R𝑘NN query for a point 𝑞 ∈ 𝑃 returns RkNN(𝑞; 𝑃) = { 𝑝 ∈ 𝑃 \ {𝑞} | 𝑞 ∈ NN𝑘 (𝑝; 𝑃) }. In other words, 𝑝 is an R𝑘NN of 𝑞 if 𝑞 is among the 𝑘 closest points to 𝑝 in the same dataset. Bichromatic R𝑘NN. Let 𝐹 = {𝑓1, . . . , 𝑓𝑚 } be a set of facilities and 𝑈 = {𝑢 1, . . . , 𝑢𝑛 } be a set of users, where 𝐹 and 𝑈 lie in the same metric space and 𝐹 ∩𝑈 = ∅. For any user 𝑢 ∈ 𝑈 , let NN𝑘 (𝑢; 𝐹 ) denote its 𝑘 nearest facilities in 𝐹 . A bichromatic R𝑘NN query for a facility 𝑓 ∈ 𝐹 returns RkNN(𝑓 ; 𝐹, 𝑈 ) = { 𝑢 ∈ 𝑈 | 𝑓 ∈ NN𝑘 (𝑢; 𝐹 ) }. That is, 𝑢 is an R𝑘NN of 𝑓 if 𝑓 is one of the 𝑘 nearest facilities to 𝑢.

R𝑘NN queries are challenging because the membership condition for a user 𝑢 depends on how the distance dist(𝑢, 𝑓 ) compares to its distances to all other facilities in 𝐹 . Formally, 𝑢 is an R𝑘NN of 𝑓 if and only if { 𝑎 ∈ 𝐹 \ {𝑓 } | dist(𝑢, 𝑎) < dist(𝑢, 𝑓 ) } < 𝑘. This condition requires determining the rank of dist(𝑢, 𝑓 ) within the entire distance set {dist(𝑢, 𝑎)}𝑎∈𝐹 . Unlike forward 𝑘NN, which only identifies the 𝑘 smallest distances for each query point, the reverse condition depends on the global ordering of distances around every user. Consequently, R𝑘NN queries inherently involve many distance comparisons per user, making them mathematically global and significantly more complex. Scope of this paper. Following existing R𝑘NN techniques that primarily target 2D spatial data that arise in location-based services [8, 50, 60, 63], we also put the focus of this paper on 2D location data. Although our approach applies to both monochromatic and bichromatic R𝑘NN queries, we focus on the bichromatic setting in our performance evaluation for easier presentation as it represents the more general case with the monochromatic case reducible to it. The performance of our approach on monochromatic R𝑘NN queries is only briefly discussed. Although, as mentioned above, R𝑘NN queries have been extensively studied with various variants, we focus on the most widely used static queries in Euclidean space in this paper. Finally, given the substantially larger memory in modern machines, even our largest dataset (containing over 23 million points) occupies only about 218 MB, far below the capacity of a typical PC. We therefore assume that all data can be fully loaded into main memory. As a result, we do not evaluate disk I/O performance in this paper and instead report runtime directly.

2.2

Existing R𝑘NN Algorithms

While early studies on reverse nearest neighbor (RNN) queries relied on substantial preprocessing to enable efficient query evaluation [19, 27, 28, 45, 47, 61], such preprocessing introduces significant overhead and lacks the flexibility required for dynamic updates in real-time services. We therefore focus on four representative preprocessing-free techniques, selected for their wide adoption and strong performance. SIX [50], known as the first algorithm that does not need any precomputation, uses a regions-based pruning strategy which partitions the space around the query point into six equal angular partitions of 60◦ each. For a given partition 𝑃, the distance from the query to its 𝑘-th nearest facility in that region defines a filtering threshold: any user located in 𝑃 at a distance greater than the threshold cannot be an R𝑘NN of the query facility. Figure 1a illustrates the idea that users lying in the shaded area are pruned because at least 𝑘 facilities within the same partition are closer to them than the query. The remaining users are treated as candidates to be verified in the subsequent verification stage, which is performed by issuing a range query centered at the candidate with radius 𝑑𝑖𝑠𝑡 (𝑢, 𝑞), where 𝑢 is the candidate user and 𝑞 is the query facility. The candidate is confirmed as an R𝑘NN result if and only if the range query contains no more than 𝑘 facilities. However, since a separate range query is required for each candidate user, the verification phase leads to substantial overhead.

Bd:q d

c b p

c q

a Bc:q (a) SIX filtering example.

Bd:q b c

b Bb:q

c a Bc:q

Ba:q

(b) TPL filtering example.

Bb:q

p a

Bb:q

Bc:q Ba:q

Ba:q

(d) SLICE pruning example.

Figure 1: Illustration of SIX [50] filtering, TPL [51] filtering, InfZone [8] pruning, and SLICE [63] pruning (𝑘 = 2). TPL [51] is the first algorithm which applied spatial pruning based on half-space pruning to R𝑘NN queries and inspired many follow up works [8, 60, 62], including ours. Given a query point 𝑞 and a facility 𝑓 , the perpendicular bisector 𝐵 𝑓 :𝑞 divides the space into two half-spaces: the region 𝐻 𝑓 :𝑞 that contains 𝑓 and the opposite region 𝐻𝑞:𝑓 . Any point 𝑝 lying in region 𝐻 𝑓 :𝑞 indicates that 𝑝 is closer to facility 𝑓 rather than 𝑞. A point lying in at least 𝑘 such half-spaces cannot regard 𝑞 as one of its 𝑘 nearest facilities and can therefore be pruned. The TPL algorithm iteratively accesses unpruned facilities in increasing order of their distance to 𝑞, and each accessed facility contributes a half-space that potentially enlarges the prunable region. Consider the example in Figure 1b, where the bisectors of facilities 𝑎, 𝑏, and 𝑐 partition the space. When 𝑘 = 2, the shaded region corresponds to points that fall in at least two of the half-spaces 𝐻𝑎:𝑞 , 𝐻𝑏:𝑞 , and 𝐻𝑐:𝑞 , and thus any point in this region can be safely filtered. Facility 𝑑, however, lies in the region that can be filtered, so it is not used to build bisectors for spatial pruning. User 𝑝 lies inside the prunable region and therefore cannot be an R𝑘NN candidate. As TPL’s filtering phase may leave false positives like SIX, the algorithm includes a subsequent refinement stage to verify the remaining candidates. Influence Zone (InfZone) [8] relies on the concept of the influence zone, which represents the region in which a user is guaranteed to be an R𝑘NN of the query point 𝑞. In other words, a point 𝑝 is an R𝑘NN of 𝑞 if and only if 𝑝 lies inside the influence zone. To estimate the influence zone, InfZone incrementally intersects the half-spaces generated by the facilities. The construction of the influence zone, illustrated in Figure 1c, is also driven by the half-spaces of facilities relative to the query point 𝑞. As each facility is processed, the region is filtered by removing any area excluded by at least 𝑘 facilities, and the remaining area is the influence zone. Facilities whose bisectors cannot affect the influence zone (like facility 𝑑 in Figure 1c) are ignored. The InfZone algorithm builds the zone by tracking the intersections of unpruned bisectors. A critical insight is that the influence zone is star-shaped [43], which enables an efficient pruning strategy: a facility 𝑓 is unnecessary if min 𝑑𝑖𝑠𝑡 (𝑓 , 𝑣) > 𝑑𝑖𝑠𝑡 (𝑣, 𝑞) for every convex vertex 𝑣 of the current zone. However, a direct check against all 𝑂 (𝑚 2 ) vertices, where 𝑚 is the number of bisectors, is computationally heavy. To mitigate this, two inexpensive filters are applied first: (1) a facility 𝑓 can be directly pruned if

𝑑𝑖𝑠𝑡 (𝑓 , 𝑞) > 2 × max 𝑑𝑖𝑠𝑡 (𝑣, 𝑞), 𝑣 ∈𝑉

(1)

and (2) a facility 𝑓 cannot be pruned if 𝑑𝑖𝑠𝑡 (𝑓 , 𝑞) < 2 × min 𝑑𝑖𝑠𝑡 (𝑝, 𝑞),

(2)

𝑝 ∈𝐸

where 𝑉 is the vertex set and 𝐸 is the boundary of the influence zone. The expensive vertex check is only performed for facilities that do not meet either of these two conditions, which significantly reduces the overall computation cost. The verification stage in InfZone consists of a single geometric containment check. Any user located inside the influence zone is directly reported as an R𝑘NN, whereas any user outside it is immediately filtered out. This mechanism allows the algorithm to avoid costly distance computations and eliminates the need for a candidate examination process. SLICE [63] enhances the filtering power of the regions-based pruning, which was first proposed in the SIX approach [50] while retaining its computational efficiency. SLICE partitions the space around the query point 𝑞 into 12 regions of equal angular extent, a number determined to be optimal. Within a partition 𝑃, a facility 𝑓 defines two key arcs: an upper arc, which describes the area that can be pruned by 𝑓 , and a lower arc, which defines the area that is safe from 𝑓 . For any partition 𝑃 and facility 𝑓 , the radius of two arcs can be determined in 𝑂 (1) time by evaluating the maximum and minimum subtended angles of 𝑓 over 𝑃, which are equivalent to the distances from the intersection points between 𝑓 ’s bisector 𝐵 𝑓 :𝑞 and the two radial boundaries of 𝑃. During the pruning phase, for each partition, SLICE maintains the 𝑘-th smallest upper arc as its bounding arc (𝑟 𝑃𝑅 ). Any point 𝑝 in 𝑃 with 𝑑𝑖𝑠𝑡 (𝑝, 𝑞) > 𝑟 𝑃𝑅 is guaranteed to be pruned by at least 𝑘 facilities and is filtered. As shown in Figure 1d, the shaded area is the space pruned by facilities 𝑎, 𝑏, 𝑐 and 𝑑. We can see that in SLICE, each facility can potentially contribute to the spatial pruning for multiple partitions. Similar to SIX and TPL, SLICE’s filtering phase may also leave false positives; therefore, a verification phase is necessary. For the verification phase, candidate users are those lying inside their partition’s bounding arc. A facility is considered significant for a partition if its lower arc is smaller than the partition’s bounding arc, meaning it can potentially prune candidates. SLICE creates a sorted significant list of these facilities for each partition. To verify a candidate user 𝑢, the algorithm checks facilities in this sorted list, counting how many prune 𝑢. The process stops early if 𝑘 pruning facilities are found, which means 𝑢 can be filtered or if the lower arc of the current facility exceeds 𝑑𝑖𝑠𝑡 (𝑢, 𝑞), which means 𝑢 is confirmed as an R𝑘NN result of 𝑞.

Input

User set u4

u2 u1

Ob:q

Modeled Users as Rays

Ray origins Rays

Occluders Intersections RkNN users Pruned users

Facility set c b a

Oa:q

Oa:q Ob:q

c b

Build Occluders a

Oc:q Build 3D Scene (BVH-indexed)

Oc:q

User plane

u2 u3

Perform User Verification through Ray Casting with GPU RT cores.

Figure 2: Overview of the RT-RkNN workflow. The input is separated into a user set and a facility set. Users are modeled as rays, while facilities are used to construct occluders based on the invalid sides of pairwise bisectors. All occluders are embedded as layered triangles in a 3D scene indexed by a BVH. During query processing, each user ray is cast perpendicularly to 𝑥, 𝑦-plane. A user is reported as an R𝑘NN result if and only if its ray intersects fewer than 𝑘 occluders.

2.3

RT Cores in Spatial Queries

In recent years, RT cores have transcended graphics, emerging as a powerful primitive for accelerating database operations including indexing, scan, and query [21, 31, 48], as well as spatial and distance-based queries such as 𝑘NN [32, 38, 64], high-dimensional approximate nearest neighbor search [30], DBSCAN clustering [37], spatial joins [16], and spatial indexing [17]. By encoding spatial proximity as geometric primitives and traversing a Bounding Volume Hierarchy (BVH) [34] on dedicated hardware, RT cores sidestep the branching that degrades standard SIMT execution, reducing distance comparisons to hardware-level intersection tests and enabling concurrent evaluation of millions of user–facility relationships at low latency. Among these tasks, RT-core-accelerated 𝑘NN is the most closely related to our problem, as both involve point-to-point distance evaluation. However, all existing 𝑘NN methods [32, 38, 64] using RT cores adopt a query-centered formulation: each point acts as a ray origin, and candidate neighbors are identified through intersection tests or distance filtering relative to that single origin of query point. While this design aligns well with the objective of 𝑘NN search, it is fundamentally incompatible with the semantics of R𝑘NN, where the goal is to determine for which users a facility remains competitive against all other facilities. Consequently, query-centered formulations cannot capture the required cross-facility ranking relationships inherent in R𝑘NN, thereby motivating the development of a distinct geometric formulation.

PROPOSED APPROACH: RT-RKNN

In this section, we describe how an R𝑘NN query can be formulated as a graphics ray casting problem, prove its correctness, and present our algorithm based on this new geometric interpretation that directly aligns with dedicated hardware ray tracing cores on modern GPUs. To offer a high-level view of the proposed method, Figure 2 summarizes the end-to-end RT-RkNN workflow, from inputs to constructing occluders and the BVH-indexed scene, and

finally performing ray-casting–based user verification on GPU RT cores.

3.1

R𝑘NN Formulation as Graphics Ray Casting

Ray casting, a fundamental operation in modern computer graphics [57], determines how rays interact with geometric primitives in a scene. A ray is emitted from an origin and travels through a 3D environment while reporting intersections with objects such as triangles. Formally, in ray casting, a ray is defined as r(𝑡) = o + 𝑡 · d,

(3)

where o ∈ R3 is the ray origin, d ∈ R3 is the ray direction, and 𝑡 ∈ [𝑡 min, 𝑡 max ] specifies the ray’s active interval. A ray intersects a geometric primitive 𝑃 if and only if {r(𝑡) | 𝑡 ∈ [𝑡 min, 𝑡 max ]} ∩ 𝑃 ≠ ∅.

(4)

∈ R3 , the widely used

When 𝑃 is a triangle with vertices v0, v1, v2 Möller–Trumbore test [36] determines an intersection by solving r(𝑡) = (1 − 𝑎 − 𝑏)v0 + 𝑎v1 + 𝑏v2,

(5)

for barycentric coordinates 𝑎 ≥ 0, 𝑏 ≥ 0, and 𝑎 + 𝑏 ≤ 1. These concepts, such as rays, triangle primitives, and ray–primitive intersection tests, form the basis for the geometric constructions used in the following subsection. Although a single ray may intersect multiple primitives, real-time graphics pipelines typically limit the number of processed intersections for performance reasons [15]. This operational model naturally aligns with the structure of R𝑘NN queries. Half-space pruning techniques for R𝑘NN rely on perpendicular bisectors between facilities, where each bisector separates space into a region in which the query facility is closer and a region in which a competing facility is closer. We reinterpret this geometric relationship directly as a graphics ray casting problem: users act as ray origins, and the invalid half-spaces induced by facility pairs are encoded as occluding geometric primitives. Under this formulation, determining whether a user belongs to the R𝑘NN result reduces to counting the number of occluder primitives intersected by their

a q

(a) Normal case.

(b) Extended case.

a q

count reaches 𝑘. Figure 2 illustrates the example with 𝑘 = 2: rays 𝑟 3 and 𝑟 4 intersect fewer than two occluders and are reported as R𝑘NN results of 𝑞, while 𝑟 1 and 𝑟 2 each hit at least two occluders and the corresponding users are pruned. To formalize the notion of occluder, scene and ray, we provide the formal notation used in our geometric representation.

(d) Horizontal case.

Figure 3: Four occluder construction scenarios.

corresponding ray. If a ray intersects at least 𝑘 such occluders, then at least 𝑘 competing facilities are closer to that user than the query facility, and the user can be pruned. For each facility pair with respect to a query facility, the invalid side of their bisector can be represented as one or more triangular occluders. Figure 3 illustrates the four possible occluder construction scenarios: (a) The normal case, where the invalid side forms a triangle naturally; (b) The extended case, where the invalid region of a non-vertical and non-horizontal bisector does not naturally form a triangular shape because the bisector extends beyond the bounded domain, and thus the exact polygonal boundary is replaced by a single triangle that fully covers the intended invalid space; (c) The vertical bisector case; and (d) The horizontal bisector case. When the bisector is neither vertical nor horizontal, the invalid region forms a triangle. Otherwise, the invalid region becomes rectangular and can be modeled using two triangles. Each occluder is constructed by intersecting the bisector with the rectangular domain boundary, producing two intersection points. Together with one or two boundary vertices lying on the invalid side, these points form either a single triangle or two triangles, depending on the shape of the invalid region. As illustrated in the right side of Figure 2, we embed all the occluders of corresponding facilities into a simple 3D scene to align the representation with the ray casting direction and to avoid geometric degeneracies. Users lie on a plane (e.g., 𝑧 = 0), and rays are cast perpendicularly through the scene from the same (𝑥, 𝑦) coordinates as the users but with a larger 𝑧 value. The occluders are positioned as horizontal layers parallel to the 𝑥𝑦-plane, each placed at a distinct height, ensuring rays traverse the occluders in a consistent front-to-back order before reaching the user plane. In this 3D embedding, each user corresponds to a single ray shot through the layered occluders. The R𝑘NN query reduces to counting the number of occluders intersected by this ray. If the ray hits at most 𝑘 −1 occluders, the user does not have more than 𝑘 closer facilities than query 𝑞 and remains as one of the query results. Conversely, if it intersects 𝑘 or more occluders, the user can be pruned. Because the occluders are arranged as discrete layers, intersections occur in strictly ordered depth, enabling early termination once the hit

Definition 3.1 (Occluder). Let 𝑅 ⊂ R2 be a rectangular domain, and let 𝑎, 𝑞 ∈ 𝑅 be two facilities with coordinates (𝑥𝑎 , 𝑦𝑎 ) and (𝑥𝑞 , 𝑦𝑞 ), where 𝑞 is the query facility and 𝐵𝑎:𝑞 denotes the perpendicular bisector between 𝑎 and 𝑞. If 𝐵𝑎:𝑞 is neither vertical nor horizontal, among the four vertices of 𝑅 we select the vertex lying on the invalid side of 𝐵𝑎:𝑞 and farthest in the direction from 𝑎 toward 𝑞, denoted by 𝑣. The bisector intersects the two boundary edges incident to 𝑣, producing two distinct intersection points 𝑝 1 and 𝑝 2 . If 𝐵𝑎:𝑞 is vertical or horizontal, there are two farthest vertices of 𝑅 on the invalid side of the bisector with equal distance to 𝐵𝑎:𝑞 , denoted by 𝑣 1 and 𝑣 2 . The bisector intersects the two boundary edges of space 𝑅 are denoted as 𝑝 1 and 𝑝 2 . To embed the geometry into 3D space, we assign a unique height 𝑧𝑎:𝑞 > 0 shared by all lifted points (𝑣, 𝑝 1, 𝑝 2 or 𝑣 1, 𝑣 2, 𝑝 1, 𝑝 2 ) such that no two occluders are associated with different facility pairs sharing the same 𝑧-coordinate. The occluder corresponding to the facility pair (𝑎, 𝑞) is then defined as 𝑂 𝑎:𝑞 =

   △ (𝑣, 𝑝 1 , 𝑝 2 ),    △ (𝑣1 , 𝑝 1 , 𝑝 2 ) ∪ △ (𝑣1 , 𝑣2 , 𝑝 2 ), 

if 𝑥𝑎 ≠ 𝑥𝑞 and 𝑦𝑎 ≠ 𝑦𝑞 , (6) if 𝑥𝑎 = 𝑥𝑞 or 𝑦𝑎 = 𝑦𝑞 .

Definition 3.2 (Scene). Let 𝐹 be the set of all facilities and let 𝑞 ∈ 𝐹 be the query facility. For every facility 𝑎 ∈ 𝐹 \ {𝑞}, let 𝑂 𝑎:𝑞 denote the occluder associated with the pair (𝑎, 𝑞) as defined in Definition 3.1. The scene corresponding to query facility 𝑞 is defined as the set: T𝑞 = 𝑂 𝑎:𝑞 𝑎 ∈ 𝐹 \ {𝑞} . (7) Definition 3.3 (Ray). For a user 𝑢 with its coordinates u ∈ R2 , as rays are cast from the same (𝑥, 𝑦)-coordinates of users and projected perpendicular to 𝑥𝑦-plane, we define the ray corresponding to 𝑢 as: r𝑢 = (u, 𝑧𝑢 ) + 𝑡 · (0, 0, −1),

(8)

based on (3), where 𝑧𝑢 is large enough to ensure that the ray origin is higher than all occluders 𝑂 ∈ T𝑞 and 𝑡 ∈ [0, 𝑧𝑢 ].

3.2

Theoretical Equivalence and Correctness

To demonstrate that the ray casting formulation faithfully preserves the semantics of R𝑘NN, we define the hit count H𝑞 (r𝑢 ) as the number of occluders intersected by the ray r𝑢 : H𝑞 (r𝑢 ) = 𝑂 ∈ T𝑞 ∃𝑡 ∈ [0, 𝑧𝑢 ] satisfying (4) . (9) Using this definition, our ray casting interpretation becomes equivalent to the classical R𝑘NN condition: 𝑢 ∈ RkNN(𝑞)

⇐⇒

H𝑞 (r𝑢 ) < 𝑘.

(10)

Lemma 3.4 (Correctness of Ray Casting Formulation). For any facility 𝑞 and user 𝑢, let r𝑢 be defined as in Definition (8) and H𝑞 (𝑢) be defined as in Equation (9). Then 𝑢 is a reverse 𝑘 nearest neighbor of 𝑞 if and only if H𝑞 (r𝑢 ) < 𝑘, i.e., Equation (10) holds.

B0 B1

Oa:q c b a Bc:q

q Ba:q

Ob:q

Oc:q

Figure 4: Equivalence between classical R𝑘NN with raycasting-based formulation(𝑘 = 2) . Half-space pruning (left). Ray casting formulation (right). Proof. Consider the perpendicular bisector between 𝑞 and any competing facility 𝑓 . Consistent with concepts used in related work, the invalid side of this bisector is precisely the region in which 𝑓 is closer to 𝑢 than 𝑞. Whenever a ray r𝑢 cast from 𝑢 perpendicularly to the user plane intersects the occlusion triangle, it means 𝑢 lies in a space indicating that 𝑓 is strictly closer to 𝑢 than 𝑞. Each intersection counted in H𝑞 (r𝑢 ) therefore corresponds to one distinct facility is closer than 𝑞 with respect to 𝑢. Therefore, if H𝑞 (r𝑢 ) ≥ 𝑘, then at least 𝑘 facilities are closer to 𝑢 than 𝑞, so 𝑞 cannot be among the 𝑘 nearest neighbors of 𝑢, implying 𝑢 ∉ RkNN(𝑞). Conversely, if H𝑞 (𝑢) < 𝑘, then fewer than 𝑘 facilities closer than 𝑞 for 𝑢, meaning that 𝑞 is within the 𝑘 nearest facilities to 𝑢, and therefore 𝑢 ∈ RkNN(𝑞). This completes the proof. □ Figure 4 shows the equivalence between classical R𝑘NN’s halfspace pruning and our ray casting formulation using an example of finding R𝑘NN of facility 𝑞 with competitor facilities 𝑎, 𝑏, and 𝑐. The shaded area in the figure on the left demonstrates the pruned space under two invalid sides of bisectors, which corresponds to the regions shaded with two or more gray levels in figure on the right, which demonstrates an area covered by at least two occluders in a top-down view. Users like 𝑢 that lie in these areas can be filtered directly.

3.3

Data Indexing and Proposed Algorithm

However, in our ray casting formulation, solving Möller–Trumbore intersection tests in Equation (5) for all ray–primitive pairs are impractical as the number of rays and primitives increases. To address this, we apply a well-established technique in computer graphics, bounding volume hierarchy (BVH) [34], to index the primitives, which significantly reduces the number of intersection tests. A BVH is a tree data structure that organizes geometric primitives into a hierarchy of nested bounding volumes, typically axis-aligned bounding boxes (AABBs). Each node in the tree represents an AABB that contains either a group of child AABBs or primitives. This structure allows the ray–primitive intersection test to be performed as an efficient single-path ray traversal over the BVH. Figure 5 illustrates a BVH constructed for a 2D scene containing four distinct triangle primitives. For example, if a ray intersects primitive C, the traversal path to locate the intersection would be 𝐵0 → 𝐵2 → 𝐵5 → 𝐶. Notably, a ray may intersect multiple primitives, so its traversal path through the scene is not necessarily

B5 B2

B0 B1

u Bb:q

D A

Figure 5: A BVH example (right) corresponding to a 2D scene (left) with four distinct triangle primitives (A, B, C, and D). The tree nodes, labeled B0 to B6, represent the corresponding AABBs in the 2D space. Primitives always appear as leaf nodes in the BVH.

linear. In a 3D scene, the BVH is typically built by recursively dividing the space along the longest axis, creating two subspaces and forming corresponding AABBs. Compared with R-trees and their variants, BVHs are preferred for ray casting because their hierarchical structure is designed specifically to optimize ray–primitive intersection queries. In a BVH, the bounding volumes of sibling nodes do not overlap, which ensures that each primitive resides in exactly one leaf node and prevents redundant traversal of the same geometry. This non-overlapping organization allows rays to move through a clean and efficient hierarchy without repeated tests. In addition, BVH traversal follows a simple and predictable pattern in which the algorithm descends the hierarchy, tests bounding volumes, and prunes subtrees that cannot be intersected. These properties make BVHs highly efficient for processing the millions of rays issued in modern graphics workloads and a natural fit for ray casting applications. Algorithm 1 summarizes our graphics ray casting approach for processing R𝑘NN queries. The computation proceeds in two phases: scene construction, where occluders associated with facilities are embedded into a 3D representation; and ray casting, where rays representing users are issued to determine whether each user can be pruned. During scene construction (Lines 1–8), for each facility 𝑓 ∈ 𝐹 \ {𝑞}, we compute the perpendicular bisector with 𝑞 and encode the invalid side as occlusion triangles following Definition 3.1. To avoid constructing unnecessary occluders and to eliminate the need for a candidate verification phase after filtering like SIX [50], TPL [51] and SLICE [63], we apply InfZone-style pruning [8]: once a facility’s occluder is already fully covered by 𝑘 previously constructed occluders, it is discarded because no ray can reach it. This pruning significantly reduces the number of remaining facilities, denoted 𝑚 ≪ |𝐹 |, and enables full utilization of the GPU during ray casting rather than falling back to CPU-based candidate verification. The construction of occluders requires 𝑂 (𝑚), while the pruning logic contributes 𝑂 (𝑚 2 ), dominated by intersection calculations between bisectors. A BVH is then built over the resulting scene T𝑞 . Unlike facility R-trees used in prior work, which can be reused across different queries, the BVH structure must be rebuilt for each query because the occlusion geometry depends on the specific query facility. While BVH construction could be amortized when the facility set is stable, similar strategies could equally benefit TPL and InfZone via cached bisector sets; for fairness, we apply

Algorithm 1 RT-RkNN Query for Facility 𝑞.

Algorithm 2 RT-RkNN Implementation using OptiX.

Input: Facility 𝑞; user set 𝑈 ; facility set 𝐹 ; pruning threshold 𝑘. Output: RkNN users set of facility 𝑞: R𝑞 .

Input: The constructed scene T𝑞 , scene height 𝑚. Output: User verification result 𝑖𝑠𝑅𝑘𝑁 𝑁 .

1: Scene Construction: Construct occluders.

1: procedure Ray Generation

2: B𝑞 ← 𝐼𝑛𝑓 𝑍𝑜𝑛𝑒_𝑝𝑟𝑢𝑛𝑖𝑛𝑔(𝑞, 𝐹, 𝑘).

3: T𝑞 ← ∅

4: for each facility 𝑓 ∈ B𝑞 do

Build occluder 𝑂 𝑓 :𝑞 based on Definition 3.1. T𝑞 ← T𝑞 ∪ 𝑂 𝑓 :𝑞 7: end for 8: Build a BVH over T𝑞 . 5: 6:

9: Ray Casting: Count intersections along user rays.

𝑡 min, 𝑡 max ← {0, 𝑚 + 1} 𝑢 ← optixGetLaunchIndex() 4: o ← (𝑢𝑥 , 𝑢 𝑦 , 𝑚 + 1) 5: d ← (0, 0, −1) 6: 𝑐←0 7: 𝑖𝑠𝑅𝑘𝑁 𝑁 ← TRUE 8: optixTrace(T𝑞 , o, d, 𝑡 min, 𝑡 max, payloads(𝑐, 𝑖𝑠𝑅𝑘𝑁 𝑁 )) 9: end procedure

10: R𝑞 ← ∅

10: procedure Any-hit

11: for each user 𝑢 ∈ 𝑈 do

11:

Construct a ray r𝑢 from 𝑢 based on Definition 8. 13: 𝑐←0 14: Traverse the BVH of T𝑞 . 15: for each occluder 𝑂 intersected by r𝑢 do 16: 𝑐 ←𝑐 +1 17: if 𝑐 ≥ 𝑘 then 18: break {Early exit: user is prunable} 19: end if 20: end for 21: if 𝑐 < 𝑘 then 22: R𝑞 ← R𝑞 ∪ {𝑢} 23: end if 24: end for 25: return R𝑞

12:

no such amortization to any method. As BVH construction typically requires 𝑂 (𝑚 log 𝑚) [53–55], the overall complexity of the scene construction phase becomes 𝑂 (𝑚 2 + 𝑚 log 𝑚). After the scene is built, ray casting begins (Lines 9–24). Each user 𝑢 emits a ray r𝑢 into the scene, and intersections are evaluated accordingly. Early termination is applied: once 𝑘 intersections are detected, the user is pruned (Line 18). Since a single intersection search under BVH traversal has an expected cost of 𝑂 (log 𝑚) [52], processing a ray with at most 𝑘 allowable intersections results in a total expected complexity of 𝑂 (𝑘 log 𝑚) for determining whether the user belongs to the R𝑘NN result. It is worth noting that, unlike prior work that indexes users using an R-tree or its variants, our approach does not index users at all. While this increases the asymptotic cost of the ray casting phase to 𝑂 (𝑘 |𝑈 | log 𝑚), it enables full exploitation of parallelism, allowing all rays to be processed independently, especially by GPUs associated with RT cores and yielding substantial performance benefits in practice.

3.4

𝑐 ←𝑐 +1 if𝑐 < 𝑘 then 13: optixIgnoreIntersection() 14: else 15: 𝑖𝑠𝑅𝑘𝑁 𝑁 ← FALSE 16: optixTerminateRay() 17: end if 18: end procedure

different rays typically produce different numbers of ray–primitive intersections, resulting in irregular memory access and divergent control flow that conflict with the SIMT execution model. RT cores address these challenges by providing hardware-accelerated ray– triangle and ray–AABB intersection tests during BVH traversal and by scheduling similar intersection tasks together to reduce divergence and improve throughput. After formulating R𝑘NN queries as ray casting, our algorithm can be implemented on RT cores with relatively modest programming effort using their corresponding APIs. There are several RT APIs, including Nvidia OptiX [42], AMD HIP-RT [33], DirectX Raytracing [35] and Vulkan [26]. All of these APIs share a similar programming model. In this paper, we choose Nvidia OptiX for our implementation due to its cutting-edge performance and strong compatibility with CUDA. It is worth noting that while the implementation in this paper targets Nvidia GPUs’ RT cores, porting the algorithm to AMD GPUs, whose ray tracing hardware is functionally similar, is straightforward. To use OptiX, developers follow a predefined workflow: (1) Create a GPU context. (2) Build a BVH. (3) Create a program pipeline. (4) Build the Shader Binding Table (SBT). (5) Launch rays.

Implementing RT-RkNN using RT cores

To fully leverage hardware acceleration, we implement the proposed formulation algorithm using RT cores. RT cores were originally designed to accelerate ray tracing in computer graphics, a more complex form of ray casting that incorporates effects such as reflection, refraction, and shadows. Before it was introduced, ray tracing was difficult to scale on GPUs because

A context is first created to associate OptiX with a specific CUDA device. In step (2), a BVH corresponding to the scene is constructed. The program pipeline in step (3) consists of several programmable stages: • Ray generation: The entry point to the pipeline, defines the ray by origin point o and direction d based on equation (3).

• Intersection: Implements a ray-primitive intersection test, invoked during BVH traversal. Programmers do not need to implement it when using the default hardware intersection test. • Any-hit: Called when a new, potentially closest intersection of a ray is found. Not necessary when only the closest intersection is counted. • Closest-hit: Called when the ray finds the closest intersection. • Miss: Called after confirming a ray does not hit any primitive in the scene. OptiX uses a single ray programming model [42], where each ray executes this pipeline independently. The SBT constructed in step (4) links primitives with their associated programs and serves as the binding layer between rays and scene behavior. Finally, rays are launched and will explore the scene based on the program pipeline defined before. As shown in Algorithm 2, our OptiX implementation of ray casting stage is straightforward because the formulated R𝑘NN computation aligns naturally with ray tracing. Only the Ray Generation and Any-hit programs are required. We use Any-hit instead of Closest-hit because we are interested in counting up to 𝑘 intersections per ray rather than identifying the nearest one. The Miss program can be omitted, as no additional processing is required when a ray misses all occluders. The Intersection program is left empty to leverage the default hardware-accelerated triangle intersection routine provided by the RT cores. OptiX will trace the ray just generated by calling optixTrace(). User’s coordinates are embedded in the rays which can be obtained by optixGetLaunchIndex(). The height of the ray origins is set to 𝑚 + 1 to ensure it is higher than all occluders in the scene. During traversal, once 𝑐 reaches 𝑘, the ray is terminated early using optixTerminateRay(). Otherwise, intermediate intersections invoke optixIgnoreIntersection(), allowing traversal to continue. Under OptiX’s single ray programming model, the Ray Generation program launches one ray per user and stores both the intersection count 𝑐 and the user verification result isRkNN via OptiX payloads variables.

EVALUATION

This section outlines the experimental setup and reports performance with detailed analysis.

4.1

Experimental Setup

System: We compare our RT-RkNN approach against three baseline algorithms introduced in subsection 2.2: TPL, InfZone, and SLICE. In the figures, InfZone is abbreviated as INF, and our RT-RkNN method is abbreviated as RT for clarity. All algorithms were implemented from scratch, using shared common routines for comparable operations. To emphasize query-time efficiency, all baselines use R*-trees rather than standard R-trees, providing a stronger query-time foundation for the competing methods. The only exception is the BVH, which is constructed exclusively for our RT-RkNN method. Implementations are written in C++11 and compiled using NVCC 12.4 with -O2 flag, and OptiX 7.7 enabled where applicable. Experiments were conducted on a workstation equipped with an AMD EPYC 7453 28-core CPU, 512 GB of system memory, and an Nvidia RTX A6000 GPU with 48 GB of GPU memory, running Ubuntu 22.04.5 LTS.

(a) NY

(b) FLA

Figure 6: Visualization of datasets. Table 1: Six real-world road-network datasets. Symbol

Description

Number of Points

USA CTR E CAL FLA NY

Full USA Central USA Eastern USA California and Nevada Florida New York City

23,947,347 14,081,816 3,598,623 1,890,815 1,070,376 264,346

Table 2: Amortized user indexing cost in dataset USA Algorithms All baselines RT-RkNN (ours)

Operation

Runtime (s)

R*-tree construction Plain GPU transfer

147.241 0.010251

Datasets: We use six real-world road-network datasets covering New York City (NY), Florida (FLA), California and Nevada (CAL), Eastern USA (E), Central USA (CTR), and the full USA (USA). These datasets contain between 264,346 and 23,947,347 points and were obtained from the DIMACS repository [13]. The spatial distributions of representative datasets are visualized in Figure 6, and detailed statistics are provided in Table 1. Evaluation Configurations: Following prior work, we vary 𝑘 from 1 to 25 (default 𝑘 = 10), with additional values up to 200 to examine large-𝑘 scalability. We use two facility settings: a default setting of 1,000 randomly selected facilities (aligning with existing baselines) and a sparse setting of 100 facilities (representing sparse facility distributions). For both settings, except for points selected as facilities, all remaining points are used as users. Results are averaged over 100 random queries for the sparse setting and 1,000 queries for settings with 1,000 or more facilities, ensuring statistical robustness and consistency. All algorithms (including RT-RkNN) follow a twostage execution model whose stage names and internal logic differ across methods; we adopt the convention of [62], calling the first stage filtering and the second verification, to enable direct runtimebreakdown comparisons across algorithms.

4.2

Amortized Operation Costs

In all baseline algorithms, R*-trees built over facilities and users are amortized across queries and thus excluded from the performance

Figure 7 and Figure 8 analyze the impact of 𝑘 on runtime under the sparse facility and default facility settings, respectively. Although only a subset of datasets is shown, all datasets exhibit the same overall trend. Under the sparse facility setting, RT-RkNN consistently outperforms all baseline algorithms except when 𝑘 = 1, where all methods complete in approximately 3 ms. Under the default facility density, where baseline algorithms benefit from stronger spatial pruning opportunities, RT-RkNN still outperforms TPL and InfZone across all tested values of 𝑘. Even when compared with SLICE, which is known to be more resilient to increases in 𝑘, RT-RkNN begins to outperform it once 𝑘 reaches 10–20. For the extremely large 𝑘 setting, we only compare RT-RkNN with SLICE on our largest dataset USA. Figure 9 illustrates that for extremely large 𝑘 scenarios, our RT-RkNN outperforms the state-of-the-art algorithm SLICE in all cases. Remarkably, our RT-RkNN achieves up to 16.4× speedup over SLICE, 34.6× over InfZone, and as much as 54.7× over TPL when |𝐹 | = 100 and 𝑘 = 25 on the CAL dataset. This result reflects the issue discussed in subsection 2.2: as 𝑘 increases, pruning-based methods lose pruning effectiveness, resulting in larger candidate sets and substantially more verification work. In contrast, for RT-RkNN, increasing 𝑘 simply allows a ray to continue traversal rather than terminating early. The algorithm, therefore, degrades gracefully, requiring only additional intersection counting while still benefiting from hardware acceleration. Consequently, the impact of larger 𝑘 values on runtime remains modest compared with traditional approaches.

4.4

Impact of Varying Data Sizes

We study the impact of data size on each algorithm using all 6 datasets, which span a wide range of scales, with the largest dataset (USA) being about 100 times larger than the smallest (NY), under both the sparse facility and default facility settings. In a sparse facility setting, as shown in Figure 10a, our RT-RkNN outperforms all baselines across all datasets. Its runtime increases only slowly as data size grows, demonstrating the effectiveness of our algorithm with massively parallel ray–primitive intersection processing on GPU RT cores. In contrast, the performance of baseline algorithms degrades substantially once the dataset exceeds approximately 10 million points (datasets E and USA), reflecting their limited scalability under large input sizes. Figure 10b shows that under the

Runtime (ms)

TPL INF SLICE RT(ours)

400

300 200 100 0

(b) CAL (setting |𝐹 | = 100)

Figure 7: Impact of varying 𝑘 on runtime in sparse facility setting. 120 100 80 60 40 20 0

800

TPL INF SLICE RT(ours)

Runtime (ms)

Impact of Varying k Settings

TPL INF SLICE RT(ours)

(a) NY (setting |𝐹 | = 100)

Runtime (ms)

4.3

70 60 50 40 30 20 10 0

TPL INF SLICE RT(ours)

600 400 200 0

(a) E (setting |𝐹 | = 1000)

(b) USA (setting |𝐹 | = 1000)

Figure 8: Impact of varying 𝑘 settings on runtime using the default facility setting.

Runtime (ms)

scaling analysis. RT-RkNN likewise benefits from amortization: although it constructs a facility R*-tree to support InfZone-style pruning during scene construction, it does not require a user R*tree. Instead, the user set is uploaded once to GPU memory and reused throughout the workload. The same applies to OptiX context and program pipeline creation, which is amortizable and trivial. Although amortizable costs do not contribute to per-query scalability, they remain relevant when comparing overall preprocessing burden across algorithms, especially in workloads with short query sequences. As shown in Table 2, RT-RkNN incurs significantly less indexing overhead than the baselines while retaining the advantages of amortized preprocessing, making it comparatively lightweight in preprocessing cost.

7000 6000 5000 4000 3000 2000 1000 0

SLICE RT(ours)

100

125

150

175

200

Figure 9: Impact of large 𝑘 on runtime in default facility setting (|𝐹 | = 1000) of USA dataset.

default facility setting, where spatial pruning remains highly effective, RT-RkNN does not outperform SLICE. This is primarily due to the additional overhead introduced by data transfer between main memory and GPU memory.

4.5

Impact of Varying Facility Cardinality

In this section, we fix the number of users to 1 million for CAL and 10 million for USA, and vary the facility cardinality |𝐹 | to study its impact on performance. From Figure 11, we observe that RT-RkNN maintains nearly constant performance across all datasets, regardless of the number of facilities. In contrast, the baseline algorithms improve significantly as |𝐹 | grows, benefiting from effective spatial pruning. From Figure 12, we observe that in both cases, the verification phase of the baseline algorithms becomes significantly faster as the facility cardinality increases, while RT-RkNN maintains a stable verification cost. The flat performance curve of RT-RkNN occurs because all computation that can benefit from GPU parallelism is already highly optimized, while the remaining overhead involved

76.1

USA

105

102

103

|F|

104

64.8

Filtering Verification

Runtime (ms)

37.7

|F|

1.96

3.98

L 0.63 INF 0.97

100000 SL

3.96

1.44

INF

ICE 0.82

10000 SL

1.58

3.84

1000

2.67

ICE

9.00

L INF

100

ICE

(b) Default facility setting.

(a) CAL (|𝑈 | = 106 ) 700

697

Figure 10: Impact of data size on runtime in sparse (|𝐹 | = 100) and default (|𝐹 | = 1000) facility setting.

5.64

20.7 3.75

USA

L INF

CTR

77.4 42.7

TP L IN SL F ICE RT

datasets

105

(b) USA (|𝑈 | = 107 )

TP L IN SL F ICE RT

CAL

TP L IN SL F ICE RT

FLA

TP 16.6 L IN 10.3 SL F ICE 4.65 RT 4.63

TP L 9.15 IN 6.01 SL F ICE 3.20 RT 3.46

TP L IN SL F ICE RT

3.13 2.34 1.21 2.08

30.8 17.5 7.65 7.31

28.4 45.9

61.7

100

104

101

125

|F|

Figure 11: Total runtime under varying cardinality for datasets CAL (|𝑈 | = 106 ) and USA (|𝑈 | = 107 ).

188

Filtering Verification 113

Runtime (ms)

150

103

(a) CAL (|𝑈 | = 106 )

(a) Sparse facility setting. 175

102

CTR

10 0

TPL INF SLICE RT(ours)

ICE

datasets

TP L IN SL F ICE RT

CAL

TP 220 L IN 132 SL F ICE 60.3 RT 6.74

FLA

TP L 118 IN 68.2 SL F ICE 35.6 RT 4.02

TP 68.1 L IN 41.2 SL F ICE 18.8 RT 2.83

TP 17.7 L IN 9.91 SL F ICE 4.86 RT 1.54

400

445

800 600

Runtime (ms)

700 600 500 400 300 200 100 0

Runtime (ms)

1558

1000

200

TPL INF SLICE RT(ours)

837

1200

Filtering Verification

TP L IN 506 SL F ICE 299 RT 47.0

Runtime (ms)

1400

965

1600

Filtering Verification

Runtime (ms)

600

384

500 400

4.6

Impact of Varying User Cardinality

In this section, we fix the number of facilities using both the sparse and default facility settings for the USA dataset, and vary the user cardinality |𝑈 | to examine its impact on performance. All algorithms perform well when the number of users is small. However, performance degrades for every method as the user population becomes large. In the sparse facility setting, as shown in Figure 13a, RT-RkNN maintains strong performance even with very large user populations of up to 107 points, outperforming the baseline algorithms by a substantial margin. In the default facility setting, as illustrated in Figure 13b, RT-RkNN still does not surpass SLICE. As shown in Figure 14, in the sparse setting, RT-RkNN achieves the best performance due to its highly efficient verification phase, which benefits from massive GPU parallelization. However, this advantage does not carry over to the default facility setting, where SLICE becomes faster but RT-RkNN experiences performance degradation, especially when |𝑈 | reaches 107 due to the additional overhead introduced by GPU data transfer. Nonetheless, although RT-RkNN does not outperform SLICE in every scenario, the performance

226

300

RT 33.7

ICE 2.43

100000 SL

10000 SL

|F|

TP 2.06 L INF 1.59

RT 33.7

ICE 3.26

TP 11.0 L INF 6.15

36.0

ICE 23.5

84.9

46.1

1000 SL

100

L INF

ICE

L INF

100

RT 33.6

200

by the GPU RT cores pipeline, is inherently difficult to parallelize and therefore does not improve with larger facility sets. As a result, RT-RkNN remains largely unaffected by increases in |𝐹 |, whereas pruning-based methods gain efficiency from having more facilities. For monochromatic R𝑘NN queries, where the query point and candidate points originate from the same set, spatial relationships tend to be more structured, providing a more favorable environment for spatial pruning as shown here. Under these conditions, RT-RkNN does not surpass the SLICE algorithm, which benefits greatly from strong pruning effectiveness.

(b) USA (|𝑈 | = 107 )

Figure 12: Breakdown of filtering and verification time under varying facility cardinality for datasets CAL (|𝑈 | = 106 ) and USA (|𝑈 | = 107 ).

gap in the default facility setting is relatively small compared to the substantial advantages RT-RkNN achieves in the sparse facility setting.

4.7

Runtime Breakdown Analysis

In this section, we provide a breakdown analysis of RT-RkNN to examine its advantages and limitations. According to the OptiX workflow, the Scene Construction stage can be divided into two components: occluder construction and BVH construction. Although the size of the Shader Binding Table (SBT) also depends on the scene configuration, we do not include the SBT construction time in our analysis, because RT-RkNN only requires hit or miss information and does not rely on per-primitive attributes, making SBT construction trivial. In practice, SBT setup takes approximately 0.062 ms even for the largest scene where |𝐹 | = 107 , which is negligible compared to the other costs. Then, Ray Casting stage is divided into ray tracing

TPL INF SLICE RT(ours)

Table 3: Average occluder counts of different occluder construction strategies in different facility cardinality.

TPL INF SLICE RT(ours)

80 60

Runtime (ms)

700 600 500 400 300 200 100 0

40 20

103

104

106

105

|U|

107

(a) Sparse facility setting.

103

104

106

105

|U|

107

693

Filtering Verification

Runtime (ms)

600

382

500 400

169

300

34.0

TP L INF SL ICE RT

105

TP 65.2 L INF 36.9 SL ICE 14.4 RT 4.25

104

TP 6.43 L INF 3.97 SL ICE 1.22 RT 1.54

103

TP 0.83 L INF 0.67 SL ICE 0.22 RT 1.23

TP 0.15 L INF 0.28 SL ICE 0.12 RT 1.19

200 100

106

|U|

107

84.6

(a) Sparse facility setting. Filtering Verification

Runtime (ms)

46.0

33.7

50 40

9.19 5.51 2.12 4.23

1.24 1.09 0.54 2.11

0.28 0.53 0.39 1.80

0.12 0.42 0.36 1.78

17.0

|U|

106

ICE RT

L INF

ICE RT

L INF

ICE RT

105

104

L INF

ICE RT

L INF

ICE RT

L INF

103

107

(b) Default facility setting.

Figure 14: Breakdown of filtering and verification time under varying user cardinality for the USA dataset in sparse and default facility settings.

Occluder Construction BVH Construction Ray Tracing Data Transfer

2.0 1.5 1.0 0.5

103

104

105

|U|

106

107

(a) USA (|𝐹 | = 1000, 𝑘 = 10)

|𝐹 | = 104

37.27 49.54 99

46.34 83.04 999

48.44 205.34 9999

0.0

We fix |𝐹 | = 103 and vary |𝑈 | from 103 to 107 to evaluate how user cardinality affects the performance of RT-RkNN on the USA dataset. Since the facility set is fixed, the constructed scene remains identical across all experiments. As shown in Figure 15a, RT cores sustain high ray tracing efficiency until the user population reaches approximately one million. However, when |𝑈 | increases to ten million, ray tracing time and data transfer time begin to dominate. This is expected because 107 rays exceed the number that the GPU can process concurrently, causing some rays to wait while others are executed. It is important to note that data transfer constitutes pure overhead, influenced solely by user cardinality. When |𝑈 | = 107 , data transfer accounts for more than half of the total runtime. This overhead becomes particularly significant in dense facility settings, where baseline algorithms achieve efficient R𝑘NN computation with small 𝑘. This explains why RT-RkNN cannot outperform SLICE on very large datasets under default facility densities. We then fix |𝑈 | = 105 and vary |𝐹 | from 102 to 105 to evaluate how facility cardinality affects the performance of RT-RkNN on the CAL dataset. The user cardinality is restricted to 105 to ensure that the Ray Casting stage does not dominate the overall runtime. As |𝐹 | increases, the occluder construction time initially grows and reaches its peak around |𝐹 | = 104 . Beyond this point, the construction time stabilizes or even slightly decreases because InfZone-style pruning removes most unnecessary occluders. This also explains why BVH construction time and ray tracing time remain largely unaffected by changes in |𝐹 |.

4.8

Impact of Different Occluder Counts

In this section, we investigate how the number of occluders affects the performance of RT-RkNN. As introduced earlier, we apply InfZone-style pruning to avoid constructing unnecessary occluders. However, in practice, we observe that when the facility set is small, constructing all occluders without pruning can actually be faster due to simpler control flow and better data locality. Motivated by this observation, we conduct supplementary experiments comparing three occluder construction strategies:

Runtime (ms)

35 30 25 20 15 10 5 0

|𝐹 | = 103

(b) Default facility setting.

Figure 13: Total runtime under varying facility cardinality for sparse and default facility setting of dataset USA. 700

InfZone-style Conservative Non-pruning

|𝐹 | = 102

102

103

|F|

104

105

(b) CAL (|𝑈 | = 105 , 𝑘 = 10)

Figure 15: Runtime breakdown analysis under configurations with fixed |𝑈 | and fixed |𝐹 |.

and data transfer, which copies the ray tracing result back to the main memory from the GPU.

• InfZone-style pruning: The original pruning strategy introduced by InfZone, which aggressively removes as many unnecessary occluders as possible, with 𝑂 (𝑚 2 ) complexity. • Conservative pruning: InfZone-style pruning is applied only for the first few occluders (e.g., the first 20). Beyond that, a lightweight conservative test based on Equation (1) is used. Although not optimal, this approach still prunes most unnecessary occluders while substantially reducing pruning overhead. • Non-pruning: As the name suggests, this strategy constructs all occluders without any pruning.

119.4

15.0 12.5

12.1

Occluder Construction BVH Construction Ray Tracing

17.5

10.0

3.65

1.86

1.97

1.69

2.5

1.89

5.0

1.48

7.5

1.33

Runtime (ms)

800

Runtime (ms)

20.0

1000

|F|

tiv e pru No nin n g

The average occluder count produced by each pruning strategy under different facility cardinalities on the NY dataset is reported in Table 3, and the corresponding performance results are shown in Figure 16. Since our goal is to examine performance variations attributable specifically to the number of occluders, Figure 16 includes only the components directly affected: Occluder Construction, BVH Construction, and Ray Tracing. We observe that Ray Tracing is not strongly affected by changes in the occluder count, except for the non-pruning strategy when |𝐹 | = 9999, which strongly complicates the scene for a ray to traverse (did not show in figure for clarity of other settings). This is because the NY dataset has a relatively small user cardinality, allowing rays to be processed with high parallel efficiency. The No-pruning strategy constructs occluders very quickly. However, the resulting large number of occluders significantly slows down subsequent stages, ultimately making it the slowest among all strategies even in a sparse facility setting. For Conservative pruning, although it removes approximately 98% of unnecessary occluders when |𝐹 | = 104 , the remaining occluders still constitute roughly four times the number produced by InfZone-style pruning. While Conservative pruning is slightly faster than InfZone-style pruning in the Occluder Construction stage, this advantage is offset during BVH construction, resulting in inferior overall performance. Consequently, InfZone-style pruning emerges as the most effective strategy for Scene Construction, providing the shortest total runtime and lower GPU memory usage.

4.9

600 506

400

370 224 132

erv a

Inf

10000

Figure 16: Impact of occluder counts on runtime under the default New York facility configuration.

Performance Evaluation w/o RT Cores

Since no publicly available GPU-based R𝑘NN algorithms exist, we implement a GPU baseline, termed InfZone-GPU, which directly offloads InfZone’s verification phase to the GPU without using RT cores. We choose InfZone because it is the only baseline that produces no false positives, thereby eliminating the need for additional user verification and allowing most computation to remain on the GPU. We also include the original InfZone algorithm in our comparison to demonstrate the computational advantage provided by GPU execution. On one hand, from Figure 17, we observe that InfZone-GPU outperforms the original CPU-based InfZone across all datasets, demonstrating the GPU’s substantial computing power even when the verification phase contains significant control divergence and

837

200

tiv e pru No nin n g

erv a ns

100

Inf

tiv e pru No nin n g

erv a

Inf

0.0

RT-RkNN(ours) InfZone-GPU InfZone

1.54 4.80 9.91

3.91 20.3

FLA

41.2

4.02

33.7

CAL

68.2 7.31

Datasets

59.4

77.4

45.9

CTR

USA

Figure 17: Performance comparison between RT-RkNN, GPUbased InfZone without RT cores, and CPU-based InfZone in the sparse facility setting of the NY dataset.

irregular memory accesses that are poorly aligned with the SIMT execution model. On the other hand, RT-RkNN consistently outperforms InfZoneGPU across all datasets. As data size increases, the performance gap widens: InfZone-GPU degrades rapidly due to the growing control divergence across users during verification, whereas RT-RkNN maintains stable scaling behavior. This is because RT-RkNN leverages dedicated hardware intersection testing in RT cores, which eliminates the need for branch-heavy verification logic and drastically reduces control divergence. These results demonstrate that our ray casting formulation, which enables algorithm fit for RT cores hardware acceleration, is essential for achieving high performance in GPU-based R𝑘NN computation.

CONCLUSIONS AND FUTURE WORK

In this paper, we presented RT-RkNN, which formulates R𝑘NN as graphics ray casting by modeling users as rays and facilities as occluders, establishing a formal equivalence between spatial pruning and ray–primitive intersection. Building on this, we design the first algorithm directly exploiting GPU RT cores for hardwareaccelerated intersection testing and BVH traversal. Experiments on real-world datasets with up to more than 23 million points show that RT-RkNN significantly outperforms state-of-the-art algorithms, especially where traditional pruning becomes ineffective: sparse facility distributions, large user populations, and large 𝑘. RT-RkNN also eliminates user indexing, cutting preprocessing overhead while enabling massive parallelism across all user rays. For future work, we plan to explore four directions: (1) adapting the approach for dynamic and continuous R𝑘NN queries where facilities or users change over time; (2) investigating batched query processing to amortize scene construction costs across multiple query facilities; (3) exploring hybrid strategies that dynamically select between RT-RkNN and traditional pruning based on data characteristics; and (4) implementing and evaluate this formulation on other RT hardware.

ACKNOWLEDGMENTS This work was supported in part by JSPS KAKENHI Grant Number JP24K20782.

REFERENCES [1] Elke Achtert, Hans-Peter Kriegel, Peer Kröger, Matthias Renz, and Andreas Züfle. 2009. Reverse k-nearest neighbor search in dynamic and general metric databases. In Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology (Saint Petersburg, Russia) (EDBT ’09). Association for Computing Machinery, New York, NY, USA, 886–897. https://doi.org/10.1145/1516360.1516462 [2] Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger. 1990. The R*-tree: an efficient and robust access method for points and rectangles. In Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data (Atlantic City, New Jersey, USA) (SIGMOD ’90). Association for Computing Machinery, New York, NY, USA, 322–331. https: //doi.org/10.1145/93597.98741 [3] Rimantas Benetis, S. Jensen, Gytis Karundefinediauskas, and Simonas undefinedaltenis. 2006. Nearest and reverse nearest neighbor queries for moving objects. The VLDB Journal 15, 3 (Sept. 2006), 229–249. https://doi.org/10.1007/ s00778-005-0166-4 [4] Thomas Bernecker, Tobias Emrich, Hans-Peter Kriegel, Matthias Renz, Stefan Zankl, and Andreas Züfle. 2011. Efficient probabilistic reverse nearest neighbor query processing on uncertain data. Proc. VLDB Endow. 4, 10 (July 2011), 669–680. https://doi.org/10.14778/2021017.2021024 [5] Avory Bryant and Krzysztof Cios. 2018. RNN-DBSCAN: A Density-Based Clustering Algorithm Using Reverse Nearest Neighbor Density Estimates. IEEE Transactions on Knowledge and Data Engineering 30, 6 (2018), 1109–1121. https: //doi.org/10.1109/TKDE.2017.2787640 [6] S. Cabello, J.M. Díaz-Báñez, S. Langerman, C. Seara, and I. Ventura. 2010. Facility location problems in the plane based on reverse nearest neighbor queries. European Journal of Operational Research 202, 1 (2010), 99–106. https: //doi.org/10.1016/j.ejor.2009.04.021 [7] Muhammad Aamir Cheema, Xuemin Lin, Wei Wang, Wenjie Zhang, and Jian Pei. 2010. Probabilistic Reverse Nearest Neighbor Queries on Uncertain Data. IEEE Transactions on Knowledge and Data Engineering 22, 4 (2010), 550–564. https://doi.org/10.1109/TKDE.2009.108 [8] Muhammad Aamir Cheema, Xuemin Lin, Wenjie Zhang, and Ying Zhang. 2011. Influence zone: Efficiently processing reverse k nearest neighbors queries. In 2011 IEEE 27th International Conference on Data Engineering. 577–588. https: //doi.org/10.1109/ICDE.2011.5767904 [9] Muhammad Aamir Cheema, Xuemin Lin, Ying Zhang, Wei Wang, and Wenjie Zhang. 2009. Lazy updates: an efficient technique to continuously monitoring reverse kNN. Proc. VLDB Endow. 2, 1 (Aug. 2009), 1138–1149. https://doi.org/10. 14778/1687627.1687755 [10] Muhammad Aamir Cheema, Wenjie Zhang, Xuemin Lin, and Ying Zhang. 2012. Efficiently processing snapshot and continuous reverse k nearest neighbors queries. The VLDB Journal 21, 5 (2012), 703–728. [11] Muhammad Aamir Cheema, Wenjie Zhang, Xuemin Lin, Ying Zhang, and Xuefei Li. 2012. Continuous reverse k nearest neighbors queries in euclidean space and in spatial networks. The VLDB Journal 21, 1 (2012), 69–95. [12] Farhana Choudhury, J Shane Culpepper, Timos Sellis, and Xin Cao. 2016. Maximizing bichromatic reverse spatial and textual k nearest neighbor queries. In 42nd International Conference on Very Large Data Bases. VLDB Endowment Inc., 456–467. [13] DIMACS. 2006. 9th DIMACS Implementation Challenge - Shortest Paths. https: //www.diag.uniroma1.it/~challenge9/download.shtml. Accessed: 2025-11-24. [14] Tobias Emrich, Hans-Peter Kriegel, Peer Kröger, Matthias Renz, Naixin Xu, and Andreas Züfle. 2010. Reverse k-Nearest Neighbor monitoring on mobile objects. In Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems (San Jose, California) (GIS ’10). Association for Computing Machinery, New York, NY, USA, 494–497. https://doi.org/10.1145/ 1869790.1869870 [15] Epic Games. 2021. Ray Tracing Features Settings. https://dev. epicgames.com/documentation/en-us/unreal-engine/ray-tracing-featuressettings?application_version=4.27. Accessed 2025-11-21. [16] Liang Geng, Rubao Lee, and Xiaodong Zhang. 2024. RayJoin: Fast and Precise Spatial Join. In Proceedings of the 38th ACM International Conference on Supercomputing (Kyoto, Japan) (ICS ’24). Association for Computing Machinery, New York, NY, USA, 124–136. https://doi.org/10.1145/3650200.3656610 [17] Liang Geng, Rubao Lee, and Xiaodong Zhang. 2025. LibRTS: A Spatial Indexing Library by Ray Tracing. In Proceedings of the 30th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (Las Vegas, NV, USA) (PPoPP ’25). Association for Computing Machinery, New York, NY, USA, 396–411. https://doi.org/10.1145/3710848.3710850 [18] Parisa Ghaemi, Kaveh Shahabi, John P. Wilson, and Farnoush Banaei-Kashani. 2012. Continuous maximal reverse nearest neighbor query on spatial networks. In Proceedings of the 20th International Conference on Advances in Geographic Information Systems (Redondo Beach, California) (SIGSPATIAL ’12). Association for Computing Machinery, New York, NY, USA, 61–70. https://doi.org/10.1145/ 2424321.2424330

[19] Yusuke Gotoh and Chiori Okubo. 2016. A Searching Method for Bichromatic Reverse k-Nearest Neighbor with Network Voronoi Diagram. In Proceedings of the 14th International Conference on Advances in Mobile Computing and Multi Media (Singapore, Singapore) (MoMM ’16). Association for Computing Machinery, New York, NY, USA, 71–78. https://doi.org/10.1145/3007120.3007133 [20] Antonin Guttman. 1984. R-trees: a dynamic index structure for spatial searching. In Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data (Boston, Massachusetts) (SIGMOD ’84). Association for Computing Machinery, New York, NY, USA, 47–57. https://doi.org/10.1145/602259.602266 [21] Justus Henneberg and Felix Schuhknecht. 2023. RTIndeX: Exploiting HardwareAccelerated GPU Raytracing for Database Indexing. Proceedings of the VLDB Endowment 16, 13 (2023), 4268–4281. [22] Lihua Hu, Hongkai Liu, Jifu Zhang, and Aiqin Liu. 2021. KR-DBSCAN: A densitybased clustering algorithm based on reverse nearest neighbor and influence space. Expert Systems with Applications 186 (2021), 115763. [23] Pengfei Jin, Lu Chen, Yunjun Gao, Xueqin Chang, Zhanyu Liu, Shu Shen, and Christian S Jensen. 2023. Maximizing the influence of bichromatic reverse k nearest neighbors in geo-social networks. World Wide Web 26, 4 (2023), 1567– 1598. [24] Jen Joynt. 2022. California Hospitals Almanac — 2022 Edition. Technical Report. California Health Care Foundation. https://www.chcf.org/resource/californiahospitals-almanac/ Accessed: 2025-11-19. [25] James M. Kang, Mohamed F. Mokbel, Shashi Shekhar, Tian Xia, and Donghui Zhang. 2007. Continuous Evaluation of Monochromatic and Bichromatic Reverse Nearest Neighbors. In 2007 IEEE 23rd International Conference on Data Engineering. 806–815. https://doi.org/10.1109/ICDE.2007.367926 [26] Khronos Group. 2020. Vulkan Ray Tracing Extensions. https://www.khronos. org/blog/vulkan-ray-tracing-final-specification-release. Accessed 2025-11-21. [27] Flip Korn and S. Muthukrishnan. 2000. Influence sets based on reverse nearest neighbor queries. SIGMOD Rec. 29, 2 (May 2000), 201–212. https://doi.org/10. 1145/335191.335415 [28] Yang Li, Mingyuan Bai, Qingfeng Guan, Zi Ming, Xun Liang, Gang Liu, and Junbin Gao. 2023. CSD-RkNN: reverse k nearest neighbors queries with conic section discriminances. International Journal of Geographical Information Science 37, 10 (2023), 2175–2204. [29] King-Ip Lin, M. Nolen, and Congjun Yang. 2003. Applying bulk insertion techniques for dynamic reverse nearest neighbor problems. In Seventh International Database Engineering and Applications Symposium, 2003. Proceedings. 290–297. https://doi.org/10.1109/IDEAS.2003.1214938 [30] Zihan Liu, Wentao Ni, Jingwen Leng, Yu Feng, Cong Guo, Quan Chen, Chao Li, Minyi Guo, and Yuhao Zhu. 2024. JUNO: Optimizing High-Dimensional Approximate Nearest Neighbour Search with Sparsity-Aware Algorithm and RayTracing Core Mapping. In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2 (La Jolla, CA, USA) (ASPLOS ’24). Association for Computing Machinery, New York, NY, USA, 549–565. https://doi.org/10.1145/3620665.3640360 [31] Yangming Lv, Kai Zhang, Ziming Wang, Xiaodong Zhang, Rubao Lee, Zhenying He, Yinan Jing, and X Sean Wang. 2024. Rtscan: Efficient scan with ray tracing cores. Proceedings of the VLDB Endowment 17, 6 (2024). [32] Durga Keerthi Mandarapu, Vani Nagarajan, Artem Pelenitsyn, and Milind Kulkarni. 2024. Arkade: k-Nearest Neighbor Search With Non-Euclidean Distances using GPU Ray Tracing. In Proceedings of the 38th ACM International Conference on Supercomputing (Kyoto, Japan) (ICS ’24). Association for Computing Machinery, New York, NY, USA, 14–25. https://doi.org/10.1145/3650200.3656601 [33] Daniel Meister, Paritosh Kulkarni, Aaryaman Vasishta, and Takahiro Harada. 2024. HIPRT: A Ray Tracing Framework in HIP. Proc. ACM Comput. Graph. Interact. Tech. 7, 3, Article 44 (Aug. 2024), 18 pages. https://doi.org/10.1145/ 3675378 [34] Daniel Meister, Shinji Ogaki, Carsten Benthin, Michael J Doyle, Michael Guthe, and Jiří Bittner. 2021. A survey on bounding volume hierarchies for ray tracing. In Computer Graphics Forum, Vol. 40. Wiley Online Library, 683–712. [35] Microsoft DirectX Team. 2025. DirectX at GDC 2025. https://devblogs.microsoft. com/directx/directx-at-gdc-2025/. Accessed 2025-11-21. [36] Tomas Möller and Ben Trumbore. 2005. Fast, minimum storage ray/triangle intersection (SIGGRAPH ’05). Association for Computing Machinery, New York, NY, USA, 7–es. https://doi.org/10.1145/1198555.1198746 [37] Vani Nagarajan and Milind Kulkarni. 2023. RT-DBSCAN: Accelerating DBSCAN using Ray Tracing Hardware. In 2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 963–973. https://doi.org/10.1109/IPDPS54959. 2023.00100 [38] Vani Nagarajan, Durga Mandarapu, and Milind Kulkarni. 2023. RT-kNNS Unbound: Using RT Cores to Accelerate Unrestricted Neighbor Search. In Proceedings of the 37th ACM International Conference on Supercomputing (Orlando, FL, USA) (ICS ’23). Association for Computing Machinery, New York, NY, USA, 289–300. https://doi.org/10.1145/3577193.3593738 [39] Michael Nwogugu. 2006. Site selection in the US retailing industry. Applied mathematics and computation 182, 2 (2006), 1725–1734.

[40] Office of the New York City Comptroller. 2025. Fast Shipping. Slow Justice: Traffic, Worker, and Climate Hazards in Last Mile Delivery. Technical Report. Office of the New York City Comptroller. https://comptroller.nyc.gov/reports/fast-shippingslow-justice/ [41] Xiao Pan, Shili Nie, Haibo Hu, Philip S. Yu, and Jingfeng Guo. 2022. Reverse Nearest Neighbor Search in Semantic Trajectories for Location-Based Services. IEEE Transactions on Services Computing 15, 2 (2022), 986–999. https://doi.org/ 10.1109/TSC.2020.2968309 [42] Steven G. Parker, James Bigler, Andreas Dietrich, Heiko Friedrich, Jared Hoberock, David Luebke, David McAllister, Morgan McGuire, Keith Morley, Austin Robison, and Martin Stich. 2010. OptiX: a general purpose ray tracing engine. 29, 4, Article 66 (July 2010), 13 pages. https://doi.org/10.1145/1778765.1778803 [43] Franco P Preparata and Michael I Shamos. 2012. Computational geometry: an introduction. Springer Science & Business Media. [44] Milos Radovanovic, Alexandros Nanopoulos, and Mirjana Ivanovic. 2010. Hubs in space: Popular nearest neighbors in high-dimensional data. Journal of Machine Learning Research 11, sept (2010), 2487–2531. [45] Maytham Safar, Dariush Ibrahimi, and David Taniar. 2009. Voronoi-based reverse nearest neighbor query processing on spatial networks. Multimedia systems 15, 5 (2009), 295–308. [46] Shuo Shang, Bo Yuan, Ke Deng, Kexin Xie, and Xiaofang Zhou. 2011. Finding the most accessible locations: reverse path nearest neighbor query in road networks. In Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (Chicago, Illinois) (GIS ’11). Association for Computing Machinery, New York, NY, USA, 181–190. https://doi.org/10.1145/ 2093973.2093999 [47] Mehdi Sharifzadeh and Cyrus Shahabi. 2010. VoR-tree: R-trees with Voronoi diagrams for efficient processing of spatial nearest neighbor queries. Proc. VLDB Endow. 3, 1–2 (Sept. 2010), 1231–1242. https://doi.org/10.14778/1920841.1920994 [48] Xuri Shi, Kai Zhang, X Sean Wang, Xiaodong Zhang, and Rubao Lee. 2025. RayDB: Building Databases with Ray Tracing Cores. Proceedings of the VLDB Endowment 19, 1 (2025), 43–55. [49] Anbang Song, Ziqiang Yu, Wei Liu, Yating Xu, and Mingjin Tao. 2025. BRkNNlight: Batch Processing of Reverse k-Nearest Neighbor Queries for Moving Objects on Road Networks. In Proceedings of the 19th International Symposium on Spatial and Temporal Data (SSTD ’25). Association for Computing Machinery, New York, NY, USA, 80–89. https://doi.org/10.1145/3748777.3748791 [50] Ioana Stanoi, Divyakant Agrawal, and Amr El Abbadi. 2000. Reverse nearest neighbor queries for dynamic databases.. In ACM SIGMOD workshop on research issues in data mining and knowledge discovery, Vol. 20. 0. [51] Yufei Tao, Dimitris Papadias, and Xiang Lian. 2004. Reverse kNN search in arbitrary dimensionality. In Proceedings of the Thirtieth International Conference on Very Large Data Bases - Volume 30 (Toronto, Canada) (VLDB ’04). VLDB Endowment, 744–755.

[52] K. Vaidyanathan, S. Woop, and C. Benthin. 2022. Wide BVH traversal with a short stack (HPG ’19). Eurographics Association, Goslar, DEU, 15–19. https: //doi.org/10.2312/hpg.20191190 [53] Ingo Wald. 2007. On fast Construction of SAH-based Bounding Volume Hierarchies. In 2007 IEEE Symposium on Interactive Ray Tracing. 33–40. https: //doi.org/10.1109/RT.2007.4342588 [54] Ingo Wald, Solomon Boulos, and Peter Shirley. 2007. Ray tracing deformable scenes using dynamic bounding volume hierarchies. 26, 1 (Jan. 2007), 6–es. https://doi.org/10.1145/1189762.1206075 [55] Ingo Wald and Vlastimil Havran. 2006. On building fast kd-Trees for Ray Tracing, and on doing that in O(N log N). In 2006 IEEE Symposium on Interactive Ray Tracing. 61–69. https://doi.org/10.1109/RT.2006.280216 [56] Sheng Wang, Zhifeng Bao, J. Shane Culpepper, Timos Sellis, and Gao Cong. 2018. Reverse 𝑘 Nearest Neighbor Search over Trajectories. IEEE Transactions on Knowledge and Data Engineering 30, 4 (2018), 757–771. https://doi.org/10. 1109/TKDE.2017.2776268 [57] Turner Whitted. 2005. An improved illumination model for shaded display. In ACM SIGGRAPH 2005 Courses (Los Angeles, California) (SIGGRAPH ’05). Association for Computing Machinery, New York, NY, USA, 4–es. https: //doi.org/10.1145/1198555.1198743 [58] Raymond Chi-Wing Wong, M. Tamer Özsu, Philip S. Yu, Ada Wai-Chee Fu, and Lian Liu. 2009. Efficient method for maximizing bichromatic reverse nearest neighbor. Proc. VLDB Endow. 2, 1 (Aug. 2009), 1126–1137. https://doi.org/10. 14778/1687627.1687754 [59] Wei Wu, Fei Yang, Chee Yong Chan, and Kian-Lee Tan. 2008. Continuous Reverse k-Nearest-Neighbor Monitoring. In The Ninth International Conference on Mobile Data Management (mdm 2008). 132–139. https://doi.org/10.1109/MDM.2008.31 [60] Wei Wu, Fei Yang, Chee-Yong Chan, and Kian-Lee Tan. 2008. FINCH: evaluating reverse k-Nearest-Neighbor queries on location data. Proc. VLDB Endow. 1, 1 (Aug. 2008), 1056–1067. https://doi.org/10.14778/1453856.1453970 [61] Congyun Yang and King-Ip Lin. 2001. An index structure for efficient reverse nearest neighbor queries. In Proceedings 17th International Conference on Data Engineering. 485–492. https://doi.org/10.1109/ICDE.2001.914862 [62] Shiyu Yang, Muhammad Aamir Cheema, Xuemin Lin, and Wei Wang. 2015. Reverse k nearest neighbors query processing: experiments and analysis. Proc. VLDB Endow. 8, 5 (Jan. 2015), 605–616. https://doi.org/10.14778/2735479.2735492 [63] Shiyu Yang, Muhammad Aamir Cheema, Xuemin Lin, and Ying Zhang. 2014. SLICE: Reviving regions-based pruning for reverse k nearest neighbors queries. In 2014 IEEE 30th International Conference on Data Engineering. 760–771. https: //doi.org/10.1109/ICDE.2014.6816698 [64] Yuhao Zhu. 2022. RTNN: accelerating neighbor search using hardware ray tracing. In Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Seoul, Republic of Korea) (PPoPP ’22). Association for Computing Machinery, New York, NY, USA, 76–89. https://doi.org/10.1145/ 3503221.3508409

Record · ID 229464 · SHA-256 a96a0d5eea42630a
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.