<p>Nowadays, location-based services are widely used, requiring instant responses to a large volume of multiple spatial queries over massive road networks, i.e., single-pair shortest path (SPSP) query, <i>k</i>-nearest neighbor (<i>k</i>NN) query, and range query. Creating index-based structure for each kind of query is costly, hence it is important to handle multiple spatial queries within one efficient structure. Partition-based hierarchical approaches show promising potential to meet the requirement. However, existing approaches require large search space on massive road networks especially for long-distance queries, which is inefficient and hard to scale. To overcome the drawbacks, we propose the shortcut-enhanced graph hierarchy tree (SCG-tree), which leverages shortcuts to effectively prune the search space over a hierarchical structure. With the SCG-tree, a pruned shortcut-based method is designed to answer SPSP query, and a two-phase expansion strategy is proposed to leverage shortcuts for <i>k</i>NN and range queries. Theoretical analyses show the superiority of proposed shortcut-based query algorithms. Extensive experiments demonstrate that our approach can achieve three times speedup for <i>k</i>NN query and an order of magnitude speedup for SPSP and range queries over existing methods on real road networks that scale up to 24 million nodes and 58 million edges.</p>

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

SCG-tree: shortcut enhanced graph hierarchy tree for efficient spatial queries on massive road networks

  • Zhuo Cao,
  • Chun Cao,
  • Jianqiu Xu,
  • Jingwei Xu,
  • Zhefei Chen,
  • Zi Chen,
  • Xiaoxing Ma

摘要

Nowadays, location-based services are widely used, requiring instant responses to a large volume of multiple spatial queries over massive road networks, i.e., single-pair shortest path (SPSP) query, k-nearest neighbor (kNN) query, and range query. Creating index-based structure for each kind of query is costly, hence it is important to handle multiple spatial queries within one efficient structure. Partition-based hierarchical approaches show promising potential to meet the requirement. However, existing approaches require large search space on massive road networks especially for long-distance queries, which is inefficient and hard to scale. To overcome the drawbacks, we propose the shortcut-enhanced graph hierarchy tree (SCG-tree), which leverages shortcuts to effectively prune the search space over a hierarchical structure. With the SCG-tree, a pruned shortcut-based method is designed to answer SPSP query, and a two-phase expansion strategy is proposed to leverage shortcuts for kNN and range queries. Theoretical analyses show the superiority of proposed shortcut-based query algorithms. Extensive experiments demonstrate that our approach can achieve three times speedup for kNN query and an order of magnitude speedup for SPSP and range queries over existing methods on real road networks that scale up to 24 million nodes and 58 million edges.