Batch Processing of Reverse k-Nearest Neighbor Queries for Moving Objects on Road Networks
Published:Dec 29, 2025 08:36
•1 min read
•ArXiv
Analysis
This paper addresses the problem of efficiently processing multiple Reverse k-Nearest Neighbor (RkNN) queries simultaneously, a common scenario in location-based services. It introduces the BRkNN-Light algorithm, which leverages geometric constraints, optimized range search, and dynamic distance caching to minimize redundant computations when handling multiple queries in a batch. The focus on batch processing and computation reuse is a significant contribution, potentially leading to substantial performance improvements in real-world applications.
Key Takeaways
Reference
“The BR$k$NN-Light algorithm uses rapid verification and pruning strategies based on geometric constraints, along with an optimized range search technique, to speed up the process of identifying the R$k$NNs for each query.”