基于空间关键词的Top-k最优路径加速查询框架OA

To address the high computational complexity in spatial keyword path queries,an efficient Top-k Optimal Path Acceleration Query(OPAQ)framework is proposed.Given a user-specified start point,end point,and a set of spatial keywords,the framework returns k optimal paths that satisfy all keyword constraints.To improve query efficiency,OPAQ introduces several key optimization strategies:constructing a point of interest(POI)subgraph to eliminate irrelevant vertices and reduce the search space;building an LG-Tree to support fast shortest distance queries between arbitrary node pairs;designing an SP-Tree to share path prefix information;and applying heuristic deviate search strategy to efficiently discover paths that cover the remaining keywords.Additionally,it defines the formal conditions for path validity and proposes an efficient path expansion method that combines the shared prefix structure and heuristic strategies to support the rapid generation of Top-k path results.Finally,experiments are conducted on multiple real-world datasets to verify the superior performance of the OPAQ framework.It outperformed existing mainstream algorithms in both query time and path quality,especially demonstrating excellent efficiency and extensibility in Top-k queries.