Recently, the keyword-aware routing problem has been widely studied. The existing research primarily focuses on finding the Top-k optimal routes that satisfy the given origin and destination while covering the required query keywords through POIs (Point of Interest). However, since the routes are constructed solely based on distance, the POIs visited along these paths are highly similar. This fails to offer diverse routes and worsens traffic congestion. Therefore, in this paper, we study the Diversified Top-k Optimal Routes with Collective Spatial Keywords (Dk-ORCSK) problem, which finds k paths with similarity below a threshold \(\tau \) and minimal total length. To avoid repeatedly visiting the same POIs during path expansion in existing methods, we propose a novel Region Deviation Algorithm (RDA). First, we pre-partition the road network into multiple regions. Next, starting from the origin, we satisfy the query keywords by deviating candidate paths toward the optimal route in different regions, rather than blindly expanding to individual POIs. However, blindly expanding to different regions still leads to higher path similarity. Therefore, we further analyze the similarity among candidate paths and introduce two pruning strategies to improve efficiency. Extensive experiments on real-world datasets demonstrate that our algorithm performs better in both efficiency and result quality.

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

Diversified Top-k Optimal Routes with Collective Spatial Keywords in Road Networks

  • Qiulin An,
  • Jiajia Li,
  • Yang Song,
  • Lei Li,
  • Chengcheng Chen,
  • Linlin Ding

摘要

Recently, the keyword-aware routing problem has been widely studied. The existing research primarily focuses on finding the Top-k optimal routes that satisfy the given origin and destination while covering the required query keywords through POIs (Point of Interest). However, since the routes are constructed solely based on distance, the POIs visited along these paths are highly similar. This fails to offer diverse routes and worsens traffic congestion. Therefore, in this paper, we study the Diversified Top-k Optimal Routes with Collective Spatial Keywords (Dk-ORCSK) problem, which finds k paths with similarity below a threshold \(\tau \) and minimal total length. To avoid repeatedly visiting the same POIs during path expansion in existing methods, we propose a novel Region Deviation Algorithm (RDA). First, we pre-partition the road network into multiple regions. Next, starting from the origin, we satisfy the query keywords by deviating candidate paths toward the optimal route in different regions, rather than blindly expanding to individual POIs. However, blindly expanding to different regions still leads to higher path similarity. Therefore, we further analyze the similarity among candidate paths and introduce two pruning strategies to improve efficiency. Extensive experiments on real-world datasets demonstrate that our algorithm performs better in both efficiency and result quality.