Адаптивный алгоритм геопоиска для движущихся объектов на основе R-деревьев

В статье предложен адаптивный алгоритм геопоиска на основе R*-деревьев, ориентированный на сценарии реального времени с участием динамически перемещающихся пользователей. Традиционные методы, основанные на фиксированной точке и круговой или квадратной зоне поиска, не учитывают кинематические параметры пользователя – скорость и направление движения, – что приводит к низкой релевантности результатов, избыточной передаче данных и повышенной нагрузке на клиентские устройства и сеть. Для решения этой проблемы разработан модифицированный подход, формирующий асимметричную поисковую область, расширенную вдоль вектора движения пользователя. Размер и форма этой области динамически регулируются с учетом текущей скорости и настраиваемого коэффициента ее влияния. Дополнительно вводится параметр «зона видимости» целевых объектов, позволяющий индексировать не только их координаты, но и радиусы потенциального отображения, что повышает точность фильтрации. Алгоритм реализован для решения задачи маршрутизации объектов метапространства и использует R*-дерево с оптимизированной массовой загрузкой данных для минимизации перекрытий минимальных ограничивающих прямоугольников (MBR). Результаты имитационного моделирования показали, что предложенный метод повышает релевантность выдачи до 7 раз по сравнению с классическим радиальным поиском, при этом не увеличивая вычислительную сложность операции поиска и снижая объем передаваемых данных. Подход применим в задачах навигации, дополненной и смешанной реальности, беспилотных систем и других областях, где критична актуальность пространственной информации в реальном времени.

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. Дорохин В.А., Подгорный С.А., Токарева Н.А. Классификация и модель объектов метапространства расширенной реальности. Моделирование, оптимизация и информационные технологии. 2025;13(1). 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.