pith. sign in

arxiv: 2605.26671 · v1 · pith:EVIJUT4Enew · submitted 2026-05-26 · 💻 cs.DB · cs.DC

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

Zhengyang Bai , Peng Chen , Mohamed Wahib This is my paper

Pith reviewed 2026-07-01 16:16 UTC · model grok-4.3

classification 💻 cs.DB cs.DC
keywords reverse k nearest neighborray castingGPU ray tracingspatial databaseshardware accelerationR-tree pruning
0
0 comments X

The pith

Reverse k nearest neighbor queries can be solved exactly by reformulating them as ray casting on GPU hardware.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that RkNN queries in 2D can be recast as a graphics ray-casting problem by treating users as rays and facilities as geometric primitives. This mapping lets dedicated ray-tracing cores on modern GPUs perform the necessary filtering. Traditional R-tree pruning loses effectiveness when k grows large, user data is dense, or facilities are sparse, but the ray-casting approach keeps strong performance across those cases. A sympathetic reader would care because location-based services and recommendation systems often encounter exactly these distributions and need exact answers at scale.

Core claim

RkNN queries are reformulated as a ray-casting task in which each user corresponds to a ray and each facility to a geometric primitive; the first algorithm and implementation then uses GPU ray-tracing hardware to compute the results while preserving exact semantics and strong filtering even for large k, dense users, and sparse facilities.

What carries the argument

The exact mapping of users to rays and facilities to 2D geometric primitives that turns RkNN into a standard ray-casting computation solvable on dedicated GPU cores.

If this is right

  • Filtering performance remains high when k is large.
  • Performance holds for dense user populations and sparse facility sets.
  • The method outperforms R-tree-based pruning in the regimes where pruning degrades.
  • Exact results are obtained without approximation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same hardware mapping could be tested on other spatial predicates that reduce to visibility or intersection tests.
  • If ray-tracing cores continue to improve, query optimizers may begin routing certain spatial workloads to the graphics pipeline rather than the CPU.
  • Extending the formulation to 3D would require only the addition of a third coordinate and the corresponding ray-tracing support.

Load-bearing premise

The geometric reformulation of users as rays and facilities as primitives produces an exact, semantics-preserving equivalent of the original RkNN problem.

What would settle it

Run the proposed algorithm and a brute-force exact RkNN implementation on the same 2D point set and check whether the reported neighbor sets differ for any query point.

Figures

Figures reproduced from arXiv: 2605.26671 by Mohamed Wahib, Peng Chen, Zhengyang Bai.

Figure 1
Figure 1. Figure 1: Illustration of SIX [50] filtering, TPL [51] filtering, InfZone [8] pruning, and SLICE [63] pruning ( [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. 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 re… view at source ↗
Figure 3
Figure 3. 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 [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 5
Figure 5. Figure 5: A BVH example (right) corresponding to a 2D scene [PITH_FULL_IMAGE:figures/full_fig_p006_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Visualization of datasets [PITH_FULL_IMAGE:figures/full_fig_p008_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Impact of varying [PITH_FULL_IMAGE:figures/full_fig_p009_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Impact of varying 𝑘 settings on runtime using the default facility setting. 25 50 75 100 125 150 175 200 k 0 1000 2000 3000 4000 5000 6000 7000 Runtime (ms) SLICE RT(ours) [PITH_FULL_IMAGE:figures/full_fig_p009_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Impact of large 𝑘 on runtime in default facility setting (|𝐹 | = 1000) of USA dataset. default facility setting, where spatial pruning remains highly effec￾tive, 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… view at source ↗
Figure 11
Figure 11. Figure 11: Total runtime under varying cardinality for [PITH_FULL_IMAGE:figures/full_fig_p010_11.png] view at source ↗
Figure 10
Figure 10. Figure 10: Impact of data size on runtime in sparse ( [PITH_FULL_IMAGE:figures/full_fig_p010_10.png] view at source ↗
Figure 12
Figure 12. Figure 12: Breakdown of filtering and verification time under [PITH_FULL_IMAGE:figures/full_fig_p010_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Total runtime under varying facility cardinality [PITH_FULL_IMAGE:figures/full_fig_p011_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Breakdown of filtering and verification time under [PITH_FULL_IMAGE:figures/full_fig_p011_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Runtime breakdown analysis under configurations [PITH_FULL_IMAGE:figures/full_fig_p011_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: Impact of occluder counts on runtime under the [PITH_FULL_IMAGE:figures/full_fig_p012_16.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims that RkNN queries can be exactly reformulated as a 2D graphics ray-casting problem by modeling users as rays and facilities as geometric primitives; this enables an algorithm that exploits dedicated GPU ray-tracing hardware, preserves correctness, and outperforms R-tree-based methods especially when the number of facilities is small, user density is high, or k is large.

Significance. If the claimed semantics-preserving reduction holds and the hardware implementation is correct, the work would demonstrate a viable path for accelerating spatial queries via commodity graphics hardware, addressing a known weakness of pruning-based indexes in certain regimes. The approach is novel in its direct use of ray-tracing cores rather than software simulation.

major comments (2)
  1. [§3 (Reformulation)] The central claim requires an exact, semantics-preserving mapping from RkNN to ray-primitive intersections. No theorem, lemma, or exhaustive equivalence argument is supplied showing that every point p for which q is among its k nearest neighbors produces (and only produces) the expected intersections, including correct handling of the k-distance boundary, ties, and dense clusters. This is load-bearing for the assertion that hardware output matches true RkNN semantics without approximation or missed results.
  2. [§5] §5 (Experiments): the reported performance superiority is asserted without accompanying details on dataset characteristics, baseline implementations, number of trials, error bars, or any brute-force verification that the ray-tracing results match ground-truth RkNN on the test instances. Without these, the experimental support for the central performance claim cannot be assessed.
minor comments (2)
  1. [§3.2] Notation for the geometric primitives and ray parameters is introduced without a consolidated table relating them back to the original RkNN definitions (e.g., distance, k).
  2. [Figures 3-5] Figure captions could more explicitly state what is being visualized (ray origins, primitive types, intersection counts) to aid readers unfamiliar with graphics hardware.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback. The comments highlight important areas for strengthening the presentation of the reformulation and the experimental evaluation. We address each point below and will incorporate revisions accordingly.

read point-by-point responses

  1. Referee: [§3 (Reformulation)] The central claim requires an exact, semantics-preserving mapping from RkNN to ray-primitive intersections. No theorem, lemma, or exhaustive equivalence argument is supplied showing that every point p for which q is among its k nearest neighbors produces (and only produces) the expected intersections, including correct handling of the k-distance boundary, ties, and dense clusters. This is load-bearing for the assertion that hardware output matches true RkNN semantics without approximation or missed results.

    Authors: We acknowledge that an explicit formal argument would improve clarity. Section 3 describes the mapping (users modeled as rays originating at query facilities, facilities as geometric primitives, with intersection counts determining RkNN membership) and argues equivalence based on the geometric interpretation of nearest-neighbor ranks. However, to directly address the concern, the revised manuscript will add a lemma in §3 that formally proves the semantics-preserving property: every valid RkNN user produces exactly the expected intersections (and no others), with the k-distance boundary handled by setting ray lengths to the precise k-th distance, ties resolved via a deterministic ordering on facility identifiers, and dense clusters processed without omission because the ray-tracing hardware reports all intersections exactly. revision: yes

  2. Referee: [§5] §5 (Experiments): the reported performance superiority is asserted without accompanying details on dataset characteristics, baseline implementations, number of trials, error bars, or any brute-force verification that the ray-tracing results match ground-truth RkNN on the test instances. Without these, the experimental support for the central performance claim cannot be assessed.

    Authors: We agree that the current experimental section lacks sufficient detail for full assessment and reproducibility. In the revision we will expand §5 to include: complete dataset characteristics (cardinalities, spatial distributions, and generation parameters), explicit descriptions of the baseline R-tree implementations (including library versions and parameter settings), the number of independent trials performed, error bars computed as standard deviations across runs, and a new correctness-verification subsection that compares ray-tracing outputs against brute-force RkNN results on representative small-scale instances to confirm exact semantic equivalence on the test data. revision: yes

Circularity Check

0 steps flagged

No circularity: reformulation is an independent algorithmic mapping

full rationale

The paper frames its contribution as a direct geometric reformulation of RkNN into ray-casting (users as rays, facilities as primitives) that is then solved on existing GPU hardware. No derivation chain reduces a claimed result to fitted parameters, self-citations, or self-definitional equations. The mapping is presented as a semantics-preserving encoding whose correctness is asserted by construction of the geometric primitives, not derived from prior fitted outputs or author-specific uniqueness theorems. This is a standard non-circular reformulation approach; the central claim stands or falls on whether the encoding is exact, which is an independent verification question rather than a circularity issue.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities are stated. The central claim rests on the unelaborated assumption that the geometric reformulation is exact and that GPU ray tracing can be applied without loss of query semantics.

pith-pipeline@v0.9.1-grok · 5696 in / 1044 out tokens · 30938 ms · 2026-07-01T16:16:40.990242+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

67 extracted references · 39 canonical work pages

  1. [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 met- ric databases. InProceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology(Saint Petersburg, Russia) (EDBT ’09). Association for Computing Machinery, N...

    work page doi:10.1145/1516360.1516462 2009

  2. [2]

    Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger

  3. [3]

    InProceedings of the 1990 ACM SIGMOD International Conference on Management of Data(Atlantic City, New Jersey, USA)(SIGMOD ’90)

    The R*-tree: an efficient and robust access method for points and rectangles. InProceedings of the 1990 ACM SIGMOD International Conference on Management of Data(Atlantic City, New Jersey, USA)(SIGMOD ’90). As- sociation for Computing Machinery, New York, NY, USA, 322–331. https: //doi.org/10.1145/93597.98741

    work page doi:10.1145/93597.98741 1990

  4. [4]

    Jensen, Gytis Karundefinediauskas, and Simonas unde- finedaltenis

    Rimantas Benetis, S. Jensen, Gytis Karundefinediauskas, and Simonas unde- finedaltenis. 2006. Nearest and reverse nearest neighbor queries for moving objects.The VLDB Journal15, 3 (Sept. 2006), 229–249. https://doi.org/10.1007/ s00778-005-0166-4

    2006

  5. [5]

    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

    work page doi:10.14778/2021017.2021024 2011

  6. [6]

    Avory Bryant and Krzysztof Cios. 2018. RNN-DBSCAN: A Density-Based Clus- tering Algorithm Using Reverse Nearest Neighbor Density Estimates.IEEE Transactions on Knowledge and Data Engineering30, 6 (2018), 1109–1121. https: //doi.org/10.1109/TKDE.2017.2787640

    work page doi:10.1109/tkde.2017.2787640 2018

  7. [7]

    Cabello, J.M

    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 Research202, 1 (2010), 99–106. https: //doi.org/10.1016/j.ejor.2009.04.021

    work page doi:10.1016/j.ejor.2009.04.021 2010

  8. [8]

    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 Engineering22, 4 (2010), 550–564. https://doi.org/10.1109/TKDE.2009.108

    work page doi:10.1109/tkde.2009.108 2010

  9. [9]

    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

    work page doi:10.1109/icde.2011.5767904 2011

  10. [11]

    Muhammad Aamir Cheema, Wenjie Zhang, Xuemin Lin, and Ying Zhang. 2012. Efficiently processing snapshot and continuous reverse k nearest neighbors queries.The VLDB Journal21, 5 (2012), 703–728

    2012

  11. [12]

    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 Journal21, 1 (2012), 69–95

    2012

  12. [13]

    Farhana Choudhury, J Shane Culpepper, Timos Sellis, and Xin Cao. 2016. Max- imizing bichromatic reverse spatial and textual k nearest neighbor queries. In 42nd International Conference on Very Large Data Bases. VLDB Endowment Inc., 456–467

    2016

  13. [14]

    DIMACS. 2006. 9th DIMACS Implementation Challenge - Shortest Paths. https: //www.diag.uniroma1.it/~challenge9/download.shtml. Accessed: 2025-11-24

    2006

  14. [15]

    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. InProceedings 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–4...

    work page arXiv 2010

  15. [16]

    Epic Games. 2021. Ray Tracing Features Settings. https://dev. epicgames.com/documentation/en-us/unreal-engine/ray-tracing-features- settings?application_version=4.27. Accessed 2025-11-21

    2021

  16. [17]

    Liang Geng, Rubao Lee, and Xiaodong Zhang. 2024. RayJoin: Fast and Precise Spatial Join. InProceedings of the 38th ACM International Conference on Super- computing(Kyoto, Japan)(ICS ’24). Association for Computing Machinery, New York, NY, USA, 124–136. https://doi.org/10.1145/3650200.3656610

    work page doi:10.1145/3650200.3656610 2024

  17. [18]

    Liang Geng, Rubao Lee, and Xiaodong Zhang. 2025. LibRTS: A Spatial Index- ing Library by Ray Tracing. InProceedings 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

    work page doi:10.1145/3710848.3710850 2025

  18. [19]

    Wilson, and Farnoush Banaei-Kashani

    Parisa Ghaemi, Kaveh Shahabi, John P. Wilson, and Farnoush Banaei-Kashani

  19. [20]

    InProceedings of the 20th International Conference on Advances in Geographic Information Systems(Redondo Beach, California)(SIGSPATIAL ’12)

    Continuous maximal reverse nearest neighbor query on spatial networks. InProceedings 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

    work page arXiv

  20. [21]

    Yusuke Gotoh and Chiori Okubo. 2016. A Searching Method for Bichromatic Reverse k-Nearest Neighbor with Network Voronoi Diagram. InProceedings 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

    work page doi:10.1145/3007120.3007133 2016

  21. [22]

    Antonin Guttman. 1984. R-trees: a dynamic index structure for spatial searching. InProceedings of the 1984 ACM SIGMOD International Conference on Manage- ment of Data(Boston, Massachusetts)(SIGMOD ’84). Association for Computing Machinery, New York, NY, USA, 47–57. https://doi.org/10.1145/602259.602266

    work page doi:10.1145/602259.602266 1984

  22. [23]

    Justus Henneberg and Felix Schuhknecht. 2023. RTIndeX: Exploiting Hardware- Accelerated GPU Raytracing for Database Indexing.Proceedings of the VLDB Endowment16, 13 (2023), 4268–4281

    2023

  23. [24]

    Lihua Hu, Hongkai Liu, Jifu Zhang, and Aiqin Liu. 2021. KR-DBSCAN: A density- based clustering algorithm based on reverse nearest neighbor and influence space.Expert Systems with Applications186 (2021), 115763

    2021

  24. [25]

    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 Web26, 4 (2023), 1567– 1598

    2023

  25. [26]

    2022.California Hospitals Almanac — 2022 Edition

    Jen Joynt. 2022.California Hospitals Almanac — 2022 Edition. Technical Report. California Health Care Foundation. https://www.chcf.org/resource/california- hospitals-almanac/ Accessed: 2025-11-19

    2022

  26. [27]

    Kang, Mohamed F

    James M. Kang, Mohamed F. Mokbel, Shashi Shekhar, Tian Xia, and Donghui Zhang. 2007. Continuous Evaluation of Monochromatic and Bichromatic Reverse Nearest Neighbors. In2007 IEEE 23rd International Conference on Data Engineering. 806–815. https://doi.org/10.1109/ICDE.2007.367926

    work page doi:10.1109/icde.2007.367926 2007

  27. [28]

    Khronos Group. 2020. Vulkan Ray Tracing Extensions. https://www.khronos. org/blog/vulkan-ray-tracing-final-specification-release. Accessed 2025-11-21

    2020

  28. [29]

    Muthukrishnan

    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

    work page arXiv 2000

  29. [30]

    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

    2023

  30. [31]

    Nolen, and Congjun Yang

    King-Ip Lin, M. Nolen, and Congjun Yang. 2003. Applying bulk insertion tech- niques for dynamic reverse nearest neighbor problems. InSeventh International Database Engineering and Applications Symposium, 2003. Proceedings.290–297. https://doi.org/10.1109/IDEAS.2003.1214938

    work page doi:10.1109/ideas.2003.1214938 2003

  31. [32]

    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 Ray- Tracing Core Mapping. InProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operatin...

    work page doi:10.1145/3620665.3640360 2024

  32. [33]

    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 Endowment17, 6 (2024)

    2024

  33. [34]

    Durga Keerthi Mandarapu, Vani Nagarajan, Artem Pelenitsyn, and Milind Kulka- rni. 2024. Arkade: k-Nearest Neighbor Search With Non-Euclidean Distances using GPU Ray Tracing. InProceedings of the 38th ACM International Confer- ence on Supercomputing(Kyoto, Japan)(ICS ’24). Association for Computing Machinery, New York, NY, USA, 14–25. https://doi.org/10.11...

    work page doi:10.1145/3650200.3656601 2024

  34. [35]

    Daniel Meister, Paritosh Kulkarni, Aaryaman Vasishta, and Takahiro Harada

  35. [36]

    ACM Comput

    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

    2024

  36. [37]

    Daniel Meister, Shinji Ogaki, Carsten Benthin, Michael J Doyle, Michael Guthe, and Jiří Bittner. 2021. A survey on bounding volume hierarchies for ray tracing. InComputer Graphics Forum, Vol. 40. Wiley Online Library, 683–712

    2021

  37. [38]

    Microsoft DirectX Team. 2025. DirectX at GDC 2025. https://devblogs.microsoft. com/directx/directx-at-gdc-2025/. Accessed 2025-11-21

    2025

  38. [39]

    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

    work page doi:10.1145/1198555.1198746 2005

  39. [40]

    Vani Nagarajan and Milind Kulkarni. 2023. RT-DBSCAN: Accelerating DBSCAN using Ray Tracing Hardware. In2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 963–973. https://doi.org/10.1109/IPDPS54959. 2023.00100

    work page doi:10.1109/ipdps54959 2023

  40. [41]

    Vani Nagarajan, Durga Mandarapu, and Milind Kulkarni. 2023. RT-kNNS Un- bound: Using RT Cores to Accelerate Unrestricted Neighbor Search. InProceed- ings 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

    work page doi:10.1145/3577193.3593738 2023

  41. [42]

    Michael Nwogugu. 2006. Site selection in the US retailing industry.Applied mathematics and computation182, 2 (2006), 1725–1734

    2006

  42. [43]

    2025.Fast Shipping

    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-shipping- slow-justice/

    2025

  43. [44]

    Yu, and Jingfeng Guo

    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 Computing15, 2 (2022), 986–999. https://doi.org/ 10.1109/TSC.2020.2968309

    work page doi:10.1109/tsc.2020.2968309 2022

  44. [45]

    Parker, James Bigler, Andreas Dietrich, Heiko Friedrich, Jared Hobe- rock, David Luebke, David McAllister, Morgan McGuire, Keith Morley, Austin Robison, and Martin Stich

    Steven G. Parker, James Bigler, Andreas Dietrich, Heiko Friedrich, Jared Hobe- rock, 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

    work page doi:10.1145/1778765.1778803 2010

  45. [46]

    2012.Computational geometry: an introduction

    Franco P Preparata and Michael I Shamos. 2012.Computational geometry: an introduction. Springer Science & Business Media

    2012

  46. [47]

    Milos Radovanovic, Alexandros Nanopoulos, and Mirjana Ivanovic. 2010. Hubs in space: Popular nearest neighbors in high-dimensional data.Journal of Machine Learning Research11, sept (2010), 2487–2531

    2010

  47. [48]

    Maytham Safar, Dariush Ibrahimi, and David Taniar. 2009. Voronoi-based reverse nearest neighbor query processing on spatial networks.Multimedia systems15, 5 (2009), 295–308

    2009

  48. [49]

    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. InProceedings 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, 1...

    work page arXiv 2011

  49. [50]

    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

    work page doi:10.14778/1920841.1920994 2010

  50. [51]

    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

    2025

  51. [52]

    Anbang Song, Ziqiang Yu, Wei Liu, Yating Xu, and Mingjin Tao. 2025. BRkNN- light: Batch Processing of Reverse k-Nearest Neighbor Queries for Moving Ob- jects on Road Networks. InProceedings 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/374...

    work page doi:10.1145/3748777.3748791 2025

  52. [53]

    Ioana Stanoi, Divyakant Agrawal, and Amr El Abbadi. 2000. Reverse nearest neighbor queries for dynamic databases.. InACM SIGMOD workshop on research issues in data mining and knowledge discovery, Vol. 20. 0

    2000

  53. [54]

    Yufei Tao, Dimitris Papadias, and Xiang Lian. 2004. Reverse kNN search in arbitrary dimensionality. InProceedings of the Thirtieth International Conference on Very Large Data Bases - Volume 30(Toronto, Canada)(VLDB ’04). VLDB Endowment, 744–755

    2004

  54. [55]

    Vaidyanathan, S

    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

    work page doi:10.2312/hpg.20191190 2022

  55. [56]

    Ingo Wald. 2007. On fast Construction of SAH-based Bounding Volume Hi- erarchies. In2007 IEEE Symposium on Interactive Ray Tracing. 33–40. https: //doi.org/10.1109/RT.2007.4342588

    work page doi:10.1109/rt.2007.4342588 2007

  56. [57]

    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

    work page doi:10.1145/1189762.1206075 2007

  57. [58]

    Ingo Wald and Vlastimil Havran. 2006. On building fast kd-Trees for Ray Tracing, and on doing that in O(N log N). In2006 IEEE Symposium on Interactive Ray Tracing. 61–69. https://doi.org/10.1109/RT.2006.280216

    work page doi:10.1109/rt.2006.280216 2006

  58. [59]

    Shane Culpepper, Timos Sellis, and Gao Cong

    Sheng Wang, Zhifeng Bao, J. Shane Culpepper, Timos Sellis, and Gao Cong

  59. [60]

    https://doi.org/10

    Reverse 𝑘 Nearest Neighbor Search over Trajectories.IEEE Transactions on Knowledge and Data Engineering30, 4 (2018), 757–771. https://doi.org/10. 1109/TKDE.2017.2776268

    work page arXiv 2018

  60. [61]

    Turner Whitted. 2005. An improved illumination model for shaded display. InACM 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

    work page doi:10.1145/1198555.1198743 2005

  61. [62]

    Tamer Özsu, Philip S

    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

    work page arXiv 2009

  62. [63]

    Wei Wu, Fei Yang, Chee Yong Chan, and Kian-Lee Tan. 2008. Continuous Reverse k-Nearest-Neighbor Monitoring. InThe Ninth International Conference on Mobile Data Management (mdm 2008). 132–139. https://doi.org/10.1109/MDM.2008.31

    work page doi:10.1109/mdm.2008.31 2008

  63. [64]

    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

    work page doi:10.14778/1453856.1453970 2008

  64. [65]

    Congyun Yang and King-Ip Lin. 2001. An index structure for efficient reverse nearest neighbor queries. InProceedings 17th International Conference on Data Engineering. 485–492. https://doi.org/10.1109/ICDE.2001.914862

    work page doi:10.1109/icde.2001.914862 2001

  65. [66]

    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

    work page doi:10.14778/2735479.2735492 2015

  66. [67]

    Shiyu Yang, Muhammad Aamir Cheema, Xuemin Lin, and Ying Zhang. 2014. SLICE: Reviving regions-based pruning for reverse k nearest neighbors queries. In2014 IEEE 30th International Conference on Data Engineering. 760–771. https: //doi.org/10.1109/ICDE.2014.6816698

    work page doi:10.1109/icde.2014.6816698 2014

  67. [68]

    Yuhao Zhu. 2022. RTNN: accelerating neighbor search using hardware ray tracing. InProceedings 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

    work page arXiv 2022