Reverse Nearest Neighbor Search in Semantic Trajectories for Location-Based Services
Xiao Pan, Shili Nie, Haibo Hu, Philip S. Yu, Jingfeng Guo · IEEE Transactions on Services Computing · 2020
In resource planning scenarios, reverse$k$nearest neighbor search plays an important role. However, the existing reverse$k$nearest neighbor search on trajectories only supports spatial features of trajectories. In this article, we introduce reverse$k$nearest neighbors query on semantic trajectories (R$k$NNST). Given a query point from a set of geo-textual objects (e.g., POIs), the query finds those trajectories that take this query point as one of their$k$nearest geo-textual correlative objects. To efficiently answer R$k$NNST queries, we propose a novel index IMC-tree, which organizes the global and local geo-textual information on semantic trajectories. A branch-and-bound search algorithm DOTA is then designed to traverse IMC-tree with various pruning rules. To speed up the computation of correlative distance, we also design an inverted-file-based algorithm to compute without enumerating all combinations of geo-textual objects. Experiments on a real dataset validate the effectiveness and efficiency of our proposed algorithms.