В статье предложен адаптивный алгоритм геопоиска на основе R*-деревьев, ориентированный на сценарии реального времени с участием динамически перемещающихся пользователей. Традиционные методы, основанные на фиксированной точке и круговой или квадратной зоне поиска, не учитывают кинематические параметры пользователя – скорость и направление движения, – что приводит к низкой релевантности результатов, избыточной передаче данных и повышенной нагрузке на клиентские устройства и сеть. Для решения этой проблемы разработан модифицированный подход, формирующий асимметричную поисковую область, расширенную вдоль вектора движения пользователя. Размер и форма этой области динамически регулируются с учетом текущей скорости и настраиваемого коэффициента ее влияния. Дополнительно вводится параметр «зона видимости» целевых объектов, позволяющий индексировать не только их координаты, но и радиусы потенциального отображения, что повышает точность фильтрации. Алгоритм реализован для решения задачи маршрутизации объектов метапространства и использует R*-дерево с оптимизированной массовой загрузкой данных для минимизации перекрытий минимальных ограничивающих прямоугольников (MBR). Результаты имитационного моделирования показали, что предложенный метод повышает релевантность выдачи до 7 раз по сравнению с классическим радиальным поиском, при этом не увеличивая вычислительную сложность операции поиска и снижая объем передаваемых данных. Подход применим в задачах навигации, дополненной и смешанной реальности, беспилотных систем и других областях, где критична актуальность пространственной информации в реальном времени.
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.
The authors declare that there are no conflicts of interest present.