Diversified Top-k Optimal Routes with Collective Spatial Keywords in Road Networks
摘要
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.