An adaptive R-Tree-based geosearch algorithm for moving users

This paper presents an adaptive R*-tree-based geospatial search algorithm tailored for real-time applications involving dynamically moving users. Conventional methods that rely on a fixed point and a circular or square search area neglect user kinematics – specifically speed and heading – resulting in low result relevance, excessive data transmission, and increased load on client devices and network infrastructure. To address this, we propose a modified approach that dynamically shapes an asymmetric search region extended along the user’s motion vector. The size and geometry of this region are adjusted in real time based on current speed and a configurable speed-influence coefficient. Additionally, a "visibility zone" parameter is introduced for target objects, enabling indexing not only of their coordinates but also of their potential display radii, thereby improving filtering accuracy. The algorithm is implemented within a metaspace object routing task and employs an R*-tree with optimized bulk-loading to minimize overlaps of Minimum Bounding Rectangles (MBR). Simulation results demonstrate improvement in search relevance up to 7 times compared to classical radial search, without increasing computational complexity and while reducing network payload. The method is applicable to navigation, augmented/mixed reality, autonomous systems, and other domains requiring real-time spatial relevance.

1. Han Q., Yoshikawa A., Yamamura M. Hierarchical Graph Learning with Cross-Layer Information Propagation for Next Point of Interest Recommendation. Applied Sciences. 2025;15(9). https://doi.org/10.3390/app15094979

2. Dorokhin V.A., Podgornyi S.A., Tokareva N.A. Classification and Model of Objects in Extended Reality Metaspace. Modeling, Optimization and Information Technology. 2025;13(1). (In Russ.). https://doi.org/10.26102/2310-6018/2025.48.1.032

3. Shi Y., Hendawi A.H., Fattah H., Mohamed A. RxSpatial: Reactive Spatial Library for Real-Time Location Tracking and Processing. In: SIGMOD '16: Proceedings of the 2016 International Conference on Management of Data, 26 June – 1 July 2016, San Francisco, CA, USA. New York: Association for Computing Machinery; 2016. P. 2165–2168. https://doi.org/10.1145/2882903.2899411

4. Nimbalkar V.P. Enhancing Vehicle Navigation and Safety Through Integration of Pre-Recorded Maps with Vehicle Control Unit. International Journal of Innovative Research in Computer Science and Technology. 2024;12(4):117–123. https://doi.org/10.55524/ijircst.2024.12.4.18

5. Li P., Wang Z., Zhang X., Wang P., Liu K. Next Arrival and Destination Prediction via Spatiotemporal Embedding with Urban Geography and Human Mobility Data. Mathematics. 2025;13(5). https://doi.org/10.3390/math13050746

6. Nutheti S.S. POI Recommendation from a Data Perspective. ResearchGate. URL: https://www.researchgate.net/publication/392708648_POI_Recommendation_from_a_Data_Perspective [Accessed 12th September 2025].

7. Guttman A. R-Trees: A Dynamic Index Structure for Spatial Searching. In: SIGMOD'84, Proceedings of Annual Meeting, 18–21 June 1984, Boston, MA, USA. ACM Press; 1984. P. 47–57. http://doi.acm.org/10.1145/602259.602266

8. Beckmann N., Kriegel H.-P., Schneider R., Seeger B. The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. In: SIGMOD '90: Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, 23–26 May 1990, Atlantic City, NJ, USA. New York: Association for Computing Machinery; 1990. P. 322–331. http://doi.org/10.1145/93597.98741

9. Beckmann N., Seeger B. A Revised R*-Tree in Comparison with Related Index Structures. In: SIGMOD '90: Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, 23–26 May 1990, Atlantic City, NJ, USA. New York: Association for Computing Machinery; 1990. P. 799–812. http://doi.org/10.1145/1559845.1559929

10. Kamel I., Faloutsos Ch. Hilbert R-Tree: An Improved R-Tree Using Fractals. In: VLDB '94: Proceedings of the 20th International Conference on Very Large Data Bases, 12–15 September 1994, Santiago de Chile, Chile. San Francisco: Morgan Kaufmann; 1994. P. 500–509.

11. Lee T., Lee S. OMT: Overlap Minimizing Top-Down Bulk Loading Algorithm for R-Tree. In: The 15th Conference on Advanced Information Systems Engineering (CAiSE '03), CAiSE Forum, Short Paper Proceedings, Information Systems for a Connected Society, 16–20 June 2003, Klagenfurt/Velden, Austria. 2003. P. 69–72.