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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

HELM: Hybrid Spatial Index of Moving Objects at Large Scales Tuned with Multi-Agent Reinforcement Learning

  • Na Guo,
  • Wenli Sun,
  • Fei Cai,
  • Xing Yiming,
  • Xiufeng Xia

摘要

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.