HELM: Hybrid Spatial Index of Moving Objects at Large Scales Tuned with Multi-Agent Reinforcement Learning
摘要
Processing spatial queries for moving objects at large spatial scales presents a significant challenge for many location-based services. While several spatial indexes offer preliminary solutions to address the inefficiencies caused by frequent position updates, they often fail to maintain high performance at large scales. In this paper, we introduce an efficient hybrid index for spatial queries involving moving objects at large scales, utilizing Minimum Bounding Rectangles for non-leaf nodes and Grid indexes for leaf nodes. Additionally, we propose a series of Reinforcement Learning-based enhancement strategies, including: (1) DGK-means, a distribution-aware clustering algorithm designed for clustering moving objects, (2) optimization algorithms for updates and queries to enhance query performance, and (3) parameter configuration strategies based on Multi-Agent Reinforcement Learning to adapt to the skewness of distribution at large spatial scales. Extensive experimental results demonstrate that our hybrid index significantly outperforms the state-of-the-art spatial indexes, achieving up to 15.6 \(\times \) improvement in update performance and up to 6.7 \(\times \) improvement in query performance.