Reverse nearest neighbor search in semantic trajectories for location-based services

Abstract

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 (RkNNST). 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 RkNNST 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.