An Efficient Edge-Based Index for Processing Collective Spatial Keyword Query on Road Networks

Spatial keyword queries find extensive applications in geographic information systems like Facebook and Instagram. The collective spatial keyword query (CSKQ) plays a crucial role among the various types of queries. This query aims to retrieve a set of Points of Interest (POIs) that collectively cover the specified keywords while being in proximity to both the query location and other objects. To evaluate the spatial cost of a set of POIs in CSKQ, we introduce the Edge-Based Collective Nine-Area Tree Index (EBCNA). By incorporating edge information and POIs into the NA-tree structure, the EBCNA offers a comprehensive solution. All edge information, including POIs, is stored in the leaf nodes, and each edge links to its adjacent edges via pointers. This design enables direct retrieval of edge information and POIs without repeatedly trailing back to the root node. Through a comparative analysis, we have demonstrated our proposed method’s superior performance compared to the existing one.