Finding Top-K Keywords-Aware Optimal Routes: A Splice-Based Expansion Approach

Given a start point s, a destination t, and the set of keyword types that must be satisfied, the goal of Top-k Keywords-Aware Optimal Route (k-KAOR) query is to return top-k shortest routes that covers all query keyword types. Existing solutions can be divided into two classes: candidate based algorithms and path expansion based algorithms. However, they all face a trade-off between query efficiency and route quality. To solve this problem, in this paper, we further study the k-KAOR problem and introduce a Splice-Based Expansion (SBE) algorithm. The SBE algorithm efficiently integrates the ideas of candidate set and path expansion. First, to avoid a vast search space, we introduce a Point of Interest (POI) filtering refinement strategy based on the spatial index IG-Tree. Then, to cover more combinations of POIs while avoiding brute-force enumeration, we pre-construct a keyword distance matrix and splice POIs using the graph partitioning of the IG-Tree. Finally, we perform path expansion by concatenating different POI combinations until the top-k paths are discovered. Extensive experiments on real-world road networks show that our method can reduces response time by an order of magnitude and improves result quality by 25%.