Efficient reverse spatial and textual k nearest neighbor queries on road networks

The proliferation of geo-positioning technologies boosts the prevalence of GPS-enabled devices, and thus many spatial-textual objects that possess both text descriptions and geo-locations are extensively available in reality. Hence, how to efficiently exploit both spatial and textual description of objects to a spatial keyword query (SKQ) has increasingly become a challenging problem. Previous studies on SKQ problem usually focus on Euclidean space. In the real world, however, most of the spatial-textual objects lie on road networks. This paper takes the first step to investigate a novel problem, namely, reverse spatial and textual k nearest neighbor (RSTkNN) queries on road networks. We formalize the RSTkNN queries and present several spatial keyword pruning methods to accelerate the query processing. Then two effective verifying techniques are proposed, which can be seamlessly integrated into our RSTkNN query procedure. Finally, comprehensive experiments on real-world and synthetic data sets are conducted to demonstrate the performance of our approaches.